Reti e sistemi complessi

Reti e sistemi complessi
Modelli per la rappresentazione della realtà
Reti sociali
Organizzate una festa ed invitate 100 persone che non
si conoscono tra loro
Le persone cominceranno ad interagire tra di loro
formando gruppi distinti ma dinamici
Diffondete una informazione rivelandola soltanto ad
un ospite
L’informazione si propagherà molto più velocemente di
quanto ci si aspetterebbe dalla semplice interazione tra
gli individui
Gradi di separazione
Frigyes Karinty, nel racconto “Catene” narra:
“per dimostrare che gli individui della terra sono più vicini
che mai un membro del gruppo propose un
esperimento. Suggerì che ognuno di noi scegliendo una
persona qualsiasi del miliardo e mezzo di abitanti del
pianeta, può raggiungerla senza difficoltà tramite un
massimo di cinque persone, di cui solo una occorre sia
in contatto diretto”
Questa fu, nel 1929, la prima apparizione di quello che noi
oggi chiamiamo “i sei gradi di separazione”
Stanley Milgram
Sociologo di Harvard, mise in atto la prima
dimostrazione formale di questa intuizione attraverso
un esperimento “epistolare”
Cercò di stabilire qual’era la distanza media tra due
individui qualsiasi degli stati uniti.
Whicita, nel Kansas e Omaha nel Nebraska
Il risultato finale evidenziò una distanza media di 5,5
Reti random e reti non
random
In una rete sociale random ogni individuo tutti gli
individui hanno la stessa probabilità di conoscere
ognuno degli altri individui.
In una rete sociale esistono tipologie di legami diversi, i
legami “forti” ed i legami “deboli”
I legami deboli sono importanti per la diminuzione
delle distanze globali in una rete
Il Numero di Erdos
Introdotto per misurare l’influenza dei ricercatori in
matematica
Misura la “distanza” dal famoso scienziato Paul Erdos
In realtà distanze molto brevi sono rilevabili anche al di
fuori del mondo matematico (James D. Watson, Bill
Gates, … )
Esempio di Network
Rappresentano un insieme di reazioni
chimiche in una cellula
Un insieme di metaboliti
(composti chimici) subiscono
delle trasformazioni (reazioni
chimiche) catalizzate da altre
sostanze (enzimi)
Alla network possono essere
aggiunti altri elementi: interazioni
con proteine, elementi regolatori
Schwarz et al. BMC Bioinformatics 2007
Il coefficiente di clustering
Che probabilità hanno due miei amici di conoscersi tra di loro?
In una rete casuale questa probabilità è uguale a quelle che
hanno un gondoliere veneziano ed un capo tribù africano
In realtà la probabilità che i miei amici si conoscano è molto
superiore, perché c’è la tendenza a frequentare (legami forti)
cerchie ristrette
Il coefficiente di clustering e il rapporto tra il numero di link
effettivi ed il numero di link ipotizzabili.
Un coefficiente di clustering uguale ad uno significa che tutti i
nodi sono connessi tra di loro.
Network Biology
COEFFICIENTE DI CLUSTERING
In molte network se A è connesso con B (con un link diretto) e B è
connesso con C allora con alta probabilità anche A ha un link diretto a
C.
Questo fenomeno può essere quantificato con
Ci 
2ni
k (k  1)
Dove ni è il numero di link che connettono i k vicini del nodo i ad ogni
altro.
La media <C> caratterizza la tendenza globale dei nodi a formare
cluster.
Network Biology
COEFFICIENTE DI CLUSTERING
In altre parole Ci da il numero di
triangoli che passano attraverso i.
k(k-1)/2 è il numero massimo
possibile di triangoli.
Esempio:
Solo B e C fra i vicini di A sono
linkati. Quindi:
nA=1 CA=2/20
Invece per F si ha CF=0
Reti Random e reti che
seguono una legge di potenza
Small world effect
Small world effect
Any two nodes can be connected with a path of a few
links only
Biological scale-free network are ultra small
In metabolism, paths of only three or four reactions can
link most pairs of metabolites
Local perturbation in metabolite concentration can reach
the whole network
There are evolutionary mechanisms that have maintained
the average path length during evolution. (e.g. E.coli &
H.influenza)
Disassortative nature
Hubs avoid linking directly to each other and instead
connect to proteins with only a few interactions
Inconstant to human social network