Vicini comuni e matrici di punteggi di attaccamento preferenziali usando igraph per python

Question

Esiste un modo efficiente per calcolare il punteggio di matrice per vicini comuni (CC) e attacco preferenziale (PA) in python? Sto usando igraph per calcolare le matrici dei punteggi per altri metodi come il coefficiente di jaccard (Graph.similarity_jaccard()), i dadi (Graph.similarity_dice) e adamic/adar (Graph.similarity_inverse_log_weighted()), ma non ho trovato alcuna funzione calcolare le matrici dei punteggi per CC e PA.

Attualmente sto facendo:

#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)) 

ma devo fare questo per tutti i bordi (i, j) della rete che nel mio caso è davvero grande.

Se qualcuno conosce un'operazione di matrice matematica che genera tali matrici di punteggio che sto cercando, apprezzerei anche.

Answer 1

Non esiste una funzione diretta per questo in igraph. Tuttavia, si noti che len(g.neighbors(i)) è semplicemente il grado del vertice i, quindi è possibile chiamare g.degree(), trattarlo come una matrice 1D utilizzando NumPy, quindi moltiplicarlo con la propria trasposizione s.t. un vettore colonna viene moltiplicato per un vettore riga da destra. Questo vi dà la preferenziale matrice di punteggio attacco:

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

I vicini comuni punteggio più complicato utilizzando la notazione della matrice, e non mi funzionano con le matrici in ogni caso se il grafico è davvero grande (anche con solo 2000 i vertici, si farebbe avere una matrice con 4 milioni di elementi). Vorrei semplicemente Cache set rappresentazioni di g.neighbors(i) per tutti i possibili valori di una lista, e quindi utilizzare tale per calcolare i punteggi vicini comuni come set possono essere intersecati in modo efficiente:

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)) 

Se si vuole veramente a bastone per le matrici, è È possibile costruire un n. per n. matrice composta da zeri solo utilizzando la funzione zeros da NumPy e quindi eseguire un ciclo sui vertici una volta. Ottenere tutti i vicini di vertice v e notare che qualsiasi coppia dei vicini di v hanno un vicino in comune: v stessa:

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