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 上运行代码。该矩阵为 1032570 x 1032570，包含 88910 个存储元素。总共生成了 2178893 个三元组。

我需要能够对 1968654 x 1968654 稀疏矩阵和 9428596 个存储元素做类似的事情。

我对 python 非常陌生（不到一个月的经验），并且在线性代数方面不是最好的，这就是为什么我的代码没有利用矩阵运算的原因。任何人都可以提出任何改进建议或让我知道我的目标是否现实？

4

2 回答 2

6

我认为您只能在行或列中找到三角形。例如：

Susan    1        1      1      0 
        Mary     Joe    Bob    Susan

这意味着 Mary、Joe、Bob 都是 Susan 的朋友，因此，使用组合从 [Mary, Joe, Bob] 中选择两个人，并将其与 Susan 组合将得到一个三角形。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.

然后意识到 1.968.654² 意味着一个非常大的矩阵，即使它非常稀疏，它的平方也会小得多，并且会占用大量内存。（我曾经解决过一个类似的问题，我考虑了距离为 2 的 Wikipedia 文章之间的链接，这需要 20 分钟才能在超级计算机集群节点上用 C++解决。这不是一个简单的问题。Wikipedia 邻接矩阵是几个订单不过，数量级更密集。）

于 2011-08-03T20:42:00.880 回答