CNGF Link Prediction algorithm utilizing NetworkX

cngf_accuracy.py

# -*- coding: utf-8 -*-
"""
@author: Yash Walankar, Carlos Galo

Script compares CNGF accuracy to common neighbor accuracy utilizing networkX.
"""

import networkx as nx
import numpy as np
import random

graph = nx.karate_club_graph()


def remove_random_edge(graph,num_edges_del):
    edges_removed =[]
    
    edges = list(graph.edges)
    
    for x in range(0,num_edges_del):
        chosen_edge = random.choice(edges)
        if chosen_edge not in edges_removed:
            edges_removed.append(chosen_edge)
   
    return edges_removed

edges_removed=remove_random_edge(graph,15)

graph.remove_edges_from(edges_removed)

cngf_tupple = nx.cngf_score(graph)

cngf_list =[];
cn_list=[];

print("-----------------------------------")
print("( u , v) --   CNGF   |  CN    ")
print("-----------------------------------")

for (u, v, cngf) in cngf_tupple:
    
    cn = len(list(nx.common_neighbors(graph,u,v)))
    print(f"({u:2}, {v:2}) -- {cngf:.4f} | {cn:.4f}")
    cngf_list.append((u,v,cngf));
    cn_list.append((u,v,cn));

print("-----------------------------------")

#Setting m prime as no. of edges removed 
m_prime = len(edges_removed)

#Sorting and getting the top m_prime values 
cngf_top_predictions = sorted(cngf_list, key= lambda cngf_value:cngf_value[2],reverse=True)[:m_prime];
cn_top_predictions = sorted(cn_list, key= lambda cn_value:cn_value[2],reverse=True)[:m_prime];

print('CNGF')

cngf_correct_predictions = 0
for u,v,cngf in  cngf_top_predictions:
    if((u,v) in edges_removed):
        print(u,v)
        cngf_correct_predictions+=1        

accuracy_cngf = cngf_correct_predictions/m_prime

print('CNGF accuracy '+str(accuracy_cngf)+'%')
print("-----------------------------------")

print('CN')

cn_correct_predictions = 0
for u,v,aa in  cn_top_predictions:
    if((u,v) in edges_removed):
        print(f"({u:2}, {v:2})")
        cn_correct_predictions+=1        

accuracy_cn = cn_correct_predictions/m_prime

print('common neighbour accuracy '+str(accuracy_cn)+'%')
print("-----------------------------------")

cngf_implementation.py

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
@author: Carlos Galo, Yash Walankar
This function can be implemented by copying it into the link_prediction.py file inside the NetworkX repository.
"""

import networkx as nx

def cngf_score(G, ebunch=None):
    r"""Computes the CNGF score for all node pairs in the ebunch.

    CNGF score of 'u' and 'v' is defined as sum of guidance of all the common neighbors of 'u' and 'v'.
    Guidance is defined as degree of node common neighbor x in extracted subgraph / log(degree of common neighbor in orignal graph).

    Parameters
    ----------
    G : graph
        A NetworkX undirected graph.

    ebunch : iterable of node pairs, optional (default = None)
        The WIC measure will be computed for each pair of nodes given in
        the iterable. The pairs must be given as 2-tuples (u, v) where
        u and v are nodes in the graph. If ebunch is None then all
        non-existent edges in the graph will be used.
        Default value: None.

    Returns
    -------
    piter : iterator
        An iterator of 3-tuples in the form (u, v, p) where (u, v) is a
        pair of nodes and p is their CNGF score.

    Examples
    --------
    >>> G = nx.complete_graph(5)
    >>> preds = nx.cngf_score(G, [(0, 1)])
    >>> for u, v, p in preds:
    ...     print(f"({u}, {v}) -> {p}")
    (0, 1) -> 8.656170245

    References
    ----------
    .. [1] Liyan Dong, Yongli Li, Han Yin, Huang Le, and Mao Rui,
    "The Algorithm of Link Prediction on Social Network",
    Mathematical Problems in Engineering, vol. 2013, Article ID 125123, 7 pages, 2013.
    https://doi.org/10.1155/2013/125123
    """

    def predict(u, v):
        # Find the common neighbor set xy.commonneighbor of the node pair
        cnbors = set(nx.common_neighbors(G, u, v))
        if len(cnbors) == 0 or u == v:
            return 0
        # Extract the sub-graph which contains the tested node pair and their common neighbors
        tempCnbors = set()
        tempCnbors = tempCnbors.union(cnbors)
        tempCnbors.add(v)
        tempCnbors.add(u)
        subG = G.subgraph(tempCnbors).copy()
        similarity = 0

        def guidance(x):
            x_degree = G.degree(x)
            x_sub_degree = subG.degree(x)
            if x_degree == 1:
                return 0
            return x_sub_degree / log(x_degree)

        if cnbors is not None:
            for x in cnbors:
                similarity += guidance(x)
        return similarity

    return _apply_prediction(G, predict, ebunch)