Я использую матрицу смежности для представления сети друзей, которую можно визуально интерпретировать как
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 (чуть меньше месяца опыта), а не в линейной алгебре, поэтому мой код не использует операции над матрицами. Может ли кто-нибудь сделать какие-либо предложения по улучшению или сообщить мне, если моя цель даже реалистична?
