Rete a invarianza di scala

Viene definita rete a invarianza di scala (in inglese scale-free network) un grafo che gode della seguente proprietà: se si considera la relazione tra il numero di nodi ed il numero delle loro connessioni si vede che il suo grafico è di tipo esponenziale negativo, e quindi 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 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 con Rèka Albert dell'Università di Notre Dame (USA) nel 1999.

Alcuni esempi

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

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. Il meccanismo del ricco che diventa sempre più ricco è inoltre molto resistente contro altri meccanismi di crescita della rete e porta spesso alla preservazione della proprietà dell'invarianza di scala.^[1]

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.

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 ${\frac {1}{\sqrt {N}}}$ 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 attacchi 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.

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.

Note

^ Angelica Pachon, Laura Sacerdote e Shuyi Yang, Scale-free behavior of networks with the copresence of preferential and uniform attachment rules, in Physica D: Nonlinear Phenomena, 2018, DOI:10.1016/j.physd.2018.01.005, arXiv:1704.08597.

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 88-06-16914-9
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
Caldarelli, G., Scale-Free Networks, Oxford University Press, (2007)
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)

Voci correlate

Collegamenti esterni

(EN) Eric W. Weisstein, Rete a invarianza di scala, su MathWorld, Wolfram Research.

Portale Matematica: accedi alle voci di Wikipedia che trattano di Matematica

[PSY-1] Angelica Pachon, Laura Sacerdote e Shuyi Yang, Scale-free behavior of networks with the copresence of preferential and uniform attachment rules, in Physica D: Nonlinear Phenomena, 2018, DOI:10.1016/j.physd.2018.01.005, arXiv:1704.08597.

[1]