12

隣接行列を使用して、視覚的に次のように解釈できる友人のネットワークを表現しています。

Mary     0        1      1      1

Joe      1        0      1      1

Bob      1        1      0      1

Susan    1        1      1      0 

         Mary     Joe    Bob    Susan

このマトリックスを使用して、ユーザー1がユーザー2と友達であり、ユーザー2がユーザー3と友達であるという条件で、考えられるすべての友情の三角形のリストを作成します。私のリストでは、ユーザー1がと友達である必要はありません。ユーザー3。

(joe, mary, bob)
(joe, mary, susan)
(bob, mary, susan)
(bob, joe, susan)

小さな三角形でうまく機能するコードが少しありますが、非常に大きなスパース行列に合わせてスケーリングする必要があります。

from numpy import *
from scipy import *

def buildTriangles(G):
    # G is a sparse adjacency matrix
    start = time.time()
    ctr = 0
    G = G + G.T          # I do this to make sure it is symmetric
    triples = []
    for i in arange(G.shape[0] - 1):  # for each row but the last one
        J,J = G[i,:].nonzero()        # J: primary friends of user i
                                      # I do J,J because I do not care about the row values
        J = J[ J < i ]                # only computer the lower triangle to avoid repetition
        for j in J:
            K, buff = G[:,j].nonzero() # K: secondary friends of user i
            K = K[ K > i ]             # only compute below i to avoid repetition
            for k in K:
                ctr = ctr + 1
                triples.append( (i,j,k) )
    print("total number of triples: %d" % ctr)
    print("run time is %.2f" % (time.time() - start())
    return triples

私は約21分でcsr_matrixでコードを実行することができました。マトリックスは1032570x1032570で、88910個の格納された要素が含まれていました。合計2178893個のトリプレットが生成されました。

9428596の格納された要素を持つ1968654x1968654のスパース行列で同様のことを実行できる必要があります。

私はPythonに非常に慣れておらず（1か月弱の経験）、線形代数が得意ではありません。そのため、私のコードは行列演算を利用していません。誰かが改善のための提案をしたり、私の目的が現実的であるかどうかを教えてもらえますか？

4

2 に答える 2

6

三角形は行か列でしか見つけられないと思います。例えば：

Susan    1        1      1      0 
        Mary     Joe    Bob    Susan

これは、メアリー、ジョー、ボブがすべてスーザンの友達であることを意味します。したがって、組み合わせを使用して[メアリー、ジョー、ボブ]から2人を選択し、スーザンと組み合わせると1つの三角形が得られます。itertools.combinations（）はこれをすばやく行います。

コードは次のとおりです。

import itertools
import numpy as np

G = np.array(   # clear half of the matrix first
    [[0,0,0,0],
     [1,0,0,0],
     [1,1,0,0],
     [1,1,1,0]])
triples = []     
for i in xrange(G.shape[0]):
    row = G[i,:]
    J = np.nonzero(row)[0].tolist() # combinations() with list is faster than NumPy array.
    for t1,t2 in itertools.combinations(J, 2):
        triples.append((i,t1,t2))
print triples
于 2011-08-03T23:03:08.580 に答える
4

最適化のためのいくつかの提案があります：

K = K[ K > i ]             # only compute below i to avoid repetition
for k in K:
    ctr = ctr + 1
    triples.append( (i,j,k) )

ループでインクリメントしないでください、それはひどく遅いです。ただctr += K.shape[0]やる。次に、をに置き換えて、最も深くネストされたループを完全に削除しますappend。

triples += ((i, j, k) for k in K[K > i])

ここで、このタスクで実際のパフォーマンスが必要な場合は、線形代数を使用する必要があります。「考えられるすべての友情の三角形のリストを作成したい」とは、隣接行列を2乗したいという意味です。これは、単純なで実行できます**2。

次に、1.968.654²は非常に大きな行列を意味し、非常にスパースであっても、その正方形ははるかに少なく、多くのメモリを消費することを理解してください。（私はかつて、C ++のスーパーコンピュータークラスターノードで、解決に20分かかった距離2のウィキペディア記事間のリンクを検討した同様の問題に取り組みました。これは簡単な問題ではありません。ウィキペディア隣接行列は数桁でした。ただし、桁違いに密度が高くなります。）

于 2011-08-03T20:42:00.880 に答える