La Teoria delle Reti: dai ponti di Königsberg ai link del Web

di Fernanda Fischione su Informatica per le scienze umane, Teoria delle reti
”Solo recentemente l’uomo ha realizzato di vivere in un mondo reticolare. Internet e il World Wide Web stanno cambiando la vita di tutti. La nostra esistenza fisica è basata su varie tipologie di reti biologiche. Il termine ‘rete’ (network) è diventato una nozione centrale dei tempi che viviamo, e la conseguente esplosione di interesse nelle reti è da considerarsi un fenomeno sociale e culturale”
(S.N. Dorogovtsev e J.F.F. Mendes)

Il problema dei ponti di Königsberg: nascita della Teoria dei Grafi
Le prime riflessioni su quella che diventerà la Teoria delle Reti risalgono al 1736, anno in cui il matematico Eulero (1707-1783) stabilì l’impossibilità di risolvere il problema dei ponti di Königsberg, dando origine alla cosiddetta Teoria dei Grafi. La città –nota ai più per essere stata teatro della vita di Immanuel Kant- è attraversata dal fiume Pregel e dai suoi affluenti, e comprende due isolotti collegati tra di loro e alla terraferma tramite sette ponti (almeno fino al 1875, quando ne verrà aggiunto un ottavo). La leggenda narra che gli abitanti dell’attuale Kaliningrad si interrogassero sulla possibilità di escogitare un percorso che, partendo da una qualsiasi delle quattro zone principali in cui era divisa la città, consentisse loro di attraversare ciascun ponte una sola volta, tornando infine al punto di partenza. Eulero, facendo astrazione dai dati contingenti del problema, lo rappresentò attraverso una struttura matematica (un grafo, appunto) che consisteva in un insieme di vertici (o nodi) connessi tramite spigoli (o link). I nodi con un numero dispari di link - detti “nodi di grado dispari” - dovevano trovarsi all’inizio o alla fine del percorso, e un percorso che cominciasse in un punto e finisse in un altro non poteva avere più di due nodi con tale caratteristica. Tuttavia, il grafo di Königsberg risultava avere quattro nodi di grado dispari: dunque, il percorso ipotizzato si rivelava impossibile.

La Teoria delle Reti
La teoria inaugurata da Eulero è alla base dell’attuale Teoria delle Reti. Negli ultimi anni si è compreso, infatti, che sistemi anche molto diversi tra loro possono essere efficacemente descritti in termini di cosiddetti networks o reti complesse. Gli esempi vanno da reti tipo tecnologico, come Internet o il World Wide Web, a reti di tipo biologico, come reti metaboliche o proteiche, e perfino di tipo sociale, come ad esempio quelle che rappresentano le collaborazioni in ambito scientifico oppure la struttura delle grandi organizzazioni aziendali. Il comune denominatore è l’esistenza di proprietà topologiche complesse, in qualche modo intermedie tra quelle di sistemi completamente ordinati (reticoli) e quelle di sistemi completamente disordinati (reti random). Nell’ambito della ricerca sulle reti, è di grande interesse la possibilità di identificare le cosiddette comunità, ossia un insieme di nodi più strettamente connessi tra loro che con il resto della rete. Il concetto di comunità è molto diffuso, ed è intimamente connesso al problema della classificazione di oggetti in categorie, ad esempio a scopo mnemonico o di recupero di informazioni. Pensiamo ad esempio a Internet: identificare le comunità risulta cruciale per ideare motori di ricerca sempre più versatili, costruire algoritmi per il filtraggio automatico o la classificazione di documenti e dati. Pari è l’importanza dell’identificazione delle comunità in ambito biologico: qui la disponibilità di enormi moli di dati rende necessaria la realizzazione di efficienti motori per l’estrazione di informazioni rilevanti e per la comprensione di strutture “nascoste” nell’architettura biologica.

In un saggio recente, il fisico rumeno Albert-Laszlo Barabàsi (docente alla University of Notre Dame dell’Indiana, nonché uno dei maggiori propugnatori della Teoria delle Reti) porta l’attenzione sull’importanza dell’imparare a ripensare le reti. Barabàsi ripercorre le tappe essenziali nella storia della scienza delle reti, e definisce un particolare modello teorico, le reti a invarianza di scala, di cui mostra esempi significativi. Internet, il World Wide Web, la rete delle citazioni scientifiche, le presenze sul set degli attori di Hollywood e persino la diffusione dei virus hanno un’architettura comune, ovvero sono riconducibili ad un unico modello. Si tratta di reti dinamiche distribuite e in crescita, tenute insieme da una gerarchia di connettori, che formano una “ragnatela” autorganizzata.

Il World Wide Web ha effettivamente una sua struttura fisica, costituita dai computer che distribuiscono i dati immessi o richiesti dagli utenti della Rete. Sulla carta è possibile costruire una mappa di Internet, però si tratta una mappa necessariamente incompleta, e comunque irrimediabilmente superata nel momento stesso in cui viene completata. Perché il Web continua a espandersi, a contrarsi e, in ogni caso, a svilupparsi in modo spontaneo e non legato ad alcuno schema scientifico.
Barabàsi e il suo team hanno orientato le proprie ricerche alla descrizione della rete come se si trattasse di un fenomeno naturale. Dunque, da modelli di rappresentazione basati su grafici a “generazione casuale” - insufficienti - si è passati a quelli “a scala libera”, che considerano la grande rete di Internet identica a una piccola porzione di se stessa. Dunque, riuscendo a compilare una infinitesimale traccia dei collegamenti di una parte del Web, e ingrandendola in modo appropriato, si riesce a creare un grafico che possa rispondere con un certo grado di esattezza alle necessità di mappatura. «Una volta ottenuto questo risultato», commenta il suo lavoro il professor Barabàsi, «i modelli preparati non avranno solo un’utilità descrittiva, ma anche una notevole potenzialità predittiva di come è destinata a svilupparsi la rete».

La struttura frattale delle Reti
La descrizione del Web fornita da Barabàsi ricorda molto da vicino quella dei frattali operata dal matematico Benôit Mandelbrot nel 1975. Un frattale, infatti,
è un oggetto geometrico che si ripete nella sua struttura allo stesso modo su scale diverse, ovvero che non cambia aspetto anche se visto con una lente d’ingrandimento. Questa caratteristica è spesso chiamata auto-similarità (self-similarity). […] La natura produce molti esempi di forme simili ai frattali. Ad esempio, in un albero, ogni ramo è approssimativamente simile all’intero albero e ogni rametto è a sua volta simile al proprio ramo, e così via; è anche possibile notare fenomeni di auto-similiarità nella forma di una costa: con immagini riprese da satellite man mano sempre più grandi si può notare che la struttura generale di golfi più o meno dentellati mostra molte componenti che, se non identiche all’originale, gli assomigliano comunque molto. Secondo Mandelbrot, le relazioni fra frattali e natura sono più profonde di quanto si creda: «Si ritiene che in qualche modo i frattali abbiano delle corrispondenze con la struttura della mente umana, è per questo che la gente li trova così familiari. Questa familiarità è ancora un mistero e più si approfondisce l’argomento più il mistero aumenta». […] Una sostanziale differenza tra un oggetto geometrico euclideo ed un frattale è il modo in cui si costruisce. […] La costruzione dei frattali non si basa su di un’equazione, ma su un algoritmo. Ciò significa che si è in presenza di un metodo, non necessariamente numerico, che deve essere utilizzato per disegnare la curva.
[Dalla voce “Frattale” in Wikipedia (http://it.wikipedia.org/wiki/Frattale)]

La Teoria dei Piccoli Mondi: Watts, Strogatz, Erdős e Milgram
Dalla Teoria delle Reti si è generata successivamente una branca particolare di essa, chiamata Teoria dei Piccoli Mondi, la cui nascita può essere individuata nella comparsa nel 1998 sulla rivista Nature dell’articolo Collective dynamics of “smallworld” networks dei due matematici Duncan Watts e Steve Strogatz. Secondo tale teoria, elementi atomici di qualunque genere (persone, molecole, elaboratori elettronici ecc.) sono più o meno strettamente interconnessi a prescindere dalla distanza che li separa.
Gli antecedenti di questa teoria vanno fatti risalire al matematico Paul Erdős (1913-1996), che, studiando le caratteristiche dei grafi casuali (che si costruiscono aggiungendo archi a caso tra i nodi di un insieme dato, secondo una variabile gaussiana), dimostrò che basta aggiungere una piccola percentuale di archi rispetto al totale per ottenere un grafo connesso, e che il grado di separazione tra i grafi ottenuti è straordinariamente piccolo. Erdős, noto per essere un personaggio piuttosto eccentrico (ungherese di nascita, enfant prodige di famiglia ebraica, condusse un’esistenza vagabonda e frugalissima; era ossessionato dalla matematica, tanto che arrivò a fare regolare uso di anfetamine per riuscire ad affrontare sessioni di lavoro lunghe fino alle 18-19 ore quotidiane; scrisse una grandissima quantità di articoli matematici, molti dei quali sono frutto di collaborazioni coi colleghi, coerentemente con la visione “collettiva” e comunitaria della ricerca che lo scienziato promuoveva), rese il proprio stesso operare una rete a invarianza di scala: infatti, attribuì ai matematici che collaborarono con lui il numero 1 (noto oggi come “numero di Erdős 1”), mentre ad altri matematici che avessero collaborato con i primi venne dato il numero 2, e così via. Dai numeri di Erdős risultava un tipico esempio di grafo sociale delle conoscenze (o, in questo caso, delle collaborazioni scientifiche): affinché ci sia una conoscenza “indiretta” di tutte le persone del mondo, è sufficiente avere solo 24 conoscenze casuali. Tuttavia, questa prospettiva, pur essendo formulabile in via teorica, non è realistica, perché nel quotidiano si tende ad avere legami di conoscenza con persone geograficamente e socialmente vicine a noi. A questo proposito, la Teoria dei Piccoli Mondi ha una maggiore valenza descrittiva, ed è dunque più adatta di una teoria delle reti casuali a tracciare la ragnatela delle interazioni sociali.

Oltre alla figura di Paul Erdős, va ricordata quella del sociologo americano Stanley Milgram, che nel 1976 effettuò un interessante esperimento che confermò l’esistenza di reti sociali a invarianza di scala. Milgram selezionò casualmente un gruppo di americani del Midwest, ai quali chiese di mandare un pacchetto a uno sconosciuto che abitava nel Massachusetts. I partecipanti non conoscevano l’indirizzo preciso del destinatario, ma erano a conoscenza del suo nome, della sua occupazione e della sua zona di residenza. Venne chiesto loro di inviare il pacchetto ad un conoscente che, a loro giudizio, avesse il maggior numero di possibilità di conoscere il destinatario finale; la stessa cosa avrebbe dovuto fare chi ricevesse il pacco, fino ad arrivare al destinatario ultimo. Ci vollero solo tra i cinque ai sette passaggi per far giungere il pacchetto a destinazione. Da qui fu coniata l’espressione topica “sei gradi di separazione”, proprio ad indicare che sono sufficienti sei soli passaggi per connettere tra di loro elementi anche lontanissimi.

La ricerca venne ripetuta nel 2001 da Duncan Watts (docente alla Columbia University e, come accennato, ideatore della Teoria dei Piccoli Mondi), che si servì questa volta di Internet, utilizzando messaggi e-mail anziché pacchi postali. I risultati dell’esperimento effettuato più di vent’anni prima da Milgram vennero confermati, nonostante Watts avesse lavorato con una mole di dati statistici nettamente superiore rispetto a quella presa in considerazione dal sociologo: i gradi di separazione tra un soggetto e l’altro della ricerca restavano effettivamente sei.

Con l’avvento dell’informatizzazione di massa, la teoria dei sei gradi di separazione è stata applicata ad aree diverse da quella sociologica (per cui era stata originariamente pensata): nuovi campi d’applicazione sono l’analisi delle reti informatiche ed elettriche, la trasmissione delle malattie, la teoria dei grafi, le telecomunicazioni ecc.

Struttura topologica del Web
Il Web è caratterizzato dalla presenza di connettori (hub); la struttura dei nodi è tutt’altro che egualitaria, ed assume una topologia paragonabile a quella di una rete del traffico aereo. A differenza di una rete stradale, i cui nodi hanno un analogo numero di link, la rete del traffico aereo presenta una topologia in cui quasi tutti i nodi hanno pochi link, e pochissimi nodi (detti appunto connettori, hub) ne hanno moltissimi.

Dal punto di vista topologico, il Web è una rete orientata, costituita da una struttura formata da quattro continenti. Questi sono:

• L’area centrale (Central Core), in cui ogni nodo è raggiungibile da ogni altro nodo (sono i siti più frequentati, come i motori di ricerca, siti di notizie, portali, ecc.);
• Il continente IN (IN Continent), i cui nodi portano verso il Central Core, ma non permettono di tornare indietro (sono i siti personali che rimandano coi link ai siti più frequentati, ma non hanno link da questi ultimi verso di loro);
• Il continente OUT (OUT Continent), che è raggiungibile dal Central Core ma dal quale non si può uscire (si tratta, per esempio, dei siti aziendali, che vengono linkati dagli hubs ma non permettono di tornare indietro);
• Alcuni nodi (nell’area Tubes) connessi solo al continente IN o a quello OUT, oltre a viticci (Tendrils) e le isole (Islands) di nodi connessi solo tra loro o parzialmente con gli altri continenti IN e OUT, che costituiscono il quarto continente, quello meno frequentato e più inaccessibile.

[Tratto da: Teresa Numerico, Memorizzazione e ricerca nel mondo digitale, in Informatica per le Scienze Umanistiche, Teresa Numerico, Arturo Vespignani (a cura di); Il Mulino, Bologna, 2003.]

Come sappiamo dalla Teoria dei Piccoli Mondi, al crescere del numero dei nodi della rete, il grado di separazione tra essi, ovvero il numero di passaggi necessari a unire due nodi qualsiasi, aumenta in misura molto ridotta (la crescita segue una funzione logaritmica).
Quando i link della rete non sono bidirezionali ma diretti, solo una parte limitata della rete è esplorabile. Per quanto riguarda il Web, recenti studi hanno stimato che soltanto il 30% di esso è navigabile. Questa caratteristica del Web è una sua proprietà topologica; ciò significa che l’esistenza di un percorso è indipendente dalle capacità dell’uomo e dei migliori motori di ricerca, esistenti o possibili (assunto che richiama direttamente quanto dimostrato da Eulero sui grafi e successivamente concettualizzato da Barabàsi: «nella loro architettura, i grafi o le reti nascondono proprietà che possono limitare o favorire ciò che possiamo fare con loro»).

Riferimenti bibliografici:
- F. Radicchi, C. Castellano, F. Cecconi, V. Loreto e D. Parisi
PNAS, early electronic edition 23rd February 2004 (http://www.pnas.org/papbyrecent.shtml); printed version 2nd March 2004
- Voci di Wikipedia (www.wikipedia.org) per le informazioni su: problema dei ponti di Königsberg, Teoria dei Grafi, Teoria dei Piccoli Mondi, frattali, Paul Erdős, teoria dei sei gradi di separazione.
- F. Di Donato, I Ponti di Königsberg e l’Architettura delle reti, 2005
- B. Paltrinieri, Punti di Contatto, articolo tratto da Quark
- Nodi, link e server: ecco come è fatta Internet, articolo de Il Corriere della Sera, 8 ottobre 2002
- T. Numerico, A. Vespignani (a cura di), Informatica per le Scienze Umanistiche, Il Mulino, Bologna, 2003

Fonte: Fernanda Fischione su Informatica per le scienze umane