Common neighbors and attachment preference matrices using igraph for python

Question

Is there an efficient way to calculate matrix for common neighbors (CC) and privileged nesting (PA) in python? I use igraph to calculate the matrix of points for other methods such as the coefficient jaccard (Graph.similarity_jaccard ()), dice (Graph.similarity_dice) and adamic / adar (Graph.similarity_inverse_log_weighted ()), but I did not find any function matrices for CC and PA.

I am currently doing:

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

but I have to do this for all edges (i, j) in the network, which in my case are really big.

If anyone knows of any operation of a mathematical matrix that generates such matrixes of points that I am looking for, I would appreciate it.

Answer 1

There is no direct function for this in igraph. However, note that len(g.neighbors(i)) is just the degree of vertex i, so you can call g.degree() , treat it as a 1D matrix using NumPy, and then multiply it by your own transpose st the column vector is multiplied by the row vector on the right. This gives you the preferred anchor score matrix:

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

Estimating common neighbors is more difficult using matrix notation, and in any case, I would not work with matrices if your graph is really large (even with 2000 vertices, you will have a matrix with 4 million elements). I would simply cache the representations of the set g.neighbors(i) for all possible values ​​in the list, and then use them to calculate the general estimates of the neighbors, since the sets can intersect effectively:

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

If you really want to stick with matrices, you can build an n by n matrix consisting of zeros only using the zeros function from NumPy, and then collapse the vertices once. Get all the neighbors of the vertices v and notice that any pair of neighbors of v has one neighbor: v:

 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