Predicción de enlaces: prediga los bordes en una red usando Networkx

La predicción de enlaces se utiliza para predecir posibles enlaces futuros en una red. Link Prediction es el algoritmo basado en el cual Facebook recomienda Personas que quizás conozcas, Amazon predice artículos que probablemente te interesen y Zomato recomienda alimentos que probablemente ordenarás.

Para este artículo, consideraríamos un gráfico como se construye a continuación:

import networkx as nx
import matplotlib.pyplot as plt
  
G = nx.Graph()
G.add_edges_from([(1, 2), (1, 3), (1, 4), (3, 4), (4, 5)])
  
plt.figure(figsize =(10, 10))
nx.draw_networkx(G, with_labels = True)

Producción:

Se pueden asumir los siguientes medios para predecir con éxito los bordes en una red:

1. cierre triádico
2. Coeficiente Jaccard
3. Índice de asignación de recursos
4. Índice Adámico de Adar
5. Apego preferencial
6. Vecino Común Comunitario
7. Asignación de recursos comunitarios

Cierre triádico:

Si dos vértices están conectados a los mismos terceros vértices, la tendencia a compartir una conexión es el Cierre Triádico.

comm_neighb(X, Y) = |N(X) N(Y)|, donde N(X) es el conjunto de todos los vecinos de X.

import networkx as nx
  
G = nx.Graph()
G.add_edges_from([(1, 2), (1, 3), (1, 4), (3, 4), (4, 5)])
e = list(G.edges())
  
def triadic(e):
  new_edges = []
  
  for i in e:
    a, b = i
  
    for j in e:
      x, y = j
  
      if i != j:
        if a == x and (b, y) not in e and (y, b) not in e:
          new_edges.append((b, y))
        if a == y and (b, x) not in e and (x, b) not in e:
          new_edges.append((b, x))
        if b == x and (a, y) not in e and (y, a) not in e:
          new_edges.append((a, y))
        if b == y and (a, x) not in e and (x, a) not in e:
          new_edges.append((a, x))
  
  return new_edges
  
print("The possible new edges according to Triadic closure are :")
print(triadic(e))

Producción:

The possible new edges according to Triadic closure are :
[(2, 3), (2, 4), (3, 2), (4, 2), (1, 5), (3, 5), (5, 1), (5, 3)]

Coeficiente de Jaccard:

Se calcula por número de vecinos comunes normalizado por número total de vecinos. Se utiliza para medir la similitud entre dos conjuntos de muestras finitas y se define como el tamaño de la intersección dividido por el tamaño de la unión de los conjuntos de muestras.

Jaccard Coefficient(X, Y) = 

import networkx as nx
  
G = nx.Graph()
G.add_edges_from([(1, 2), (1, 3), (1, 4), (3, 4), (4, 5)])
  
print(list(nx.jaccard_coefficient(G))

Producción:

[(1, 5, 0.33333333333333333), (2, 3, 0.5), (2, 4, 0.3333333333333333), (2, 5, 0.0), (3, 5, 0.5)]

La jaccard_coefficientfunción incorporada de Networkx necesariamente devuelve una lista de 3 tuplas (u, v, p), donde u, v es el nuevo borde que se agregará a continuación con una medida de probabilidad de p (p es el Coeficiente de Jaccard de los Nodes u y V).

Índice de asignación de recursos:

Entre una serie de métodos basados ​​en similitudes para predecir enlaces faltantes en una red compleja, el índice de asignación de investigación funciona bien con una menor complejidad de tiempo. Se define como una fracción de un recurso que un Node puede enviar a otro a través de sus vecinos comunes.

Research Allocation Index(X, Y) = 

import networkx as nx
  
G = nx.Graph()
G.add_edges_from([(1, 2), (1, 3), (1, 4), (3, 4), (4, 5)])
  
print(list(nx.resource_allocation_index(G)))

Producción:

[(1, 5, 0,33333333333333333), (2, 3, 0,33333333333333333), (2, 4, 0,3333333333333333), (2, 5, 0), (3, 5, 0,33333333333333333)]

El paquete networkx ofrece una función incorporada resource_allocation_indexque ofrece una lista de 3 tuplas (u, v, p), donde u, v es el nuevo borde y p es el índice de asignación de recursos del nuevo borde u, v.

Índice Adámico de Adar:

Esta medida se introdujo en 2003 para predecir los enlaces faltantes en una Red, según la cantidad de enlaces compartidos entre dos Nodes. Se calcula de la siguiente manera:

Adamic Adar Index(X, Y) = 

import networkx as nx
  
G = nx.Graph()
G.add_edges_from([(1, 2), (1, 3), (1, 4), (3, 4), (4, 5)])
  
print(list(nx.adamic_adar_index(G)))

Producción:

[(1, 5, 0,9102392266268373), (2, 3, 0,9102392266268373), (2, 4, 0,9102392266268373), (2, 5, 0), (3, 5, 0,9102392266268373)]

El paquete networkx ofrece una función incorporada adamic_adar_indexque ofrece una lista de 3 tuplas (u, v, p) donde u, v es el nuevo borde y p es el índice adámico de adar del nuevo borde u, v.

Apego preferencial:

Adjunto preferencial significa que cuanto más conectado está un Node, más probable es que reciba nuevos enlaces (consulte este artículo para consultar el gráfico de Barabasi Albert formado sobre los conceptos de Adjunto preferencial). Los Nodes con mayor grado obtienen más vecinos.

Preferential Attachment(X, Y) = |N(X)|.|N(Y)|

import networkx as nx
  
G = nx.Graph()
G.add_edges_from([(1, 2), (1, 3), (1, 4), (3, 4), (4, 5)])
  
print(list(nx.preferential_attachment(G)))

Producción:

[(1, 5, 3), (2, 3, 2), (2, 4, 3), (2, 5, 1), (3, 5, 2)]

El paquete networkx ofrece una función incorporada preferential_attachmentque ofrece una lista de 3 tuplas (u, v, p) donde u, v es el nuevo borde y p es el puntaje de conexión preferencial del nuevo borde u, v.

Comunidad de Vecinos Comunes:

Número de vecinos comunes con bonificación por vecinos de la misma comunidad. Para aplicar esto, tenemos que especificar la comunidad de todos los Nodes.

Comunidad Vecinos Comunes(X, Y) = |N(X) N(Y)| + ,
donde f(u) = 1, si u está en una comunidad; de lo contrario 0.

import networkx as nx
import matplotlib.pyplot as plt
  
G = nx.Graph()
G.add_node('A', community = 0)
G.add_node('B', community = 0)
G.add_node('C', community = 0)
G.add_node('D', community = 0)
G.add_node('E', community = 1)
G.add_node('F', community = 1)
G.add_node('G', community = 1)
G.add_node('H', community = 1)
G.add_node('I', community = 1)
  
G.add_edges_from([('A', 'B'), ('A', 'D'), ('A', 'E'), ('B', 'C'),
                  ('C', 'D'), ('C', 'F'), ('E', 'F'), ('E', 'G'), 
                             ('F', 'G'), ('G', 'H'), ('G', 'I')])
  
nx.draw_networkx(G)
print(list(nx.cn_soundarajan_hopcroft(G)))

Producción:

[('I', 'A', 0),
 ('I', 'C', 0),
 ('I', 'D', 0),
 ('I', 'E', 2),
 ('I', 'H', 2),
 ('I', 'F', 2),
 ('I', 'B', 0),
 ('A', 'H', 0),
 ('A', 'C', 4),
 ('A', 'G', 1),
 ('A', 'F', 1),
 ('C', 'H', 0),
 ('C', 'G', 1),
 ('C', 'E', 1),
 ('D', 'G', 0),
 ('D', 'E', 1),
 ('D', 'H', 0),
 ('D', 'F', 1),
 ('D', 'B', 4),
 ('G', 'B', 0),
 ('E', 'H', 2),
 ('E', 'B', 1),
 ('H', 'F', 2),
 ('H', 'B', 0),
 ('F', 'B', 1)]

El paquete networkx ofrece una función incorporada cn_soundarajan_hopcroftque ofrece una lista de 3 tuplas (u, v, p) donde u, v es el nuevo borde y p es la puntuación del nuevo borde u, v.

Asignación de recursos comunitarios:

Calcula el índice de asignación de recursos de todos los pares de Nodes utilizando información de la comunidad.

Community Resource Allocation(X, Y) = 

import networkx as nx
  
G = nx.Graph()
  
G.add_node('A', community = 0)
G.add_node('B', community = 0)
G.add_node('C', community = 0)
G.add_node('D', community = 0)
G.add_node('E', community = 1)
G.add_node('F', community = 1)
G.add_node('G', community = 1)
G.add_node('H', community = 1)
G.add_node('I', community = 1)
  
G.add_edges_from([('A', 'B'), ('A', 'D'), ('A', 'E'), ('B', 'C'),
                  ('C', 'D'), ('C', 'F'), ('E', 'F'), ('E', 'G'), 
                             ('F', 'G'), ('G', 'H'), ('G', 'I')])
  
print(list(nx.ra_index_soundarajan_hopcroft(G)))

Producción:

[('I', 'A', 0),
 ('I', 'C', 0),
 ('I', 'D', 0),
 ('I', 'E', 0.25),
 ('I', 'H', 0.25),
 ('I', 'F', 0.25),
 ('I', 'B', 0),
 ('A', 'H', 0),
 ('A', 'C', 1.0),
 ('A', 'G', 0),
 ('A', 'F', 0),
 ('C', 'H', 0),
 ('C', 'G', 0),
 ('C', 'E', 0),
 ('D', 'G', 0),
 ('D', 'E', 0),
 ('D', 'H', 0),
 ('D', 'F', 0),
 ('D', 'B', 0.6666666666666666),
 ('G', 'B', 0),
 ('E', 'H', 0.25),
 ('E', 'B', 0),
 ('H', 'F', 0.25),
 ('H', 'B', 0),
 ('F', 'B', 0)]

El paquete networkx ofrece una función incorporada ra_index_soundarajan_hopcroftque ofrece una lista de 3 tuplas (u, v, p) donde u, v es el nuevo borde y p es la puntuación del nuevo borde u, v.