Vecinos comunes y matrices de puntuación de inserción preferencial usando igraph para python

Question

¿Existe una manera eficiente de calcular la puntuación de la matriz para los vecinos comunes (CC) y la conexión preferencial (PA) en python? Estoy usando igraph para calcular matrices de puntuación para otros métodos como el coeficiente de jaccard (Graph.similarity_jaccard()), dice (Graph.similarity_dice) y adámica/adar (Graph.similarity_inverse_log_weighted()), pero no he encontrado ninguna función para calcular matrices de puntaje para CC y PA.

Actualmente estoy haciendo:

#Preferential attachment score between nodes i and j in a graph g 
len(g.neighbors(i))*len(g.neighbors(j)) 

#Common neighbors score between nodes i and j in a graph g 
len(g.neighbors(i) and g.neighbors(j)) 

pero tengo que hacer esto para todos los bordes (i, j) de la red que en mi caso es muy grande.

Si alguien conoce alguna operación de matriz matemática que genere tales matrices de puntuación que estoy buscando, lo agradecería también.

Answer 1

No hay una función directa para esto en igraph. Sin embargo, tenga en cuenta que len(g.neighbors(i)) es simplemente el grado de vértice i, por lo que puede llamar al g.degree(), trátelo como una matriz 1D usando NumPy, luego multiplíquelo con su propia transposición a la vez. un vector de columna se multiplica por un vector de fila desde la derecha. Esto le da la matriz de puntuación de conexión preferencial:

from numpy import matrix 
d = matrix(g.degree()) 
pref_score_matrix = d.T*d 

Los vecinos comunes puntuación es más complicado usando notación matricial, y no operaría con matrices de todos modos si la gráfica es muy grande (incluso con sólo 2.000 vértices, lo haría tener una matriz con 4 millones de elementos). Simplemente habría caché establecer representaciones de g.neighbors(i) para todos los valores posibles de una lista, y luego utilizar eso para calcular las puntuaciones vecinos comunes como conjuntos se pueden cruzaron de manera eficiente:

neisets = [set(g.neighbors(i)) for i in xrange(g.vcount())] 
for v1, v2 in g.get_edgelist(): 
    common_neis = neisets[v1].intersection(neisets[v2]) 
    print "%d --> %d: %d" % (v1, v2, len(common_neis)) 

Si realmente quiere meter a las matrices, se puede construir un n por n matriz que consta de ceros solo utilizando la función zeros de NumPy y luego recorrer los vértices una vez. Obtener todos los vecinos del vértice v y tenga en cuenta que cualquier par de vecinos de v tiene un vecino en común: v sí:

from itertools import combinations 
from numpy import zeros 

n = g.vcount() 
common_neis = zeros(n, n) 
for v in xrange(g.vcount()): 
    neis = g.neighbors(v) 
    for u, w in combinations(neis, 2): 
     # v is a common neighbor of u and w 
     common_neis[u, w] += 1 
     common_neis[w, u] += 1