Graph Data Science con Python/NetworkX

Siamo inondati di dati. Database e fogli di calcolo in continua espansione sono pieni di informazioni aziendali nascoste. Come possiamo analizzare i dati ed estrarre conclusioni quando ce n'è così tanto? I grafici (reti, non grafici a barre) forniscono un approccio elegante.

Usiamo spesso le tabelle per rappresentare le informazioni in modo generico. Ma i grafici utilizzano una struttura di dati specializzata: invece di una riga di tabella, un nodo rappresenta un elemento. Un bordo collega due nodi per indicare la loro relazione.

Questa struttura dei dati del grafico ci consente di osservare i dati da angolazioni uniche, motivo per cui la scienza dei dati dei grafici viene utilizzata in ogni campo, dalla biologia molecolare alle scienze sociali:

Quindi, come possono gli sviluppatori sfruttare la scienza dei dati dei grafici? Passiamo al linguaggio di programmazione di data science più utilizzato: Python.

Guida introduttiva ai grafici di "teoria dei grafici" in Python

Gli sviluppatori Python hanno a disposizione diverse librerie di dati grafici, come NetworkX, igraph, SNAP e graph-tool. Pro e contro a parte, hanno interfacce molto simili per la gestione e l'elaborazione delle strutture dati dei grafici Python.

Useremo la popolare libreria NetworkX. È semplice da installare e utilizzare e supporta l'algoritmo di rilevamento della comunità che utilizzeremo.

Creare un nuovo grafico con NetworkX è semplice:

 import networkx as nx G = nx.Graph()

Ma G non è ancora un gran grafo, essendo privo di nodi e bordi.

Come aggiungere nodi a un grafico

Possiamo aggiungere un nodo alla rete concatenando il valore di ritorno di Graph() con .add_node() (o .add_nodes_from() per più nodi in un elenco). Possiamo anche aggiungere caratteristiche o attributi arbitrari ai nodi passando un dizionario come parametro, come mostriamo con node 4 e node 5 :

 G.add_node("node 1") G.add_nodes_from(["node 2", "node 3"]) G.add_nodes_from([("node 4", {"abc": 123}), ("node 5", {"abc": 0})]) print(G.nodes) print(G.nodes["node 4"]["abc"]) # accessed like a dictionary

Questo produrrà:

 ['node 1', 'node 2', 'node 3', 'node 4', 'node 5'] 123

Ma senza bordi tra i nodi, sono isolati e il set di dati non è migliore di una semplice tabella.

Come aggiungere bordi a un grafico

Simile alla tecnica per i nodi, possiamo usare .add_edge() con i nomi di due nodi come parametri (o .add_edges_from() per più bordi in un elenco) e opzionalmente includere un dizionario di attributi:

 G.add_edge("node 1", "node 2") G.add_edge("node 1", "node 6") G.add_edges_from([("node 1", "node 3"), ("node 3", "node 4")]) G.add_edges_from([("node 1", "node 5", {"weight" : 3}), ("node 2", "node 4", {"weight" : 5})])

La libreria NetworkX supporta grafici come questi, in cui ogni bordo può avere un peso. Ad esempio, in un grafico di social network in cui i nodi sono utenti e gli spigoli sono interazioni, il peso potrebbe indicare quante interazioni avvengono tra una data coppia di utenti, una metrica altamente rilevante.

NetworkX elenca tutti i bordi quando si utilizza G.edges , ma non include i loro attributi. Se vogliamo gli attributi edge, possiamo usare G[node_name] per ottenere tutto ciò che è connesso a un nodo o G[node_name][connected_node_name] per ottenere gli attributi di un particolare edge:

 print(G.nodes) print(G.edges) print(G["node 1"]) print(G["node 1"]["node 5"])

Questo produrrà:

 ['node 1', 'node 2', 'node 3', 'node 4', 'node 5', 'node 6'] [('node 1', 'node 2'), ('node 1', 'node 6'), ('node 1', 'node 3'), ('node 1', 'node 5'), ('node 2', 'node 4'), ('node 3', 'node 4')] {'node 2': {}, 'node 6': {}, 'node 3': {}, 'node 5': {'weight': 3}} {'weight': 3}

Ma leggere il nostro primo grafico in questo modo non è pratico. Per fortuna, c'è una rappresentazione molto migliore.

Come generare immagini da grafici (e grafici ponderati)

Visualizzare un grafico è essenziale: ci permette di vedere le relazioni tra i nodi e la struttura della rete in modo rapido e chiaro.

Basta una rapida chiamata a nx.draw(G) :

Rendiamo i bordi più pesanti di conseguenza più spessi tramite la nostra chiamata nx.draw() :

 weights = [1 if G[u][v] == {} else G[u][v]['weight'] for u,v in G.edges()] nx.draw(G, width=weights)

Abbiamo fornito uno spessore predefinito per i bordi senza peso, come si vede nel risultato:

I nostri metodi e algoritmi grafici stanno per diventare più complessi, quindi il passaggio successivo consiste nell'utilizzare un set di dati più noto.

Grafico della scienza dei dati utilizzando i dati del film Star Wars: Episodio IV

Per semplificare l'interpretazione e la comprensione dei nostri risultati, utilizzeremo questo set di dati. I nodi rappresentano personaggi importanti e i bordi (che non sono ponderati qui) indicano la co-apparizione in una scena.

Nota: il set di dati proviene da Gabasova, E. (2016). Rete sociale di Guerre stellari. DOI: https://doi.org/10.5281/zenodo.1411479.

Per prima cosa, visualizzeremo i dati con nx.draw(G_starWars, with_labels = True) :

I personaggi che di solito appaiono insieme, come R2-D2 e C-3PO, appaiono strettamente connessi. Al contrario, possiamo vedere che Darth Vader non condivide scene con Owen.

Layout di visualizzazione Python NetworkX

Perché ogni nodo si trova dove si trova nel grafico precedente?

È il risultato dell'algoritmo spring_layout predefinito. Simula la forza di una molla, attirando i nodi collegati e respingendo quelli disconnessi. Questo aiuta a evidenziare i nodi ben collegati, che finiscono al centro.

NetworkX ha altri layout che utilizzano criteri diversi per posizionare i nodi, come circular_layout :

 pos = nx.circular_layout(G_starWars) nx.draw(G_starWars, pos=pos, with_labels = True)

Il risultato:

Questo layout è neutro, nel senso che la posizione di un nodo non dipende dalla sua importanza: tutti i nodi sono rappresentati allo stesso modo. (Il layout circolare potrebbe anche aiutare a visualizzare componenti collegati separati, sottografi che hanno un percorso tra due nodi qualsiasi, ma qui l'intero grafico è un grande componente connesso.)

Entrambi i layout che abbiamo visto presentano un certo disordine visivo perché i bordi sono liberi di attraversare altri bordi. Ma Kamada-Kawai, un altro algoritmo diretto dalla forza come spring_layout , posiziona i nodi in modo da ridurre al minimo l'energia del sistema.

Questo riduce l'attraversamento dei bordi ma a un prezzo: è più lento di altri layout e quindi non altamente raccomandato per grafici con molti nodi.

Questo ha una funzione di disegno specializzata:

 nx.draw_kamada_kawai(G_starWars, with_labels = True)

Ciò produce invece questa forma:

Senza alcun intervento speciale, l'algoritmo ha messo i personaggi principali (come Luke, Leia e C-3PO) al centro e quelli meno importanti (come Camie e il generale Dodonna) al confine.

Visualizzare il grafico con un layout specifico può darci dei risultati qualitativi interessanti. Tuttavia, i risultati quantitativi sono una parte vitale di qualsiasi analisi della scienza dei dati, quindi dovremo definire alcune metriche.

Analisi dei nodi: Laurea e PageRank

Ora che possiamo visualizzare chiaramente la nostra rete, potrebbe interessarci caratterizzare i nodi. Esistono molteplici metriche che descrivono le caratteristiche dei nodi e, nel nostro esempio, dei caratteri.

Una metrica di base per un nodo è il suo grado: quanti archi ha. Il grado del nodo di un personaggio di Star Wars misura quanti altri personaggi hanno condiviso una scena con.

La funzione degree() può calcolare il grado di un carattere o dell'intera rete:

 print(G_starWars.degree["LUKE"]) print(G_starWars.degree)

L'output di entrambi i comandi:

 15 [('R2-D2', 9), ('CHEWBACCA', 6), ('C-3PO', 10), ('LUKE', 15), ('DARTH VADER', 4), ('CAMIE', 2), ('BIGGS', 8), ('LEIA', 12), ('BERU', 5), ('OWEN', 4), ('OBI-WAN', 7), ('MOTTI', 3), ('TARKIN', 3), ('HAN', 6), ('DODONNA', 3), ('GOLD LEADER', 5), ('WEDGE', 5), ('RED LEADER', 7), ('RED TEN', 2)]

L'ordinamento dei nodi dal più alto al più basso in base al grado può essere eseguito con una singola riga di codice:

 print(sorted(G_starWars.degree, key=lambda x: x[1], reverse=True))

L'output:

 [('LUKE', 15), ('LEIA', 12), ('C-3PO', 10), ('R2-D2', 9), ('BIGGS', 8), ('OBI-WAN', 7), ('RED LEADER', 7), ('CHEWBACCA', 6), ('HAN', 6), ('BERU', 5), ('GOLD LEADER', 5), ('WEDGE', 5), ('DARTH VADER', 4), ('OWEN', 4), ('MOTTI', 3), ('TARKIN', 3), ('DODONNA', 3), ('CAMIE', 2), ('RED TEN', 2)]

Essendo solo un totale, il grado non tiene conto dei dettagli dei singoli bordi. Un determinato edge si connette a un nodo altrimenti isolato o a un nodo connesso all'intera rete? L'algoritmo PageRank di Google aggrega queste informazioni per valutare quanto sia "importante" un nodo in una rete.

La metrica PageRank può essere interpretata come un agente che si sposta casualmente da un nodo all'altro. I nodi meglio connessi hanno più percorsi che li attraversano, quindi l'agente tenderà a visitarli più spesso.

Tali nodi avranno un PageRank più alto, che possiamo calcolare con la libreria NetworkX:

 pageranks = nx.pagerank(G_starWars) # A dictionary print(pageranks["LUKE"]) print(sorted(pageranks, key=lambda x: x[1], reverse=True))

Questo stampa il grado di Luke e i nostri personaggi ordinati per grado:

 0.12100659993223405 ['OWEN', 'LUKE', 'MOTTI', 'DODONNA', 'GOLD LEADER', 'BIGGS', 'CHEWBACCA', 'LEIA', 'BERU', 'WEDGE', 'RED LEADER', 'RED TEN', 'OBI-WAN', 'DARTH VADER', 'CAMIE', 'TARKIN', 'HAN', 'R2-D2', 'C-3PO']

Owen è il personaggio con il PageRank più alto, superando Luke, che aveva il grado più alto. L'analisi: sebbene Owen non sia il personaggio che condivide la maggior parte delle scene con altri personaggi, è un personaggio che condivide scene con molti personaggi importanti come lo stesso Luke, R2-D2 e C-3PO.

Al contrario, C-3PO, il personaggio con il terzo grado più alto, è quello con il PageRank più basso. Nonostante C-3PO abbia molte connessioni, molte di esse sono con personaggi non importanti.

Il takeaway: l'utilizzo di più metriche può fornire informazioni più approfondite sulle diverse caratteristiche dei nodi di un grafico.

Algoritmi di rilevamento della comunità

Quando si analizza una rete può essere importante separare le comunità : gruppi di nodi che sono altamente connessi tra loro ma minimamente connessi con nodi al di fuori della loro comunità.

Ci sono più algoritmi per questo. La maggior parte di essi si trova all'interno di algoritmi di apprendimento automatico non supervisionati perché assegnano un'etichetta ai nodi senza che sia necessario che siano stati etichettati in precedenza.

Uno dei più famosi è la propagazione dell'etichetta . In esso, ogni nodo inizia con un'etichetta univoca, in una comunità di uno. Le etichette dei nodi vengono aggiornate in modo iterativo in base alla maggior parte delle etichette dei nodi vicini.

Le etichette si diffondono attraverso la rete fino a quando tutti i nodi condividono un'etichetta con la maggior parte dei loro vicini. Gruppi di nodi strettamente collegati tra loro finiscono per avere la stessa etichetta.

Con la libreria NetworkX, l'esecuzione di questo algoritmo richiede solo tre righe di Python:

 from networkx.algorithms.community.label_propagation import label_propagation_communities communities = label_propagation_communities(G_starWars) print([community for community in communities])

L'output:

 [{'R2-D2', 'CAMIE', 'RED TEN', 'RED LEADER', 'OBI-WAN', 'DODONNA', 'LEIA', 'WEDGE', 'HAN', 'OWEN', 'CHEWBACCA', 'GOLD LEADER', 'LUKE', 'BIGGS', 'C-3PO', 'BERU'}, {'DARTH VADER', 'TARKIN', 'MOTTI'}]

In questo elenco di insiemi, ogni insieme rappresenta una comunità. I lettori che hanno familiarità con il film noteranno che l'algoritmo è riuscito a separare perfettamente i "bravi ragazzi" dai "cattivi", differenziando i personaggi in modo significativo senza utilizzare alcuna vera etichetta (comunità) o metadati.

Approfondimenti intelligenti utilizzando Graph Data Science in Python

Abbiamo visto che iniziare con gli strumenti di data science per i grafici è più semplice di quanto possa sembrare. Una volta che rappresentiamo i dati come un grafico utilizzando la libreria NetworkX in Python, alcune brevi righe di codice possono essere illuminanti. Possiamo visualizzare il nostro set di dati, misurare e confrontare le caratteristiche dei nodi e raggruppare i nodi in modo sensato tramite algoritmi di rilevamento della comunità.

Avere la capacità di estrarre conclusioni e approfondimenti da una rete utilizzando Python consente agli sviluppatori di integrarsi con strumenti e metodologie comunemente presenti nelle pipeline dei servizi di data science. Dai motori di ricerca alla programmazione dei voli fino all'ingegneria elettrica, questi metodi si applicano facilmente a un'ampia gamma di contesti.

Letture consigliate su Graph Data Science

Algoritmi di rilevamento della comunità
Zhao Yang, René Algesheimer e Claudio Tessone. "Un'analisi comparativa degli algoritmi di rilevamento della comunità su reti artificiali". Rapporti scientifici, 6, n. 30750 (2016).

Grafico Deep Learning
Thomas Kipf. "Reti convoluzionali del grafico". 30 settembre 2016.

Applicazioni della scienza dei dati dei grafi
Albanese, Federico, Leandro Lombardi, Esteban Feuerstein e Pablo Balenzuela. "Previsione di individui in movimento utilizzando l'estrazione di testo e l'apprendimento automatico dei grafici su Twitter". (24 agosto 2020): arXiv:2008.10749 [cs.SI].

Cohen, Elior. "PyData Tel Aviv Meetup: Node2vec." Youtube. 22 novembre 2018. Video, 21:09. https://www.youtube.com/watch?v=828rZgV9t1g.