使用 igraph for python 计算常见邻居和优先连接得分矩阵

Question

有没有什么高效的方法可以用Python计算常见邻居的矩阵得分（CC）和优先连接（PA）呢？我现在在用igraph库计算其他方法的得分矩阵，比如Jaccard系数（Graph.similarity_jaccard()）、Dice系数（Graph.similarity_dice）和Adamic/Adar（Graph.similarity_inverse_log_weighted()），但是我找不到可以计算CC和PA得分矩阵的函数。

目前我在做的是：

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

不过我得对网络中的所有边(i,j)都进行这个操作，而在我的情况下，网络真的很大。

如果有人知道有什么数学矩阵运算可以生成我想要的得分矩阵，我会非常感激。

Answer 1

在igraph中没有直接的函数可以做到这一点。不过，要知道，len(g.neighbors(i))其实就是顶点i的度数，也就是它有多少个邻居。所以你可以调用g.degree()，然后用NumPy把它当作一维矩阵来处理，再把它和自己的转置相乘，这样就能得到一个优先连接得分矩阵：

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

计算共同邻居得分就比较复杂了，使用矩阵表示法也不是个好主意，特别是当你的图很大的时候（就算只有2000个顶点，你也会得到一个有400万个元素的矩阵）。我建议直接把g.neighbors(i)的集合表示缓存到一个列表中，然后用这个来计算共同邻居得分，因为集合之间的交集计算起来很高效：

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

如果你真的想用矩阵的话，可以用NumPy的zeros函数构建一个只有零的n乘n的矩阵，然后遍历一次所有的顶点。获取顶点v的所有邻居，并注意到任何一对邻居都有一个共同的邻居，就是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