6

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）に対してこれを行う必要があります。

私が探しているそのようなスコア行列を生成する数学的な行列演算を誰かが知っているなら、私も感謝します。

4

1 に答える 1

2

igraphにはこれに対する直接的な機能はありません。ただし、これlen(g.neighbors(i))は単に頂点iの次数であるため、を呼び出しg.degree()、NumPyを使用して1D行列として扱い、それを独自の転置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行n列の行列を作成し、頂点を1回ループすることができます。zeros頂点vのすべてのネイバーを取得し、 vのネイバーのペアには共通のネイバーが1つあることに注意してください。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 に答える