Le sfide di Eulero e di Pareto: Internet, Teoria dei Grafi e distribuzione Power Law

di |

Mondo



di Alessio Brugnoli

Consulente Key Partners

Da almeno vent¿anni, pi&#249 generazioni di ricercatori hanno provato a verificare l¿applicabilit&#224 di teoremi, congetture e lemmi della Teoria del Caos ad Internet. Inizialmente tali analisi, prendendo spunto dalla idee di Benoit Mandelbrot e di Murad S. Taqqu, erano limitate allo sviluppo di modelli di previsione e di aggregazione del traffico dati, al fine di ottimizzare il dimensionamento delle infrastrutture di rete. Esigenza che, con l¿evoluzione della tecnologia e la diminuzione dei costi di investimento, sta diventando di fatto meno pressante.

L¿interesse della ricerca applicata si sta pertanto concentrando su un altro argomento: lo studio delle regole utilizzate dalla Rete delle Reti per sviluppare e modificare la sua topografia. Fenomeno simile al micelio di un fungo. Si tratta di studi, a prima vista pi&#249 astratti dei procedenti, eppure di enorme impatto pratico, finalizzati,ad esempio, alla comprensione dei meccanismi di congestione della rete, alla diffusione dei virus informatici o ancora all¿elaborazione di algoritmi pi&#249 efficaci per la ricerca dell¿informazione.

Prima di addentrarsi nella trattazione &#232 necessario chiarire un concetto: l¿infrastruttura fisica, costituita da routers, link ed altri apparati di rete, non deve essere confusa con quella logica, ovvero con i servizi che appaiono all¿utente quando naviga per il Cyber Spazio, siti, blog, mailing list. Le strutture di entrambi i layer, pur sviluppandosi con regole simili, presentano una sostanziale differenza: a livello fisico le reti saranno di tipo funzionale, a livello logico di tipo sociale.

Per comprendere meglio i modelli proposti &#232 necessario introdurre i concetti di:

  • lunghezza media di un cammino, la media aritmetica tra le distanze esistenti tra coppie di nodi, dove la distanza consiste nel numero di rami del cammino pi&#249 breve che li connette;

  • il livello di clustering, che quantifica il livello di interconnessione esistente tra i nodi presenti. Un valore 0 implica come non esista nessuna connessione, mentre un valore 1 indica una topologia a maglia completa della rete;

  • il grado, il numero di rami che si attestano su un nodo.

Per il layer fisico, il problema &#232 immediato: dato un insieme di N nodi, i routers, &#232 necessario individuare una modalit&#224 per connetterli tra loro. Dato lo sviluppo non pianificato di Internet, si pu&#242 ipotizzare come tale connessioni siano casuali. Inoltre, per ovvi motivi di costo, non genereranno una maglia completa. Ossia il numero dei rami presenti tra i nodi dovr&#224 essere di gran lunga minore della quantit&#224 che si avrebbe nel caso che tutti gli N nodi fossero interconnnessi tra loro, valore espresso dalla formula.

Il primo modello utilizzato per descrivere e simulare le regole di sviluppo dell¿infrastruttura fisica sui si basa Internet fu implementato basandosi sulle ricerche di due matematici ungheresi: Paul Erd&#246s and Alfred R&#233nyi. Senza ricorrere ad eccessivi formalismi matematici, l¿ipotesi di base era che la probabilit&#224 che due nodi fossero connessi seguisse una distribuzione di tipo poissoniano.

La rete descritta da tale tipologia di grafo pu&#242 scherzosamente essere definita “democratica”. I suoi nodi godono infatti delle seguenti propriet&#224:

  • il grado di un singolo nodo &#232 una costante. In termini pratici, ogni router ha un uguale numero di link;

  • ogni nodo &#232 indistinguibile dagli altri.

Un modello semplice ed efficace, con un unico e sottile difetto: le sue propriet&#224 contrastano con quanto suggerito dall¿esperienza empirica di chi progetta, sviluppa e gestisce quotidianamente reti dati.

Nel 1999, i tre fratelli Faloutsos si dedicarono ad analizzare i dati raccolti in “Internet Mapping Project” di William R. Cheswick, Hal Burch e Steve Branigan dei Bell Lab, ovvero i diagrammi, le cosiddette mappe, che rappresentano i diversi percorsi dai pacchetti tra un terminale utente e un generico host Internet, ottenute tramite un utilizzo massivo del trace route.

Le conclusioni furono che la probabilit&#224 di connessione tra due nodi della rete Internet seguisse una distribuzione di tipo Power Law il cui andamento &#232 evidenziato, al variare dell¿esponente, in questo grafico.

In particolare, il valore dell¿esponente &#232 stato stimato pari a 2.5. Tale fatto, che riguarda astratte formule matematiche, a prima vista pu&#242 lasciare indifferenti, ma ad un¿analisi pi&#249 approfondita permette di spiegare logicamente diverse propriet&#224 del Cyber Spazio.

La prima propriet&#224 di una distribuzione Power Law &#232 facilmente identificabile dal grafico. Incrementando il valore dell¿esponente a , diminuisce l¿estensione della coda delle distribuzione favorendo una aggregazione dei suoi valori intorno al valore 1; in particolare, se l¿esponente tender&#224 all¿infinito, tale distribuzione degenerer&#224 in un impulso di Dirac. L¿esponente a permette una valutazione della dispersione dei valori della distribuzione.

Mentre nella distribuzione poissoniana, per ogni nodo il numero dei rami che vi si attestano &#232 pressoch&#233 costante, in una Power Law vi sono soltanto pochi nodi con molti rami; sulla quasi totalit&#224 dei router si attestano pochi link. Tale propriet&#224, per chi applica il modello gerarchico di rete IP, con la sua divisione in tre livelli (Access, Distribution, Core), risulta modellare meglio la realt&#224 empirica. Nell¿immagine seguente &#232 evidenziato un grafo random generato con distribuzione Power Law.

Altra propriet&#224, deducibile dalla formula della distribuzione, riguarda il principio per cui i momenti di ordine N assumano valore infinito per N > a . Ad esempio, se a < 2 la varianza sar&#224 infinita, mentre, con a < 1, risulter&#224 essere infinito il valore atteso. Negli studi per la modellizzazione delle sorgenti dati, la varianza infinita rendeva inutilizzabile per la loro aggregazione il teorema del limite centrale. Per ovviare a tale difficolt&#224 &#232 stata sviluppata un¿enunciazione pi&#249 generale, che sostituisce alla funzione gaussiana un¿alfa stabile.

Se tale parametro assume valori prossimi o inferiori ad 1, il sistema gode dalla propriet&#224 LRD (Long Range Dipendence), ossia per essere sintetici, dell¿equivalente dell¿effetto farfalla nella dinamica non lineare: piccole variazioni delle propriet&#224 di un elemento appartenente ad un sistema vengono amplificate dalle sue non linearit&#224 sino ad alterarne lo stato globale.

Seppur anche questa propriet&#224 potrebbe apparire poco immediata, &#232 tuttavia interessante osservare come pu&#242 influenzare il routing dinamico di una rete, nonostante i vari meccanismi di salvaguardia, il down o la congestione di un link preferenziale nell¿inoltro dei pacchetti.

Connessa alla procedente, &#232 la propriet&#224 di autosomiglianza o di scale free, definibile come la propriet&#224 del sistema di avere un comportamento indipendente dall¿intervallo di osservazione. Nel nostro caso, le caratteristiche topologiche di una rete non sono influenzate dal numero di router che ne fanno parte. In battuta, si pu&#242 affermare che questa &#232 la dimostrazione logica dell¿utilit&#224 degli ambienti di test.

E proprio la propriet&#224 scale free garantisce la robustezza di Internet a guasti casuali. Reuven Cohen dell”Universit&#224 di Bar-Ilan (Israele) e Duncan Callaway della Cornell University hanno dimostrato matematicamente che la frazione critica, ossia la percentuale di router che si devono guastare affinch&#233 la funzionalit&#224 della rete sia completamente compromessa, &#232 pari ad 80% per Power Law con esponente a < 3.

Tuttavia, proprio per le caratteristiche che la rendono intrinsecamente gerarchica, a sua volta tale rete risulta essere particolarmente sensibile ad attacchi mirati all¿eliminazione degli hub, i pochi nodi con elevato numero di connessioni. Da un certo punto di vista, chi ide&#242 Arpanet non ha pienamente raggiunto i suoi scopi.

Recentemente, Romualdo Pastor-Satorras dell¿ Universitat Politecnica de Catalunya in Barcelona e Alessandro Vespigniani del Centro internazionale di fisica teorica di Trieste hanno evidenziato inoltre come l¿esistenza della propriet&#224 scale free favorisca la diffusione dei virus informatici.

Per decadi, nello studio della propagazione dei virus informatici si &#232 utilizzato un approccio epidemiologico, ossia ispirato alla propagazione delle epidemie nell¿Uomo. In Natura, quando si immunizza una certa frazione della popolazione, l¿incidenza di una malattia cala bruscamente: la popolazione del virus scende al di sotto della soglia epidemica, favorendo il debellamento della malattia.

Tale assunto si &#232 dimostrato inefficace nel caso informatico, caratterizzato infatti dall¿estrema longevit&#224 delle infezioni. Pastor-Satorras e Vespigniani hanno dimostrato che per reti scale free, la soglia epidemica &#232 pari a 0. In termini pratici, per quanto possa essere pervasiva la diffusione degli antivirus, il virus informativo riesce tuttavia a sopravvivere in uno stato endemico infettando un piccolo numero di nodi poco connessi. Non solo, esiste anche la possibilit&#224 che da qui il virus si propaghi a tutto il sistema.

A titolo di curiosit&#224 &#232 interessante sottolineare che un meccanismo analogo &#232 stato riscontrato nella diffusione delle malattie sessuali, come l¿AIDS.

Altra propriet&#224 dei grafi random associati a Power Law &#232 la loro struttura a Small World, caratterizzata dalle seguenti propriet&#224:

  • la lunghezza media di un cammino dipende logaritmicamente dal numero di nodi: al loro aumentare, il suo valore cresce lentamente;

  • icoefficiente di clustering assume valore 0 per valori di N tendenti all¿infinito.

Le ricerche compiute nei laboratori IBM hanno inoltre verificato che la rete Internet risponde pienamente a tali propriet&#224. In particolare:

  • la lunghezza media di un cammino cresce secondo la formula d = 0.35 + 2.06 log(N). Attualmente il valore di d stimato &#232 pari a 9, ossia per connettere due generici host sono necessari in media 9 hope;

  • il coefficiente di clustering decresce secondo la formula C » N0.75

Una spiegazione empirica di questa organizzazione “aristocratica” &#232 legata alla struttura stessa di Internet, connessione tra reti di diverso tipo e natura, tutte utilizzanti i protocolli appartenenti alla suite TCP/IP.

Fino a questo punto, sono state sottoposte a verifica le propriet&#224 statiche di Internet. La rete delle reti, per&#242, &#232 in continua evoluzione: ad ogni istante si aggiungono nuovi link che ne alterano la topologia. Alla luce di tale dinamismo, &#232 possibile creare dei modelli di simulazione che rispettino le propriet&#224 legate alla distribuzione Power Law, ossia un¿organizzazione a Small World in cui si riscontri la tendenza di un nodo a connettersi a quelli gi&#224 presenti e caratterizzati da un altro numero di link?

Allo stato dell¿arte, esistono due differenti modelli che, tra loro differenti per le premesse teoriche, implementati conducono ai medesimi risultati. Il primo, elaborato nell¿Universit&#224 di Notre Dame da Albert-L&#225szl&#243 Barab&#225si e da Ginestra Bianconi &#232 basato sull¿utilizzo degli stessi principi su cui si basa il modello di condensazione di Bose-Einstein.

Il secondo, sviluppato nell¿Universit&#224 La Sapienza da Caldarelli, Marchetti e Petronero &#232 basato sull¿utilizzo degli Alberi di Cayley, a cui sono riconducibili gli algoritmi di River Wind che descrivono l¿evoluzione dei bacini fluviali. Nell¿immagine sottostante &#232 evidenziata l¿evoluzione di una rete, basata su algoritmi dipendenti dai due modelli.

Parallelamente alle ricerche sull¿infrastruttura di rete, si sono svolte analisi sui link esistenti nel World Wide Web. Sinteticamente le conclusioni sono le seguenti:

  • la distribuzione dei link &#232 anch¿essa di tipo Power Law con a pari a 2.1;

  • la lunghezza media di un cammino &#232 stata valutata da alcuni ricercatori pari a 19. Secondo altri studi, tale valore &#232 di poco inferiore a 6, rispettando cos&#236 le previsioni di Stanley Milgram. Tale disparit&#224 &#232 legata alle diverse definizioni che sono state date alla lunghezza media di cammino. La definizione standard non pu&#242 essere applicata, in questo contesto, dato che la presenza di un link tra il sito A e un sito B non implica necessariamente che ne esista un altro tra B ed A;

  • l¿inadeguatezza degli algoritmi che descrivono l¿evoluzione del layer fisico. Attualmente, il modello pi&#249 preciso per modellizzare la crescita del World Wide Web &#232 quello Multilayer, sviluppato nell¿Universit&#224 La Sapienza da Debora Donato, Luigi Laura, Stefano Donati e Stefano Millozzi;

  • La predominanza di link diretti rispetto ai bidirezionali, che, a differenza dell¿infrastruttura fisica, modellizza il World Wide Web come un grafo orientato, limitandone la porzione esplorabile a circa il 40% del totale. Tale vincolo &#232 topologico, indipendente dallle capacit&#224 dell¿uomo e dei migliori motori di ricerca, esistenti o possibili;

  • La possibilit&#224 di applicare al World Wide Web le tesi di Maturana, Morin e Schwartz,descrivendolo come un sistema dotato delle propriet&#224 di autopoiesi e di self organization;

Relativamente ai blog, fenomeno in costante crescita, non sono state ancora compiute ricerche sulla distribuzione statistica dei link. Pertanto, a priori, non si pu&#242 affermare la validit&#224 della distribuzione Power Law, poich&#233, dai dati ottenuti applicando le tecniche del Social Networking, la lunghezza media di un cammino &#232 stata stimata di poco maggiore di 2 e il coefficiente di clustering pari al 30%. La bloggosfera sembra quindi avere una struttura flat, rispetto a quella a Small World.

I sociologi ipotizzano che tale differenza sia legata a due opposti meccanismi di attribuzione dell¿autorevolezza: nel caso di un sito &#232 di tipo top-down, ovvero legato alla conoscenza e al valore attribuito al brand del titolare. Nei blog, invece, il meccanismo si lega ai contenuti che vi sono presenti.

Dai giorni in cui Eulero, padre della Teoria dei Grafi, discuteva di K&#246nigsberg o in cui Pareto rifletteva sulla Curva del Reddito, di acqua ne &#232 passata sotto i ponti.

Teorie matematiche hanno trovato nuovi ambiti applicativi. Ci&#242 che sembrava un puro ed inutile gioco intellettuale addirittura &#232 diventato la chiave interpretativa dello sviluppo di uno dei simboli della contemporaneit&#224.

A fronte di una tale evoluzione, &#232 oltremodo interessante passare dall¿interpretazione teorica all¿azione. I concetti espressi possono essere interessanti, ma se non vengono applicati alla realt&#224 quotidiana, aiutando a migliorare le prestazioni dei motori di ricerca, i meccanismi di gestione della congestione della rete o di monitoraggio delle crisi informatiche, rimangono dei meri formalismi e quindi concretamente inutili.

Tale constatazione si lega al problema, drammatico e ricorrente per l¿Italia, del mancato dialogo tra Universit&#224 e Azienda; due realt&#224 parallele, che si confrontano con le stesse sfide intellettuali, senza conoscersi e confrontarsi, rischiando mille volte di reinventare la ruota e di perdere importanti e strategiche opportunità di innovazione, crescita e progresso.

© 2005 Key4biz.it