Appunti in libertà: le reti casuali di Erdos e Renyi

- 6 marzo, 2007 10:51 pm

I seguenti appunti sono frutto della lettura del libro “Link” di Albert Laszlo Barabasi. Nel libro si discutono alcune proprietà delle reti, procedendo per esempi, lasciando formule e spiegazioni matematiche in appendice. L’approccio forse un po’ troppo semplicistico potrà far storcere il naso ai più esperti ma è ideale per chi si avvicina allo studio delle reti.
Uno dei primi capitoli tratta delle reti casuali, concetto introdotto nel 1959 da Erdos e Renyi.
Immaginate di organizzare un ricevimento con un centinaio di invitati, tutti estranei tra di loro, e di voler servire per l’occasione vino ai vostri ospiti. Confidate ad un invitato di aver messo il vino di qualità all’interno delle bottiglie con l’etichetta nera e di aver riempito le bottiglie con l’etichetta rossa con vino economico. Pensate di poter trovare almeno un bicchiere di buon vino a fine serata? In altre parole, quanto tempo dovrà trascorrere prima che tutti gli invitati vengano a conoscenza della qualità del vino con l’etichetta nera? (supponendo che nessun invitato possa giungere autonomamente a tale conclusione). Un invitato può stringere amicizia con due o tre persone, si possono formare dei piccoli gruppi di discussione all’interno della festa, il vostro amico-confidente trasmetterà ad altre persone il vostro “segreto”. Se ipotizziamo che ogni persona parla con un’altra per dieci minuti, prima che tutti si siano conosciuti personalmente devono passare 16 ore, dato che il ricevimento ha una durata sicuramente inferiore (3-4 ore?) il nostro segreto (ed il nostro vino) è al sicuro. Erdos e Renyi hanno introdotto una visione diversa del problema. Immaginiamo la festa come una grande rete, dove gli invitati sono i nodi ed i legami sociali che si instaurano con la conversazione sono i link. Immaginiamo che i link tra i nodi si instaurino in maniera casuale. Non importa la topologia o la natura della rete, se si raggiunge un certo numero di link ed i nodi possiedono in media almeno un collegamento, il nostro vino avrà i minuti contati. Infatti inizialmente assisteremo alla nascita di “cluster”, cioè piccoli gruppi di persone che socializzano al loro interno ma non all’esterno. Trascorsi dieci minuti (il tempo ipotizzato per la socializzazione) i nodi (cioè le persone) tenderanno a creare nuovi cluster senza rompere i legami instaurati precedentemente. In questo modo, dopo n minuti, anche se i componenti non si conoscono direttamente, si instaurerà un rapporto indiretto tra tutti gli invitati, i link instaurati saranno tali che un qualsiasi nodo potrà essere collegato direttamente o indirettamente a qualsiasi altro nodo. Il momento in cui tutti sono collegati con tutti è chiamato “Transizione di fase”.
Riassumendo, indipendentemente dal tipo di rete, se colleghiamo tra di loro coppie di nodi, raggiunto un numero n di link, la rete si trasforma radicalmente. Prima abbiamo una serie di piccoli cluster non comunicanti tra loro; dopo otteniamo un unico grande cluster in cui tutti i nodi sono collegati.
I collegamenti tra i nodi sono casuali, cioè ogni nodo ha la possibilità di acquisire un link in più. Un modello di questo tipo prevede quindi che alcuni nodi possiedano un numero elevato di link ed altri ne siano addirittura privi. Ma il numero di link posseduto da ogni nodo segue, secondo la dimostrazione di Bollobas del 1982, una distribuzione di Poisson per cui tutti i nodi hanno un numero di link medio rendendo rare le deviazioni significative dalla norma. La teoria di Erdos e Renyi prevede quindi un mondo medio dove tutti abbiamo più o meno lo stesso numero di amici, le imprese hanno lo stesso numero di rapporti di affari ed i siti web hanno lo stesso numero di visite.

Se la natura distribuisce i suoi link alla cieca, nel lungo periodo nessun nodo risulta favorito rispetto agli altri

La debolezza del modello risiede proprio negli scarsi riscontri in applicazioni concrete ma non era certo intenzione di Erdos e Renyi elaborare una teoria universale sulla formazione delle reti.

Postato in : Scienza della complessità
Print This Post Print This Post


Trackbacks & Pingbacks

Commenti
dirichlet 25 novembre 2008

Ciao, anche io ho letto ed apprezzato Link, ottimo sunto e approfondimento…sai di qualche altro libro del genere?

Grazie,

Alberto 25 novembre 2008

Ciao dirichlet
Ora non conosco i tuoi gusti in materia, però se hai apprezzato Link di Barabasi ti consiglio anche Non linearità, caos Complessità di Bertuglia e Vaio.
Non vi è un rapporto diretto con Link però potrebbe rivelari una lettura interessante. Qui un assaggio:
http://tecalibri.altervista.org/B/BERTUGLIA-CS_complessita.htm#p000

E qui il link dove acquistarlo:
http://www.ibs.it/code/9788833917689/bertuglia-cristoforo-s/non-linearita-caos

A presto!

dirichlet 30 novembre 2008

Ciao, grazie per le segnalazioni, al momento sto leggendo “Caos” di Leonard Smith (http://www.webster.it/libri-caos_smith_leonard_codice-9788875781132.htm) che dovrebbe essere anch’esso attinente alle tue segnalazioni.
Metto subito quello di Bertuglia nella whishlist di IBS!

Alberto 30 novembre 2008

Leggendo il riassunto ho capito di cosa si tratta. Grazie della segnalazione, entra nella lista dei libri da leggere!

Sorry, the comment form is closed at this time.