6

有没有一种有效的方法来计算python中共同邻居（CC）和优先附件（PA）的矩阵分数？我正在使用 igraph 计算其他方法的分数矩阵，例如 jaccard 系数 (Graph.similarity_jaccard())、dice (Graph.similarity_dice) 和 adam/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）执行此操作，在我的情况下它确实很大。

如果有人知道任何生成我正在寻找的分数矩阵的数学矩阵运算，我也会很感激。

4

1 回答 1

2

在 igraph 中没有直接的功能。但是，请注意，这len(g.neighbors(i))只是顶点i的度数，因此您可以调用g.degree()，使用 NumPy 将其视为一维矩阵，然后将其与其自己的转置 st 相乘，列向量乘以右侧的行向量。这为您提供了优先附件得分矩阵：

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 中的函数构造一个由零组成的n x nzeros矩阵，然后在顶点上循环一次。获取顶点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
于 2011-07-09T15:54:11.470 回答