Rete a invarianza di scala
Da Wikipedia, l'enciclopedia libera.
Viene definito una Rete a invarianza di scala (in inglese è scale-free network) un grafo che gode della seguente proprietà: se si considera il numero di nodi aventi un certo numero di connessioni si vede che questo grafico è di tipo esponenziale negativo, appunto invariante per cambiamenti di scala. Questa invarianza di scala significa che paragonando il numero di due tipi di nodi, ad esempio quelli con 10 connessioni e quelli con 15, si vede che la proporzione fra i due è e − a(Nb − Na), dove Nb ed Na sono il numero di nodi del denominatore e numeratore rispettivamente mentre a è un parametro del tipo di rete considerato. Questa legge è detta legge di potenza, di cui a è il parametro.
Il termine fu coniato da Albert-László Barabási dell'Università di Notre Dame, USA nel 1998.
Indice |
[modifica] Alcuni esempi
Sono reti a invarianza di scala:
- La rete metabolica
- La rete sociale
- La rete economica
- Internet (i collegamenti fisici tra router)
- il World Wide Web (i collegamenti tra pagine web)
- Il numero di Bacon e il numero di Erdős
- I domini magnetici in un materiale antiferromagnetico
- Sistemi di apprendimento lessicale
[modifica] Nascita di una rete a invarianza di scala
La nascita di una rete a invarianza di scala è molto semplice: si stabilisce che quando un nodo deve stabilire un nuovo collegamento, preferisca farlo verso un nodo che ne ha già molti, portando questi ad una crescita esponenziale con l'aumentare del numero dei collegamenti della rete. In breve è una situazione del tipo:il ricco diventa sempre più ricco mentre il povero sempre più povero (in proporzione). Nodi di questo tipo vengono detti hub.
[modifica] Piccolo Mondo
Vedi articolo principale: Teoria del mondo piccolo
La presenza di questi hub è alla base dell'effetto "6 gradi di separazione", ovvero la teoria secondo cui due persone qualsiasi sono in media collegate da sei livelli di conoscenza (ovvero gli "amici degli amici degli amici degli amici degli amici dei miei amici" comprendono buona parte della popolazione mondiale). In questo senso gli hub hanno la funzione di collegare zone del grafo che sarebbero altrimenti separate.
[modifica] Sensibilità ai danni
Le reti a invarianza di scala sono interessanti anche per il loro comportamento nei confronti di situazioni aggressive. Paragoniamo una rete di tipo casuale ed una a invarianza di scala sulla base delle reazioni a due tipi di attacco: l'attacco casuale e l'attacco mirato. Un attacco casuale non sceglie i nodi da sopprimere, andando a caso; in una rete casuale la perdita di funzionalità sarà quindi proporzionale al danno inflitto mentre una rete ad invarianza, avendo la sua funzionalità concentrata in pochissimi centri, sarà virtualmente insensibile a danni di questo tipo fintanto che il numero di nodi non-hub rimane alto. Un attacco mirato invece sceglie con cura i nodi da attaccare per massimizzare il danno; nel caso di una rete casuale, avendo tutti i nodi approssimativamente la stessa importanza (con un margine di errore di 
dove N è il numero dei nodi della rete) un attacco mirato non ha quindi differenze sostanziali da un attacco casuale. L'effetto su di una rete ad invarianza di scala è invece l'opposto:con pochi singoli attacci mirati agli hub è possibile abbattere la funzionalità praticamente del 100% (anche con milioni di nodi!). L'effetto è pertanto studiato per via degli effetti che un eventuale attacco informatico da parte di malintenzionati potrebbe avere sulla struttura di internet, o di come tossine mirate possano distruggere interi ecosistemi.
[modifica] Fisica e teoria dei grafi
Nel 2000, Ginestra Bianconi e Albert-László Barabási hanno mostrato come i fenomeni fisici della transizione di fase e del condensato di Bose-Einstein siano matematicamente equivalenti ai cambiamenti delle reti ad invarianza di scala. Recentemente sono state avanzate ipotesi di somiglianza tra il comportamento dei materiali ferromagnetici e antiferromagnetici e l'evoluzione delle opinioni nelle reti sociali.
[modifica] Voci correlate
[modifica] Bibliografia
- Barabási, A-L. e Albert, R. "Emergence of Scaling in Random Networks" Science 286, pp 509-512, 1999
- Barabási, A-L., Albert, R., Jeong, H. "Mean-Field Theory for Scale-Free Random Networks", Physica A 272, pp 173-187, 1999
- Barabási, A.-L., "Link - la scienza delle reti", Einaudi, 2004, ISBN 8806169149
- Barabási, A.-L. e Bianconi, G., Bose-Einstein Condensation in Complex Networks, Phisycal Review Letters, vol. 86, N. 24, pp. 5632-5635, 11 giugno 2001
- Chang, I., Sznajd sciophysics model on a triangular lattice: ferro and antiferromagnetic opinions, International Journal of Modern Physics C, Vol. 12, No. 10, pp 1509-1512 (2001)
