Python, Scipy：使用大型邻接矩阵构建三元组

Question

我正在用一个邻接矩阵来表示朋友网络，这个矩阵可以用图形的方式来理解。

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

我在一个csr_matrix上运行这段代码大约花了21分钟。这个矩阵的大小是1032570 x 1032570，里面有88910个存储的元素。总共生成了2178893个三元组。

我需要能够在一个1968654 x 1968654的稀疏矩阵上做类似的事情，这个矩阵有9428596个存储的元素。

我对Python还很陌生（大约只有不到一个月的经验），而且线性代数也不是我的强项，这就是为什么我的代码没有利用矩阵运算的原因。有没有人能给我一些改进的建议，或者告诉我我的目标是否现实？

Answer 1

这里有一些优化建议：

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² 代表一个非常大的矩阵，即使它的内容很稀疏，平方后会变得更加密集，占用很多内存。（我曾经处理过一个类似的问题，考虑维基百科文章之间的二级链接，解决这个问题花了20分钟，在超级计算机集群节点上，用C++编写。这并不是一个简单的问题。不过，维基百科的邻接矩阵要密集得多。）

Answer 2

我觉得你只能在行或列中找到三角形。例如：

Susan    1        1      1      0 
        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