Reti parte 2: Gradi di separazione

Un modo molto sintetico di descrivere la differenza tra le due reti di linee aeree del post precedente è attraverso la dimensione di una rete. Non intendo dimensione nel senso di grandezza o estensione, ma un concetto più simile a quello di dimensioni dello spazio, una su una retta, due su un piano, e così via. Per le reti è rilevante una definizione di dimensione abbastanza esotica, che è lo stessa che si usa per i frattali. Questa non fa uso, come si fa di solito, del numero di variabili usate per descrivere un punto, e grazie a questo non è necessariamente un numero intero!

Cercherò di spiegare il senso di questo strano concetto. Partiamo da una rete fatta così:1dchiamiamo distanza tra due nodi della rete il numero minimo di passi che dobbiamo compiere per passare dall’uno all’altro. Inoltre si dice diametro D la distanza tra i due nodi più lontani. In questo caso è facile vedere che il diametro è lineare in n, in particolare è uguale a n-1. I due nodi più lontani sono, ovviamente, quelli agli estremi.

Se invece consideriamo un reticolo quadrato

2d

i due nodi più lontani sono quelli negli angoli, che distano il doppio del lato del quadrato. D’altra parte, se il quadrato contiene n nodi, il lato ne contiene un numero dell’ordine della radice di n.

Potremmo andare avanti, ma dovrebbe cominciare a intuirsi un pattern: con un reticolo cubico il diametro scalerà come la radice cubica del numero di nodi, e così via. Dal momento che è intuitivo definire il primo esempio come rappresentativo di reti unidimensionali e il secondo come bidimensionale, chiamiamo dimensione della rete il numero d che dà la legge di potenza attesa:

D = n^{1/d}.

In poche parole, il diametro indica quanto è ben connessa la rete, mentre il numero di nodi quanto è grande. Allora la dimensione è una misura di quanto è compatta. Più avanti vedremo degli esempi.

I reticoli non sono gli unici casi mono o bi-dimensionali: considerando un anello, cometoro

si vede che questa volta il diametro è n/2, diverso dal reticolo rettilineo, ma con la stessa legge di potenza rispetto a n, che fa di lui ancora una volta una rete a una dimensione, come vuole l’intuito.

L’intuito però può rapidamente fallire quando esaminiamo casi più strani.

cayley

Questo è un Cayley tree. Potete divertirvi a far vedere che il diametro scala come il logaritmo del numero di nodi! Non esiste un d abbastanza grande da soddisfare la definizione! Per questo si dice che la rete ha dimensione infinita. Reti di questo tipo si chiamano small worlds, “mondi piccoli”.

Da quando il loro studio si è diffuso, negli anni Novanta, reti small world sono state trovate dappertutto. È molto nota l’ipotesi dei sei gradi di separazione, secondo cui ognuno di noi è collegato a chiunque altro nel mondo, da un contadino cinese al presidente Obama, attraverso non più di sei “passi” di conoscenza personale. Perché qualcosa del genere sia possibile, su sette miliardi di individui, il diametro non può scalare con una legge di potenza!

Un altro esempio, quello da cui eravamo partiti, è Internet: immaginate che sia, per esempio, una rete bidimensionale. Ogni volta che volete raggiungere un server in Nuova Zelanda, i dati che inviate e ricevete dovrebbero passare attraverso un numero di intermediari dell’ordine della radice di n, qualcosa come dieci, centomila computer o più. Non sarebbe di sicuro un metodo efficiente di costruire una “world wide web”. Ecco perché l’informazione sulla struttura della rete è cruciale per il suo funzionamento.

Con questo volevo spiegare perché tutte queste reti sono strutturate in modo da avere una dimensione infinita. Il problema è che spiegare il perché non è sufficiente. Il “perché” presuppone un fine; ma questo è in contraddizione con quello che dicevo nel post precedente, cioè che Internet, il WWW, e molte altre reti di rilevanza quotidiana si sono sviluppate (“evolute” è un bel modo di dirlo) per auto-organizzazione, senza che ci fosse un progettista o Creatore con la C maiuscola che vede dall’alto gli scopi della sua opera. Abbiamo quindi ancora una volta bisogno di trovare un modo per rendere conto di come hanno fatto a emergere una dimensione, e una degree distribution, che sono proprio quelle che ci servono. La rete deve essersi sviluppata secondo un criterio particolare che ha portato a questo risultato momento per momento, ognuno pensando per sé, senza sapere quale fosse l’obiettivo globale.

Disgraziatamente, mi sono dilungato troppo.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s