Quali problemi di scalabilità sono associati a NetworkX?

Question

Sono interessato all'analisi di rete su reti di grandi dimensioni con milioni di nodi e decine di milioni di spigoli. Voglio essere in grado di fare cose come analizzare reti da molti formati, trovare componenti connessi, rilevare comunità ed eseguire misure di centralizzazione come PageRank.

Sono attratto da NetworkX perché ha una bella API, una buona documentazione ed è stato in sviluppo attivo per anni. Inoltre perché è in Python, dovrebbe essere veloce da sviluppare con.

In una recente presentazione (le diapositive sono disponibili su GitHub here), è stato affermato che:

differenza di molti altri strumenti, NX è progettato per gestire i dati su scala rilevante per problemi moderni .. La maggior parte degli algoritmi di base in NX si basa su un codice legacy estremamente veloce.

La presentazione afferma inoltre che gli algoritmi di base di NetworkX sono implementati in C/Fortran.

Tuttavia, guardando il codice sorgente, sembra che NetworkX sia principalmente scritto in python. Non ho molta familiarità con il codice sorgente, ma sono a conoscenza di un paio di esempi in cui NetworkX usa numpy per fare sollevamento pesi (che a sua volta usa C/Fortran per fare algebra lineare). Ad esempio, il file networkx/networkx/algorithms/centrality/eigenvector.py utilizza numpy per calcolare autovettori.

Qualcuno sa se questa strategia di chiamare una libreria ottimizzata come numpy è davvero diffusa in tutta NetworkX, o se solo pochi algoritmi lo fanno? Qualcuno può inoltre descrivere altri problemi di scalabilità associati a NetworkX?

Modulo risposta NetworkX Capo Programmatore ho posto questa domanda sulla mailing list NetworkX, e Aric Hagberg ha risposto:

Le strutture di dati utilizzati in NetworkX sono appropriati per scalare fino a problemi di grandi dimensioni (ad esempio, il la struttura dei dati è una lista di adiacenze). Gli algoritmi hanno varie proprietà di ridimensionamento ma alcuni di quelli che si menzionano sono utilizzabili (ad esempio PageRank, i componenti connessi sono una complessità lineare del numero di spigoli).

A questo punto NetworkX è puro codice Python. La struttura di adiacenza è codificata con dizionari Python che offre una grande flessibilità a scapito della memoria e della velocità di calcolo. I grafici grandi porteranno a molta memoria e alla fine finirai.

NetworkX utilizza NumPy e SciPy per algoritmi che sono principalmente basati su algebra lineare. In questo caso il grafico viene rappresentato come (copiata) come matrice di adiacenza utilizzando le matrici NumPy o le matrici sparse di SciPy . Questi algoritmi possono trarre vantaggio dal codice FORTRAN C e utilizzato in NumPy e SciPY.

Answer 1

Il tuo grande problema sarà la memoria. Python semplicemente non può gestire decine di milioni di oggetti, senza saltare i cerchi nell'implementazione di classe. Il sovraccarico della memoria di molti oggetti è troppo alto, si colpisce 2 GB e il codice a 32 bit non funzionerà. Ci sono modi per aggirarlo, usando slot, array o numpy. È dovrebbe essere OK, perché networkx è stato scritto per le prestazioni, ma se ci sono alcune cose che semplicemente non funzionano controllerò l'utilizzo della memoria.

Per quanto riguarda il ridimensionamento, gli algoritmi sono fondamentalmente l'unica cosa che importa con i grafici. Gli algoritmi dei grafici tendono ad avere in realtà scaling brutto se sono fatti male, e hanno la stessa probabilità di essere fatti bene in Python come qualsiasi altra lingua.

Answer 2

Il fatto che networkX sia scritto principalmente in python non significa che non sia scalabile, né rivendichi la perfezione. C'è sempre un compromesso. Se spendi di più sulle tue "macchine", avrai la scalabilità che desideri più i vantaggi dell'uso di una libreria di grafici pitonici.

In caso contrario, ci sono altre soluzioni, (here e here), che possono consumare meno memoria (punto di riferimento e da vedere, penso che IGRAPH è completamente C sostenuta in modo da esso), ma si può perdere la sensazione divinatorio di NX.

Answer 3

Questa è una vecchia questione, ma penso che la pena ricordare che graph-tool ha una funzionalità molto simile a NetworkX, ma è implementato in C++ con i modelli (utilizzando la spinta Graph Library), e quindi è molto più veloce (up to two orders of magnitude) e utilizza molta meno memoria.

Disclaimer: Sono l'autore di graph-tool.