python - 使用 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 将其视为一维矩阵，然后将其与自己的转置 s.t 相乘。列向量从右边乘以行向量。这为您提供了优先依恋分数矩阵:

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

公共(public)邻居分数使用矩阵表示法比较棘手，如果您的图形非常大(即使只有 2000 个顶点，您也会有一个包含 400 万个元素的矩阵)，无论如何我都不会使用矩阵。我会简单地为列表中的所有可能值缓存 g.neighbors(i) 的集合表示，然后使用它来计算公共(public)邻居分数，因为集合可以有效地相交:

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

如果你真的想坚持使用矩阵，你可以使用 zeros 函数构造一个 n × n 矩阵，仅由零组成NumPy 然后遍历顶点一次。获取顶点 v 的所有邻居，并注意 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