SISTEMI COMPLESSI E RETI A INVIARIANZA DI SCALA

Perché su Google io sono primo e tu no? Nel 2001 tutto quello che c'era da sapere sulle regole del Web lo ha spiegato in un "semplice" paper dal titolo "Competition and multiscaling in evolving networks" una allieva di Albert-László Barabási, ora professoressa alla Queen Mary University of London: l'italiana Ginestra Bianconi.

Tratto da un articolo dell'autore del 3 febbraio 2007 

Per più di 40 anni la scienza si è interrogata sul perché certi sistemi complessi (tra cui alcune reti e Internet) non fossero governati dalla casualità.



Dal 1959, da quando due matematici ungheresi, l’inimitabile Paul Erdős e il suo collaboratore Alfréd Rényi iniziarono a studiare il comportamento delle reti in comunicazione e nelle scienze biologiche, è passata molta acqua sotto i ponti. Essi suggerirono, con convincenti calcoli, che i sistemi complessi si comportavano in maniera del tutto aleatoria [1] [2].

Quarant’anni dopo, nel 1999, il fisico Albert-László Barabási (foto) e i suoi collaboratori Reka Albert e Hawoong Jeon si accorsero non solo che non tutte le reti si comportavano come sistemi casuali [3] [4]: anzi, erano molti gli esempi di reti che presentavano un comportamento altamente organizzato: una di queste era proprio Internet e il World Wide Web.

Da sinistra: Alex Vespignani, Claudio Pasqua, Albert-László Barabási

Teniamo presente che gli strumenti che prima di tali studi venivano utilizzati per spiegare il comportamento di Internet si basavano su idee mutuate dall’analisi sul comportamento di sistemi privi di organizzazione.
Gli attuali protocolli sono stati sviluppati negli anni Settanta, quando la rete era piccola, sfruttando le tecnologie disponibili allora.
L’importanza di conoscere la topologia della rete e dei suoi attributi è legata dunque alla necessità di abbattere le limitazioni intrinseche al modello: senza tali conoscenze non si possono ad esempio progettare nuovi strumenti e nuovi servizi.

Da cui l’importanza di introdurre nuovi modelli che spieghino con maggiore raffinatezza le caratteristiche di questi sistemi.

I sistemi complessi come internet non possono essere spiegati come una semplice connessione tra hub, così come un organismo vivente non può venire descritto solo come una riduzione alle sue particelle elementari (le cellule) e alle leggi fondamentali della chimica.

Un ecosistema digitale, così come un ecosistema biologico o sociale, è sufficientemente “reale” al pari delle sue parti costituenti: del che ci accorgiamo con disagio quando, ad esempio, l’ecosistema viene perturbato da inquinamenti o virus, oppure quando si presenta con tanti problemi irrisolti.

Ecco così che si rendeva necessario uno studio più olistico, che tenesse conto dell’estrema complessità delle relazioni tra le parti.

Nell’esperimento che consisteva nella mappatura di una piccola porzione del World Wide Web il gruppo di Barabasi si accorse che l’80 percento delle pagine possedevano non più di quattro link entranti, ma una piccola minoranza (meno dello 0,01 percento di tutti i nodi) ne avevano più di mille, e pochissimi anche milioni!

Conteggiando quante pagine web avevano esattamente k link dimostrò che la distribuzione invece di diminuire con velocità esponenziale, diminuiva con una legge di potenza: la probabilità che un nodo sia connesso a k altri nodi era proporzionale a 1/kⁿ

Il valore della potenza n per i link entranti risultava essere 2,2, valore sperimentalmente e intrinsecamente legato alla struttura del WWW.

In termini algebrici era come dire che ogni volta che il numero di collegamenti in entrata diminuiva di un fattore 10, il numero di pagine che avevano quel numero di collegamenti aumentava, mediamente, di un fattore 10 elevato alla potenza di 2,2. Un numero che è circa uguale a 158. Per dirla in altre parole, significa che le pagine con un numero di collegamenti dieci volte maggiore erano 158 volte meno probabili.

Un comportamento simile da parte di un sistema complesso fa normalmente brillare gli occhi di un fisico perché quando un sistema è retto da una legge di questo tipo significa che il sistema si sta autoorganizzando. [5]

Questi fenomeni si ritrovano di solito nei sistemi in transizione di fase, e accadono quando un sistema si trova ad esempio sull’orlo di un baratro, in bilico tra l’ordine e il caos. Si riconoscono ad esempio nei frattali, quando una parte arbitrariamente piccola riproduce il tutto. Emergono anche nella spiegazione del modo in cui si diffondono le epidemie, nelle statistiche dei fenomeni naturali (terremoti, tsunami), tutti casi in cui il valore medio di una curva gaussiana non può spiegare adeguatamente la distribuzione generale.

In una prima, forte approssimazione, il Web è un esempio di come questo curioso andamento spieghi l’accrescere dei nodi di grandi hub, che diventano sempre più connessi a discapito della maggior parte dei nodi meno connessi.
Infatti nel Web esistono molti pagien che hanno pochi link in entrata, e pochi pagine che hanno invece un elevato numero di collegamenti.

Nel modello a invarianza di scala l’età dei nodi è il fattore più importante e con l’ingresso di nuove pagine gli hub più più popolari hanno maggiori probabilità di essere linkati, accrescendo ulteriormente la loro connettività, un fenomeno che comunemente è conosciuto con il nome di collegamento preferenziale (preferential attachment)

Ma questo modello non è sufficiente a spiegare perché alcuni nodi o website, entrati più recentemente in competizione, riescano in breve tempo a diventare più popolari di altri.


L’EQUAZIONE ALLOMETRICA DEL WEB

Il grado con cui i nodi di una rete accrescono la loro connettività dipende dal loro grado di competere per accaparrarsi link.

In biologia è nota da molto tempo una relazione che viene chiamata equazione allometrica che indica proprio la competizione tra le parti. Tale equazione può essere applicata in un ampio spettro di campi: la morfologia, la biochimica, la fisiologia o la filogenetica. Essa spiega che una certa caratteristica Q₁ possa essere espressa come una potenza che è funzione di un’altra caratteristica Q₂.
In morfogenesi ad esempio, la grandezza di un certo organo (ad esempio il cervello di un essere vivente) è in generale una funzione allometrica della dimensione del peso complessivo dell’organismo in questione.

L’equazione stabilisce i ritmi dell’accrescimento relativo tra le parti, le quali stanno in una proporzione costante durante tutta la vita dell’organismo, oppure durante un ciclo vitale per il quale sia valida l’equazione allometrica. E’ sorprendente come, nonostante l’estrema complessità dell’intero processo di accrescimento di un organismo, tutto sia regolato da una equazione algebrica così semplice.

In questo caso la capacità dell’organo di prendersi la propria quota è indicata da un coefficiente di ripartizione α.

Se α₁> α₂ e cioè se l’intensità di accrescimento di Q₁ è superiore a quella di Q₂ allora α=α₁/α₂ >1; l’organo cattura allora una quota maggiore di quella relativa alle altre parti; esso pertanto cresce più rapidamente di queste, ovvero cresce con allometria più positiva.

In sociologia, l’equazione di cui stiamo parlando è la cosiddetta legge di Pareto (1897) sulla distribuzione della ricchezza del reddito di una nazione, per cui Q₁=bQ₂^a, con Q₁= numero degli individui che guadagnano un certo reddito, Q₂ ammontare del reddito e b ed a due costanti.

La distribuzione del reddito di una nazione copre molti ordini di grandezza, dai redditi annuali vicini allo zero dei senzatetto fino ai miliardi di dollari che Bill Gates incassa soli di interessi.

Distribuzioni di questo tipo sono definite anche come scale-free (prive di scala o a invarianza di scala), intendendo con questo che esse non sono dominate da un’unica scala rappresentativa.

Il World Wide Web è appunto una di queste.


RETI IN EVOLUZIONE CONTINUA

Uno dei limiti dei modelli tradizionali della scienza che studia i grafi e le reti è che tiene conto del fatto che il numero dei nodi di una rete sia fissa.

Ma il web non è statico: ogni giorno pagine nuove vengono connesse, nuovi router attivati, dei collegamento vengono aggiunti ma altri vengono persi. Altri infine sono modificati e qualche vecchia pagina muore.

Ginestra Bianconi 

Così il nuovo parametro "fitness", e introdotto per la prima volta dalla scienziata italiana Ginestra Bianconi, tiene proprio conto di questo comportamento: tiene conto della competizione tra i nodi.

Google è la dimostrazione più evidente di questa possibilità, della possibilità che l’ultimo arrivato, ma con una buona prestanza nell’accaparrarsi link, possa contrastare il comportamento dettato dal modello a invarianza di scala, secondo il quale chi arriva per primo è in vantaggio.

Nel modello che i fisici Bianconi e Barabasi chiamano “modello a fitness” [6] i nodi hanno diversi valori di prestazione e conquistano in maniera diversa la propria connettività.

La probabilità P_i (k_i) che un nuovo nodo sia connesso a k_i link viene così modificato da un nuovo parametro η

P_i (k_i) = η_i k_i / Σ_j η_j k_j.

La competizione generata dai diversi valori di fitness causa una evoluzione diversa nel tempo delle connettività dei nodi

Quindi, la connettività di ogni nodo è dato da k_i (t) ~= t^ß(η), dove l’esponente ß(η) cresce con il crescere di η.

Il risultato è che nodi entrati in competizione recentemente (ma con grande η) possono acquisire nuovi link a velocità maggiore rispetto a nodi entrati da più tempo in competizione ma con minore fitness.

Dire che un link ha la probabilità di avere un peso più alto di un altro dipende dal modello che consideriamo.

Molti sono i meccanismi che possono esserne implicati. Meccanismi come la legge di potenza, il preferential attachment, tipici di una rete a invarianza di scala, non sono più sufficienti (studi recenti lo confermano) a spiegare fenomeni come i link interni, il ricablaggio, la rimozione di nodi e link, l’invecchiamento, gli effetti non lineari e molti altri processi relativi alla tipologia delle reti che sono sotto studio solo da alcuni anni.

La risposta è tutta nel modo in cui nuovi hub (es. Google, YouTube) hanno avuto successo nonostante si siano inseriti relativamente tardi nel panorama interrnet, quando altri come Yahoo e Altavista erano già dei colossi.

Alcuni hub adottatarono strategie basate su ecosistemi digitali sperimentali al tempo in cui vennero utlizzati per la prima volta. Quando Google è stata fondata nel 1997 nessuno nell’ambiente scientifico era a conoscenz, ad esempio, che il World Wide Web seguisse comportamenti a invarianza di scala.
Quando il modello a invarianza di scala fu coniato da Barabási e diventò il punto di riferimento, alcuni anni dopo (2000) si è poi iniziato a comprendere che il modello di per sé pur valido, non poteva ancora spiegare tutti i fenomeni del comportamento del WWW.

Una sua evoluzione, il modello a fitness di Barabási e Bianconi, rimane ad oggi il modello più accreditato.

In sintesi hub come Google tentano di avvantaggiarsi rispetto alla concorrenza creando i presupposti per sfruttare quelle non linearità nel modello a invarianza di scala, Ciò consente a hub meno recenti di avvantaggiarsi contrastando la regola del “preferential attachment”

Lawrence Page e Sergey Brin idearono e brevettarono un metodo matematico originale per il calcolo della link popularity di una pagina o di un sito web: il PageRank [7]

Cito qui i 5 fattori più importanti che influenzano il calcolo della link popularity di un nodo descritti proprio da Lawrence Page:

1. Visibilità di un Link
2. Posizione di un Link all’interno di un documento
3. Distanza di tra le pagine
4. Importanza di una pagina linkata
5. Aggiornamento di una pagina linkata
6. Invecchiamento in realtà questo non lo ha detto Page ma è uno studio che ho descritto qui [9]

Una caratteristica non spiegata dal modello di rete a invarianza di scala è che quando aggiungo alla mia pagina Web un link verso, ad esempio, una pagina di questa rivista, creo un link interno fra due nodi vecchi.

Luis Amaral e Gene Anely della Boston University [8] e due studenti hanno dimostrato proprio questo: che i nodi, invecchiando, perdono gradualmente la loro capacità di annettersi dei link.
I due studenti del gruppo (Mendes e Dorogovtsev) hanno dimostrato poi che l’invecchiamento non distrugge le leggi di potenza, ma altera semplicemente il numero di hub perché cambia il loro esponente in grado.

Cioè come dire che la regola del collegamento preferenziale (preferential attachment) segue un meccanismo più complesso: la probabilità che un nuovo nodo si colleghi a uno già esistente non dipende unicamente dal numero di link ma anche dall’aggiornamento e dalla distanza tra le pagine.

Ecco perché ad esempio metodi di calcolo come il PageRank di una pagina sono influenzati solo in piccolissima parte da Link ipertestuali interni. Anzi di più: è importante che le due pagine non risiedano sullo stesso server, giudicato dal PR come pagine “vicine tra loro”.

Tutto questo per confermare che in alcuni sistemi complessi come le reti, le caratteristiche fondamentali sono descritte non dai nodi, dai loro costituenti, ma dalle relazioni tra esse.Un approccio totalmente nuovo utilizzato recentemente anche in altri campi scientifici.

In Biologia Sistemica, ad esempio, non si studiano i geni e le proteine individualmente ed un alla volta, come è stato fatto, del resto con straordinario successo, negli ultimi 30 anni. Ma ci si interessa di come si comportano e di quali relazioni hanno tra loro gli elementi che costituiscono un sistema biologico, mentre stanno funzionando.

Un nuovo modo di approcciarsi ai fenomeni che farà di questo nostro secolo, per dirla con le parole di un altro celebre scienziato, Stephen Hawking, il "Secolo della Complessità".


REFERENCES

[1] Paul Erdős and Alfréd Rényi , Publ. Math. Inst. Acad. Sci. 5, 17 (1960).

[2] B. Bollobas, Random Graphs (Academic Press, London, 1985).

[3]Albert-László Barabási, and R. Albert, Science 286, 509 (1999).

[4] Albert-László Barabás, Linked, The New Science of Networks, Perseus Publishing, 2002

[5] Per una introduzione brillante alle leggi di potenza in tutte le forme, si veda Manfred Schroeder, Fractals, Chaos, Power Laws: Minutes from an Infinitive Paradise, W.H.Freeman, New York, 1991

[6] Albert-László Barabási, Ginestra Bianconi, Competition and multiscaling in evolving network, (2000)

[7] The PageRank Citation Ranking: Bringing Order to the Web (PDF, 1999) by Lawrence Page, Sergey Brin, Rajeev Motwani and Terry Winograd

[8] Il lavoro sull’invecchiamento condotto dal gruppo dell’Università di Boston è stato pubblicato in L.A. Amaral, A. Scala, M. Barthélémy e H.E. Stanley, Classes of Small-World Networks, in “Proceedings of the National Academy of Sciences”, 97 (2000). pp. 1149-152

[9] GOOGLE E L'EFFETTO SAN MATTEO

L'AUTORE

Claudio Pasqua è docente di Scienza della Comunicazione dal 1994. La teoria della complessità (l'insieme interdisciplinare delle teorie che si occupano dello studio di sistemi complessi) e gli scenari del mondo digitale e delle sue applicazioni nel mondo reale sono alcune delle sue attività di interesse. Pubblica regolarmente articoli sull'argomento ICT su riviste nazionali e su Internet dal 1995