tutorial - Python, Scipy: construyendo trillizos usando una gran matriz de adyacencia

transpuesta de una matriz en python

Question

Estoy usando una matriz de adyacencia para representar una red de amigos que se puede interpretar visualmente como

Mary     0        1      1      1

Joe      1        0      1      1

Bob      1        1      0      1

Susan    1        1      1      0 

         Mary     Joe    Bob    Susan

Usando esta matriz, quiero compilar una lista de todos los posibles triángulos de amistad con la condición de que el usuario 1 sea amigo del usuario 2, y el usuario 2 sea amigo del usuario 3. Para mi lista, no es necesario que el usuario 1 sea amigo de usuario 3.

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

Tengo un poco de código que funciona bien con triángulos pequeños, pero lo necesito para escalar matrices dispersas muy grandes.

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

Pude ejecutar el código en una csr_matrix en aproximadamente 21 minutos. La matriz era 1032570 x 1032570 y contenía 88910 elementos almacenados. Hubo un total de 2178893 trillizos generados.

Necesito poder hacer algo similar con una matriz escasa 1968654 x 1968654 con 9428596 elementos almacenados.

Soy muy nuevo en Python (poco menos de un mes de experiencia) y no el mejor en álgebra lineal, por lo que mi código no aprovecha las operaciones de matrices. ¿Alguien puede hacer alguna sugerencia para mejorar o dejarme saber si mi objetivo es incluso realista?

Answer 1

Aquí hay algunas sugerencias para la optimización:

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

No incremente en un bucle, es terriblemente lento. Solo ctr += K.shape[0] . Luego, elimine completamente el ciclo anidado al reemplazar el append por

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

Ahora, si quieres un rendimiento real en esta tarea, tendrás que entrar en álgebra lineal. "Quiero compilar una lista de todos los posibles triángulos de amistad" significa que desea cuadrar la matriz de adyacencia, lo que puede hacer con un simple **2 .

Entonces date cuenta de que 1.968.654² significa una matriz muy grande, y aunque es muy escasa, su cuadrado será mucho menor y requerirá mucha memoria. (Una vez abordé un problema similar cuando consideré enlaces entre artículos de Wikipedia a una distancia dos, que tardó 20 minutos en resolverse, en un nodo de clúster de supercomputadora , en C ++ . Esto no es un problema trivial. La matriz de adyacencia de Wikipedia era unas pocas órdenes de magnitud más densa, sin embargo)

Answer 2

Creo que puedes encontrar triángulos solo en filas o columnas. por ejemplo:

Susan    1        1      1      0 
        Mary     Joe    Bob    Susan

esto significa que Mary, Joe, Bob son todos amigos de Susan, entonces, usa combinaciones para elegir dos personas de [Mary, Joe, Bob], y combínalo con Susan para obtener un triángulo. itertools.combinations () hace esto rápidamente.

Aquí está el código:

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