Teoria dei grafi e reti

Tutto è connesso — ma come?

Livello Base — linguaggio semplice, senza matematica

Supponi di voler far arrivare un messaggio a un famoso sconosciuto che non hai mai incontrato — un capo di Stato, una star del cinema. Lo dici a un amico, che lo dice a un suo amico, che lo dice a uno dei suoi. Quanti passaggi prima di raggiungere chiunque sul pianeta? Nel 1967 Stanley Milgram fece l'esperimento con lettere spedite e ottenne una risposta sorprendente: circa sei. Sei gradi di separazione, fra te e chiunque sia vivo.

È il potere silenzioso delle reti. Una rete — i matematici la chiamano grafo — non è altro che un insieme di nodi (le cose) uniti da archi (i collegamenti). Le tue amicizie sono un grafo. Lo sono le città collegate da strade, le pagine web cucite insieme da collegamenti ipertestuali, i neuroni intrecciati nel tuo cervello, le proteine che reagiscono dentro una cellula. Stesso scheletro, carne selvaggiamente diversa.

La grande sorpresa degli ultimi cinquant'anni è che queste reti del tutto diverse condividono la stessa architettura nascosta. Decifra quell'architettura e puoi prevedere come si diffonde un'epidemia, come un blackout dilaga in una rete elettrica, come un solo aeroporto chiuso ingarbuglia i viaggi globali, come una voce diventa virale. Nella simulazione qui sotto, guarda l'informazione propagarsi in una rete — e nota come un singolo hub ben collegato possa cambiare tutto.

Piccoli mondi, reti a invarianza di scala e i ponti di Eulero

Livello Studente — le equazioni principali

La teoria dei grafi nacque nel 1736, quando Leonhard Euler affrontò i ponti di Königsberg: potevi passeggiare per la città attraversando ciascuno dei suoi sette ponti esattamente una volta? Euler dimostrò che non potevi — e il suo ragionamento buttò via del tutto la mappa, tenendo solo ciò che collega a cosa. Una passeggiata del genere esiste precisamente quando il grafo ha 0 o 2 vertici di grado dispari, e nient'altro conta. Scartare la geometria e tenere la pura connettività fondò un intero ramo della matematica.

Un grafo \(G = (V, E)\) è solo un insieme di vertici \(V\) e archi \(E\). Il grado \(d(v)\) conta i vicini di un vertice, e la distribuzione dei gradi \(P(k)\) — la probabilità che un nodo a caso abbia \(k\) collegamenti — si rivela l'impronta digitale della rete. Sparpaglia archi a caso (il modello di Erdős–Rényi) e ottieni un'ordinata distribuzione di Poisson e una netta transizione di fase: supera \(p = 1/n\) e una componente connessa gigante scatta in essere. Ma le reti reali non somigliano affatto a quelle casuali. Sono piccoli mondi — strettamente aggregate eppure a pochi passi di distanza (Watts–Strogatz, 1998) — e a invarianza di scala, con una \(P(k) \sim k^{-\gamma}\) a coda pesante (Barabási–Albert, 1999) che emerge ogni volta che i nuovi arrivati preferiscono collegarsi ai già popolari.

Quella forma a invarianza di scala porta con sé un sorprendente doppio taglio. Queste reti sono robuste al guasto casuale — quasi ogni nodo è secondario, così un knockout casuale raramente tocca un hub — eppure fragili a un colpo mirato: rimuovi la manciata di hub più grandi e l'intera cosa si frantuma. È perché internet si scrolla di dosso i crash dei router ma teme un attacco coordinato, e perché vaccinare i pochi super-connettori ferma un'epidemia molto più efficacemente che vaccinare persone a caso.

Teoria spettrale dei grafi, camminate aleatorie ed epidemie di rete

Livello Esperto — profondità matematica completa

01Il laplaciano: una matrice che ricorda la forma

Riduci una rete a numeri e tutta la sua struttura vive nel laplaciano del grafo \(L = D - A\), costruito dalla matrice dei gradi \(D\) e dalla matrice di adiacenza \(A\). Diagonalizzalo e gli autovalori \(0 = \lambda_1 \le \lambda_2 \le \dots \le \lambda_n\) leggono la geometria della rete senza che tu la disegni mai. Il numero di autovalori nulli conta i pezzi connessi; i divari fra gli altri codificano colli di bottiglia, simmetrie e come il calore o una voce diffonderebbero nel grafo. La teoria spettrale dei grafi è la sorprendente affermazione che puoi davvero ascoltare la forma di una rete.

02Il valore di Fiedler: quanto connessa, davvero?

Il secondo autovalore \(\lambda_2\) — la connettività algebrica di Fiedler — è quello da tenere d'occhio. Sta appena sopra lo zero quando un grafo è a malapena tenuto insieme e sale man mano che il grafo si intreccia più stretto. La disuguaglianza di Cheeger rende esatta quell'intuizione, intrappolando il vero collo di bottiglia \(h(G)\) (il taglio più economico rispetto alla sua dimensione) fra due funzioni dello spettro: \(\dfrac{\lambda_2}{2} \le h(G) \le \sqrt{2\lambda_2}\). Un \(\lambda_2\) piccolo garantisce che esista un taglio rado; uno grande certifica che la rete non ha una cucitura debole lungo cui strapparsi.

03Clustering spettrale: trovare le comunità

Quello stesso autovettore di Fiedler si guadagna da vivere in pratica. Ordina i nodi per il segno della loro voce in esso e il grafo tende a dividersi lungo la sua cucitura più naturale — il cuore del clustering spettrale, l'algoritmo dietro gran parte del rilevamento moderno di comunità, della segmentazione di immagini e delle raccomandazioni. Ciò che sembra un astratto problema agli autovalori si rivela il modo più pulito che si conosca per chiedere: "quali parti di questa rete appartengono davvero insieme?"

04Camminate aleatorie, mescolamento e PageRank

Metti un gettone a vagare nel grafo, saltando a un vicino a caso a ogni passo — una camminata aleatoria con matrice di transizione \(P = D^{-1}A\). Si assesta in una distribuzione stazionaria \(\pi(v) = d(v)/2|E|\), puramente proporzionale al grado, e il tempo che le serve per dimenticare da dove è partita — il tempo di mescolamento — scala come \(\tau_{\text{mix}} \sim \log n / \lambda_2\): i grafi "expander" ben intrecciati si mescolano in un batter d'occhio, quelli con colli di bottiglia arrancano. Aggiungi una piccola possibilità di teletrasportarti ovunque e hai PageRank, la camminata aleatoria la cui distribuzione stazionaria Google usò per prima per classificare il web.

05Epidemie sulle reti: la soglia che svanisce

Fai girare un contagio SIR — suscettibile, infetto, guarito — su un grafo e compare una soglia netta: l'epidemia attecchisce solo quando \(\beta/\mu > 1/\lambda_{\max}(A)\), governata dal più grande autovalore della matrice di adiacenza. Qui la topologia a invarianza di scala tira fuori il suo trucco più cattivo. Per \(\gamma \le 3\), \(\lambda_{\max}\) cresce senza limite man mano che la rete cresce, così la soglia scivola fino a zero: su una grande rete a invarianza di scala un'epidemia si diffonde per quanto debole sia la trasmissione. È il motivo profondo per cui i virus informatici e la disinformazione online sono così ostinati — gli hub offrono loro un punto d'appoggio gratis.

06I problemi difficili nascosti nei grafi più semplici

Con tutta questa eleganza, alcune delle domande sui grafi dall'aria più semplice sono tra le più difficili conosciute. Chiedere se un grafo abbia un cammino hamiltoniano — un percorso che visita ogni nodo esattamente una volta — è NP-completo, e un algoritmo efficiente per esso rovescerebbe migliaia di altri problemi in un colpo e risolverebbe P contro NP, la domanda aperta più profonda dell'informatica. I grafi sono il punto in cui la connettività astratta sbatte contro il muro della difficoltà computazionale — che è la stanza accanto.