Graph Data Science cu Python/NetworkX

Suntem inundați de date. Bazele de date și foile de calcul în continuă expansiune sunt pline de informații de afaceri ascunse. Cum putem analiza datele și extrage concluzii atunci când sunt atât de multe? Graficele (rețele, nu grafice cu bare) oferă o abordare elegantă.

Adesea folosim tabele pentru a reprezenta informația în mod generic. Dar graficele folosesc o structură de date specializată: în loc de un rând de tabel, un nod reprezintă un element. O margine conectează două noduri pentru a indica relația lor.

Această structură de date grafice ne permite să observăm datele din unghiuri unice, motiv pentru care știința datelor grafice este utilizată în fiecare domeniu, de la biologia moleculară la științele sociale:

Deci, cum pot dezvoltatorii să folosească știința datelor grafice? Să trecem la cel mai folosit limbaj de programare pentru știința datelor: Python.

Noțiuni introductive cu graficele „Teoria graficelor” în Python

Dezvoltatorii Python au la dispoziție mai multe biblioteci de date grafice, cum ar fi NetworkX, igraph, SNAP și graph-tool. Lăsând deoparte avantajele și dezavantajele, au interfețe foarte asemănătoare pentru manipularea și procesarea structurilor de date grafice Python.

Vom folosi populara bibliotecă NetworkX. Este simplu de instalat și utilizat și acceptă algoritmul de detectare a comunității pe care îl vom folosi.

Crearea unui nou grafic cu NetworkX este simplă:

 import networkx as nx G = nx.Graph()

Dar G nu este încă un graf, fiind lipsit de noduri și margini.

Cum să adăugați noduri la un grafic

Putem adăuga un nod în rețea prin înlănțuirea valorii returnate a lui Graph() cu .add_node() (sau .add_nodes_from() pentru mai multe noduri dintr-o listă). De asemenea, putem adăuga caracteristici sau atribute arbitrare nodurilor prin trecerea unui dicționar ca parametru, așa cum arătăm cu node 4 și 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

Aceasta va scoate:

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

Dar fără margini între noduri, acestea sunt izolate, iar setul de date nu este mai bun decât un simplu tabel.

Cum să adăugați margini la un grafic

Similar cu tehnica pentru noduri, putem folosi .add_edge() cu numele a două noduri ca parametri (sau .add_edges_from() pentru mai multe muchii dintr-o listă) și, opțional, includem un dicționar de atribute:

 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})])

Biblioteca NetworkX acceptă grafice ca acestea, în care fiecare muchie poate avea o greutate. De exemplu, într-un grafic al unei rețele sociale în care nodurile sunt utilizatori și marginile sunt interacțiuni, ponderea ar putea semnifica câte interacțiuni au loc între o anumită pereche de utilizatori - o măsură foarte relevantă.

NetworkX listează toate marginile când se utilizează G.edges , dar nu include atributele acestora. Dacă vrem atribute de margine, putem folosi G[node_name] pentru a obține tot ceea ce este conectat la un nod sau G[node_name][connected_node_name] pentru a obține atributele unei anumite margini:

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

Aceasta va scoate:

 ['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}

Dar citirea primului nostru grafic în acest fel este impracticabilă. Din fericire, există o reprezentare mult mai bună.

Cum se generează imagini din grafice (și grafice ponderate)

Vizualizarea unui grafic este esențială: ne permite să vedem rapid și clar relațiile dintre noduri și structura rețelei.

Un apel rapid la nx.draw(G) este tot ce este nevoie:

Să facem marginile mai grele în mod corespunzător mai groase prin apelul nostru nx.draw() :

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

Am furnizat o grosime implicită pentru marginile fără greutate, așa cum se vede în rezultat:

Metodele și algoritmii noștri grafici sunt pe cale să devină mai complexe, așa că următorul pas este să folosim un set de date mai cunoscut.

Stiinta datelor grafice folosind date din filmul Star Wars: Episode IV

Pentru a facilita interpretarea și înțelegerea rezultatelor noastre, vom folosi acest set de date. Nodurile reprezintă personaje importante, iar marginile (care nu sunt ponderate aici) înseamnă co-apariția într-o scenă.

Notă: Setul de date este de la Gabasova, E. (2016). Rețeaua socială Star Wars. DOI: https://doi.org/10.5281/zenodo.1411479.

Mai întâi, vom vizualiza datele cu nx.draw(G_starWars, with_labels = True) :

Caracterele care apar de obicei împreună, cum ar fi R2-D2 și C-3PO, par strâns legate. În schimb, putem vedea că Darth Vader nu împărtășește scene cu Owen.

Aspecte de vizualizare Python NetworkX

De ce fiecare nod este situat acolo unde se află în graficul anterior?

Este rezultatul algoritmului implicit spring_layout . Simulează forța unui arc, atrăgând nodurile conectate și respingându-le pe cele deconectate. Acest lucru ajută la evidențierea nodurilor bine conectate, care ajung în centru.

NetworkX are alte aspecte care folosesc criterii diferite pentru a poziționa nodurile, cum ar fi circular_layout :

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

Rezultatul:

Acest aspect este neutru în sensul că locația unui nod nu depinde de importanța acestuia - toate nodurile sunt reprezentate în mod egal. (Dispunerea circulară ar putea ajuta și la vizualizarea componentelor conectate separate - subgrafe care au o cale între oricare două noduri - dar aici, întregul grafic este o componentă mare conectată.)

Ambele aspecte pe care le-am văzut au un anumit grad de dezordine vizuală, deoarece marginile sunt libere să traverseze alte margini. Dar Kamada-Kawai, un alt algoritm de forță, precum spring_layout , poziționează nodurile astfel încât să minimizeze energia sistemului.

Acest lucru reduce încrucișarea marginilor, dar la un preț: este mai lent decât alte aspecte și, prin urmare, nu este foarte recomandat pentru graficele cu multe noduri.

Acesta are o funcție de extragere specializată:

 nx.draw_kamada_kawai(G_starWars, with_labels = True)

Asta dă în schimb această formă:

Fără nicio intervenție specială, algoritmul a pus personajele principale (cum ar fi Luke, Leia și C-3PO) în centru, iar pe cele mai puțin proeminente (cum ar fi Camie și generalul Dodonna) la graniță.

Vizualizarea graficului cu un aspect specific ne poate oferi niște rezultate calitative interesante. Cu toate acestea, rezultatele cantitative sunt o parte vitală a oricărei analize a științei datelor, așa că va trebui să definim unele valori.

Analiza nodurilor: grad și PageRank

Acum că ne putem vizualiza rețeaua în mod clar, ar putea fi de interes pentru noi să caracterizăm nodurile. Există mai multe metrici care descriu caracteristicile nodurilor și, în exemplul nostru, ale personajelor.

O metrică de bază pentru un nod este gradul său: câte muchii are. Gradul nodului unui personaj din Star Wars măsoară cu câte alte personaje au împărtășit o scenă.

Funcția degree() poate calcula gradul unui caracter sau al întregii rețele:

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

Ieșirea ambelor comenzi:

 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)]

Sortarea nodurilor de la cel mai mare la cel mai mic în funcție de grad se poate face cu o singură linie de cod:

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

Ieșire:

 [('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)]

Fiind doar un total, gradul nu ia în considerare detaliile marginilor individuale. O margine dată se conectează la un nod altfel izolat sau la un nod care este conectat cu întreaga rețea? Algoritmul PageRank de la Google adună aceste informații pentru a evalua cât de „important” este un nod într-o rețea.

Valoarea PageRank poate fi interpretată ca un agent care se deplasează aleatoriu de la un nod la altul. Nodurile mai bine conectate au mai multe căi care duc prin ele, așa că agentul va avea tendința de a le vizita mai des.

Astfel de noduri vor avea un PageRank mai mare, pe care îl putem calcula cu biblioteca NetworkX:

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

Aceasta afișează rangul lui Luke și personajele noastre sortate după rang:

 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 este personajul cu cel mai mare PageRank, depășindu-l pe Luke, care avea cel mai înalt grad. Analiza: Deși Owen nu este personajul care împarte cele mai multe scene cu alte personaje, el este un personaj care împarte scene cu multe personaje importante precum Luke însuși, R2-D2 și C-3PO.

În contrast mai mare, C-3PO, personajul cu gradul al treilea cel mai înalt, este cel cu cel mai mic PageRank. În ciuda faptului că C-3PO are multe conexiuni, multe dintre ele au personaje neimportante.

Concluzie: utilizarea mai multor valori poate oferi o perspectivă mai profundă asupra diferitelor caracteristici ale nodurilor unui grafic.

Algoritmi de detectare a comunității

Când se analizează o rețea, poate fi important să se separe comunitățile : grupuri de noduri care sunt puternic conectate între ele, dar puțin conectate cu noduri din afara comunității lor.

Există mai mulți algoritmi pentru aceasta. Cele mai multe dintre ele se găsesc în algoritmi de învățare automată nesupravegheați, deoarece atribuie o etichetă nodurilor fără a fi nevoie ca acestea să fi fost etichetate anterior.

Una dintre cele mai cunoscute este propagarea etichetei . În el, fiecare nod începe cu o etichetă unică, într-o comunitate de unul. Etichetele nodurilor sunt actualizate iterativ în funcție de majoritatea etichetelor nodurilor învecinate.

Etichetele difuzează prin rețea până când toate nodurile împărtășesc o etichetă cu majoritatea vecinilor lor. Grupuri de noduri strâns legate între ele ajung să aibă aceeași etichetă.

Cu biblioteca NetworkX, rularea acestui algoritm necesită doar trei linii de Python:

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

Ieșire:

 [{'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'}]

În această listă de seturi, fiecare set reprezintă o comunitate. Cititorii familiarizați cu filmul vor observa că algoritmul a reușit să separe perfect „băieții buni” de „băieții răi”, diferențiind personajele în mod semnificativ fără a utiliza vreo etichetă sau metadate adevărate (comunității).

Perspective inteligente folosind știința datelor grafice în Python

Am văzut că începerea cu instrumentele de știință a datelor grafice este mai simplă decât ar părea. Odată ce reprezentăm datele ca un grafic folosind biblioteca NetworkX în Python, câteva linii scurte de cod pot fi iluminatoare. Ne putem vizualiza setul de date, măsura și compara caracteristicile nodurilor și nodurile cluster în mod sensibil prin algoritmi de detectare a comunității.

Având abilitățile de a extrage concluzii și perspective dintr-o rețea folosind Python, le permite dezvoltatorilor să se integreze cu instrumente și metodologie întâlnite în mod obișnuit în conductele de servicii de știință a datelor. De la motoarele de căutare la programarea zborurilor până la inginerie electrică, aceste metode se aplică cu ușurință într-o gamă largă de contexte.

Lectură recomandată despre știința datelor grafice

Algoritmi de detectare a comunității
Zhao Yang, Rene Algesheimer și Claudio Tessone. „O analiză comparativă a algoritmilor de detectare a comunității pe rețelele artificiale.” Rapoarte științifice, 6, nr. 30750 (2016).

Învățare profundă grafică
Thomas Kipf. „Grafic rețele convoluționale”. 30 septembrie 2016.

Aplicații ale științei datelor grafice
Albanese, Federico, Leandro Lombardi, Esteban Feuerstein și Pablo Balenzuela. „Predicția persoanelor aflate în schimbare folosind text Mining și Graph Machine Learning pe Twitter.” (24 august 2020): arXiv:2008.10749 [cs.SI].

Cohen, Elior. „Întâlnirea PyData Tel Aviv: Node2vec.” YouTube. 22 noiembrie 2018. Video, ora 21:09. https://www.youtube.com/watch?v=828rZgV9t1g.