effizienter Algorithmus 2-Stufen-Nachbarn für alle Knoten in einem gerichteten Graphen zu finden

Question

Ich habe eine große Graphen im CSV-Format (~ 14GB) von Kanten als ganze Zahlen in folgendem Format dargestellt:

node1,node2 
3213741,23521361 
3213741,6532710 
3213741,12340611 
3213741,6457392 
3213741,9682135 
6567133,12956771 
6567133,2386

node1 ist wo die Kante beginnt und node2 ist, wo die Kante endet. Die Kanten sind nach node1 gruppiert (gruppierbar nach node2).

Ich brauche 2-Schritt-Nachbarn für alle Knoten zu generieren. Das ist in folgendem Format:

node1,node2,node3 
3213741,6532710,5347128 

Meine Idee, eine Kopie der Kanten zu machen ist, und sortiert sich nach Knoten2, so gibt es zwei Tabellen t1.node1,t1.node2 und t2.node1,t2.node2, dann irgendwie diese beiden Tabellen verbinden, wenn t1.node1 == t2.node1 und t1.node1 != t2.node2. Aber das sieht zu langsam aus. Gibt es bessere Algorithmen oder Algorithmen, die die Tatsache nutzen können, dass die Daten nach node1 gruppiert sind? Ich bevorzuge Numpy. Vielen Dank.

Answer 1

Ich schrieb einige Code der Sparse-Matrix-Ansatz vorgeschlagen von obachtos Implementierung und dask mit parallel auf einem einzelnen Knoten auszuführen:

import numpy as np 
import pandas as pd 
import dask 
import time 
from scipy.sparse import coo_matrix 

np.random.seed(1) 

# Fabricate some data 
elem = int(1e7) 
rng = int(1e5) 
gr = np.random.randint(0, rng, elem * 2, np.uint32) 
gr = gr.reshape((elem, 2)) 
gr = gr[np.argwhere(gr[:, 0] != gr[:, 1])] 
gr = gr.reshape(-1, 2) 
grdf = pd.DataFrame(data=gr) 
gr = grdf.drop_duplicates().values 

def coord2adjacency(coords, shp, order, chunksize): 
    grsp = coo_matrix((np.ones(gr.shape[0]), (gr[:, 0], gr[:, 1])), 
         shape=(shp, shp)) 
    grcsr = grsp.tocsr() 
    adj = grcsr**order 
    return adj 

adjspdel = dask.delayed(coord2adjacency, 
         pure=True, nout=1, traverse=False)(gr, shp=rng, 
                  order=2, 
                  chunksize=5000) 
print('Computing an adjacency matrix of order {ordr} from {n} coordinates.'\ 
     .format(ordr=2, n=gr.shape[0])) 
t0 = time.time() 
adjsp = adjspdel.compute() 
print('Execution time: {tm} minutes.'.format(tm=(time.time() - t0)/60)) 

Auf meinem 4-Kern/8 GB PC war die Ausführungszeit 4.1 Protokoll. Das OP-Problem ist noch einige Größenordnungen größer. Das dask distributed-Paket sollte einen ähnlichen Code zulassen, um auf einem Cluster zu laufen, der groß genug für die Aufgabe ist.

Answer 2

Je nachdem, wie groß Ihr Speicher ist, könnten Sie eine Adjazenzmatrix als scipy.sparse.coo_matrix erstellen (dh eine Matrix, die Knoten hat, wenn zwei Knoten verbunden sind und an anderer Stelle Nullen), diese in einen anderen Typ von Sparse-Matrix konvertieren und dann das Quadrat nehmen . Diese Matrix enthält Einträge genau dort, wo Verbindungen zweiter Ordnung existieren. Der Wert des Eintrags sagt Ihnen sogar, wie viele Pfade zwischen den Knoten mit der Länge zwei existieren.