Eulero e la teoria dei grafi

Per comprendere i molti modi in cui le reti possono influenzare le proprietà di un sistema, bisogna familiarizzare con la teoria dei grafi, una branca della matematica nata dalle prove del signor Eulero. Questo articolo vuole familiarizzare ed introdurre caratteristiche elementari delle reti come il degree distribution, i percorsi, le distanze tra nodi per imparare a distinguere, anche nei prossimi articoli sul tema, alcuni tipi di reti.

I ponti di Königsberg

La teoria dei grafi, l’impalcatura matematica dietro la scienza delle reti, affonda le proprie radici nel lontano 1735 a Königsberg, capitale della Prussia orientale, una fiorente città mercantile del suo tempo. Il commercio sostenuto dalla sua flotta permise ai funzionari della città di costruire sette ponti attraverso il fiume Pregel, che circondava la città. Cinque di questi collegavano alla terraferma l’elegante isola di Kneiphof, intrappolata tra i due rami del Pregel (Immagine 1). Questa peculiare disposizione ha dato vita a un quiz contemporaneo: si può attraversare tutti e sette i ponti senza passare due volte sullo stesso? Nonostante molti tentativi, nessuno è riuscito a trovare un simile percorso. Il problema rimase irrisolto fino al 1735, quando Leonhard Euler, un matematico svizzero, offrì una rigorosa dimostrazione matematica della non esistenza di tale percorso.

Egli semplificò il quiz creando un grafo: i nodi (A, B, C, D) rappresentavano i lembi di terra, mentre i link (a, b, c, d, e, f, g) raffiguravano i ponti. Quindi Eulero fece una semplice osservazione: se c’è un percorso che attraversa tutti i ponti, ma mai lo stesso ponte due volte, vuol dire che i nodi con un numero dispari di collegamenti devono essere il punto iniziale o finale di questo percorso. Infatti, se si arriva a un nodo con un numero dispari di link, è possibile che non si disponga di alcun collegamento inutilizzato per poterlo lasciare. Il grafico di Königsberg aveva quattro nodi con un numero dispari di collegamenti, quindi nessun percorso poteva soddisfare il problema.

Fu la prima volta in cui un grafo venne utilizzato per risolvere un problema matematico. La dimostrazione ebbe due messaggi importanti:

• alcuni problemi diventano più semplici e più trattabili se sono rappresentati come grafo
• l’esistenza del percorso non dipende dal nostro ingegno per trovarlo.

Quest’ultima piuttosto, è una proprietà del grafo. In effetti, data la struttura del grafo di Königsberg, non importa quanto siamo intelligenti, non troveremo mai il percorso desiderato! In altre parole, le reti hanno proprietà codificate nella loro struttura che limitano o migliorano il loro comportamento.

Reti e grafi: cosa sono?

Se vogliamo comprendere un sistema complesso, dobbiamo prima sapere come i suoi componenti interagiscono tra loro. Una rete è un catalogo di componenti di un sistema spesso chiamati nodi o vertici e le interazioni dirette tra di essi, chiamate collegamenti o bordi. Questa rappresentazione della rete offre un linguaggio comune per studiare sistemi che possono differire notevolmente in natura, aspetto o ambito. In effetti, come mostrato nell’immagine 2, tre sistemi piuttosto diversi hanno esattamente la stessa rappresentazione di rete.

L’immagine 2 introduce due parametri di rete:

• Il numero di nodi, o N, rappresenta il numero di componenti nel sistema
• Il numero di collegamenti, che indichiamo con L, rappresenta il numero totale di interazioni tra i nodi.

Le reti mostrate nell’immagine 2 hanno N = 4 e L = 4. I collegamenti di una rete possono essere diretti o non diretti. Alcuni sistemi hanno collegamenti diretti, come il WWW, i cui URL puntano da un documento Web all’altro, o le telefonate, in cui una persona chiama un’ altra. Altri sistemi hanno collegamenti diretti, come i rapporti romantici (se esco con Laura, anche Laura mi dà appuntamento), o come linee di trasmissione sulla rete elettrica, su cui la corrente elettrica può fluire in entrambe le direzioni.

Una rete è chiamata:

• diretta (o digraph) se tutti i suoi collegamenti sono diretti
• indiretta se tutti i suoi collegamenti sono non diretti

Alcune reti hanno collegamenti diretti e non diretti. Per esempio nella rete metabolica alcune reazioni sono reversibili (cioè bidirezionali o non orientate) e altre sono irreversibili, avendo luogo in una sola direzione (diretta).

Le scelte che facciamo quando rappresentiamo un sistema come rete determineranno la nostra capacità di utilizzare con successo la scienza delle reti per risolvere un particolare problema. Ad esempio, il modo in cui definiamo i collegamenti tra due individui determina la natura delle domande che possiamo esplorare:

• Collegando individui che interagiscono regolarmente tra di loro nel contesto del loro lavoro, otteniamo la rete organizzativa o professionale, che svolge un ruolo chiave nel successo di un’azienda o di un’istituzione, ed è di grande interesse per la ricerca organizzativa.
• Collegando gli amici gli uni agli altri, otteniamo la rete di amicizia, che svolge un ruolo importante nella diffusione di idee, prodotti e abitudini ed è di grande interesse per la sociologia, il marketing e le scienze della salute.
• Collegando individui che hanno una relazione intima, otteniamo la rete sessuale, di grande interesse per l’epidemiologia per seguire la diffusione di malattie trasmesse sessualmente, come l’AIDS.
• Usando le registrazioni telefoniche ed e-mail per connettere le persone che si sono inviate tutte o e-mail l’una con l’altra, otteniamo la rete di conoscenze, catturando un misto di collegamenti professionali, di amicizia o intimi, importanti per le comunicazioni e il marketing.

Al fine di applicare la teoria della rete ad un sistema, è necessario quindi che considerazioni accurate precedano la nostra scelta di nodi e collegamenti, assicurando il loro significato al problema che desideriamo esplorare.

Degree, Average Degree e Degree Distribution

Una proprietà chiave di ciascun nodo è il suo degree, che rappresenta il numero di collegamenti che ha con altri nodi. Il degree può rappresentare il numero di contatti di telefonia mobile che un individuo ha nel grafico delle chiamate (cioè il numero di diversi individui con cui la persona ha parlato), o il numero di citazioni che un documento di ricerca inserisce nella rete di citazioni.

Una proprietà importante di una rete è il suo average degree. Nelle reti dirette, distinguiamo tra degree in entrata, che rappresenta il numero di collegamenti che puntano al nodo i, e degree in uscita, che rappresenta il numero di collegamenti che puntano dal nodo i ad altri nodi. Infine, il total degree di un nodo è dato dalla somma dei degree in entrata e i degree in uscita.

La degree distribution fornisce la probabilità che un nodo selezionato a caso nella rete abbia il degree k. La degree distribution ha assunto un ruolo centrale nella teoria delle reti in quanto il calcolo della maggior parte delle proprietà di rete richiede di conoscere il degree distribution, che determina molti fenomeni di rete, dalla robustezza della stessa alla diffusione dei virus.

Reti reali e bipartite, applicazioni in biologia e medicina

Nelle reti reali il numero di nodi (N) e collegamenti (L) può variare notevolmente. Per esempio, la rete neurale del verme C. elegans, l’unico sistema nervoso completamente mappato di un organismo vivente, ha N = 302 neuroni (nodi). Al contrario, si stima che il cervello umano abbia circa cento miliardi di neuroni (N ≈ 10¹¹). La rete genetica di una cellula umana ha circa 20.000 geni come nodi; il social network è composto da sette miliardi di individui (N ≈ 7 × 10⁹) e si stima che il WWW abbia oltre un trilione di documenti web (N> 10¹²).

Un l (o bigraph) è una rete i cui nodi possono essere divisi in due insiemi disgiunti U e V tali che ogni collegamento colleghi un nodo U a un nodo V. In altre parole, se coloriamo i nodi U verdi e i nodi V viola, allora ogni collegamento deve connettere nodi di colori diversi.

La medicina offre un esempio di spicco di rete bipartitica: The Human Disease Network collega le malattie ai geni le cui mutazioni sono note per causare la malattia corrispondente.  La Human Disease Network (o malattia) è una rete bipartita, i cui nodi sono malattie (U) e geni (V). Una malattia è collegata a un gene se è noto che le mutazioni in quel gene influenzano la data malattia. La seconda proiezione è la rete genica, i cui nodi sono geni e in cui due geni sono collegati se associati alla stessa malattia.

Percorsi e distanze

La distanza fisica gioca un ruolo chiave nel determinare le interazioni tra i componenti dei sistemi fisici. Ad esempio la distanza tra due atomi in un cristallo o tra due galassie nell’universo determina le forze che agiscono tra loro.

Nelle reti la distanza è un concetto stimolante. In effetti, qual è la distanza tra due pagine web o tra due individui che non si conoscono? Due pagine web potrebbero essere posizionate su computer ai lati opposti del globo, tuttavia sono collegati. Allo stesso tempo, due individui che vivono nello stesso edificio potrebbero non conoscersi.

Nelle reti la distanza fisica viene sostituita dalla lunghezza del percorso, che corre lungo i collegamenti della rete. La lunghezza del percorso rappresenta il numero di collegamenti che il percorso contiene.

Il percorso più breve tra i nodi i e j è il percorso con il minor numero di collegamenti. Il percorso più breve è spesso chiamato “distanza tra i nodi” i e j. Possiamo avere percorsi multipli più brevi della stessa lunghezza d tra una coppia di nodi. Il percorso più breve non contiene mai loop e non si interseca.

Nelle reti reali spesso è necessario determinare la distanza tra due nodi. In una piccola rete questo è un compito facile. In una rete con milioni di nodi, trovare il percorso più breve tra due nodi può richiedere molto tempo.

Connessione

La posta elettronica sarebbe piuttosto inutile se potessimo inviare e-mail solo a determinati indirizzi e non ad altri. Ciò significa che la rete dietro Internet deve essere in grado di stabilire un percorso tra due nodi qualsiasi. Questa è in effetti l’utilità chiave della maggior parte delle reti: assicurano una connessione.

In un nodo di rete indiretto i e j sono connessi se c’è un percorso tra di loro. Sono disconnessi se tale percorso non esiste, nel qual caso abbiamo la distanza tra i e j (dij) = ∞.

Una rete è connessa se tutte le coppie di nodi nella rete sono collegate. Una rete è disconnessa se c’è almeno una coppia con dij = ∞. I componenti di una rete disconnessa sono chiamati cluster o sottoreti. Un componente è un sottoinsieme di nodi in una rete, quindi esiste un percorso tra due nodi qualsiasi che appartengono al componente, ma non è possibile aggiungere altri nodi ad esso che abbiano la stessa proprietà.

Coefficiente di clustering

Il coefficiente di clustering (C) indica il grado in cui i vicini di un dato nodo si collegano l’un l’altro. C’è la probabilità che due vicini di un nodo si colleghino l’un l’altro. Di conseguenza C = 0,5 implica che esiste una probabilità del 50% che due vicini di un nodo siano collegati.

In breve, C misura la densità del collegamento locale della rete: più è densamente interconnesso il vicinato del nodo i, più alto è il suo coefficiente di clustering locale.

Molte delle reti che vengono studiate nella scienza delle reti consistono di migliaia o persino milioni di nodi e collegamenti. Per esplorarli, dobbiamo andare oltre i piccoli grafici. La rete di interazione proteine-proteine del lievito, per esempio, è troppo complessa per comprenderne le proprietà attraverso un’ispezione visiva del suo schema. Abbiamo quindi bisogno di ricorrere agli strumenti della scienza di rete per caratterizzare la sua topologia. Pertanto riguardo questo topic, è utile approfondire i vari tipi di reti aggiungendo, un tassello dopo l’altro, strumenti che aiutino a comprendere le loro caratteristiche topologiche.

Fonte: Barabasi A., Network Science. Chapter 2., Cambridge University Press (21 luglio 2016)