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

Я думаю, что вы можете найти треугольники только в строках или столбцах.например:

Susan    1        1      1      0 
        Mary     Joe    Bob    Susan

это означает, что Мэри, Джо, Боб - все друзья Сьюзен, поэтому используйте комбинации, чтобы выбрать двух человек из [Мэри, Джо, Боб], и объедините их с Сьюзен, чтобы получить одноготреугольник.itertools.combination () делает это быстро.

Вот код:

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

Answer 2

Вот несколько советов по оптимизации:

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])

Теперь, если вы хотите real производительности в этой задаче, вам нужно будет перейти к некоторому линейномуалгебра.«Я хочу составить список всех возможных треугольников дружбы» означает, что вы хотите возвести в квадрат матрицу смежности, что вы можете сделать с помощью простого **2.

Затем поймите, что 1.968.654² означает очень большойматрица, и хотя она очень разреженная, ее площадь будет намного меньше и займет много памяти.(Однажды я решил аналогичную проблему, когда рассматривал связи между статьями Википедии на расстоянии два, на решение которых потребовалось 20 минут на узле кластера суперкомпьютера , в C ++ .тривиальная проблема. Хотя матрица смежности Википедии была на несколько порядков плотнее.)