Reti Complesse

I. Concetti base di teoria dei grafi e delle reti

II. Modelli

III. La rete come insieme di comunità

Programma

Bibliografia

• Evolution of networks

S.N. Dorogovtsev, J.F.F. Mendes, Adv. Phys. 51, 1079 (2002),

cond-mat/0106144

• Statistical mechanics of complex networks

Reka Albert, Albert-Laszlo Barabasi

Reviews of Modern Physics 74, 47 (2002), cond-mat/0106096

• The structure and function of complex networks

M. E. J. Newman, SIAM Review 45, 167-256 (2003),

cond-mat/0303516

• Complex networks: structure and dynamics

S. Boccaletti, V. Latora, Y. Moreno, M. Chavez, D.-U. Hwang

Physics Reports 424, 175-308 (2006)

Definizione di Network Network=insieme di vertici (nodi) uniti da

legami (links)

Rappresentazione molto astratta

molto generale Utile per descrivere

sistemi molto diversi

Nodi Links

Reti sociali Individui Relazioni sociali

Internet Routers

AS

Cavi + coll. wireless

Accordi commerciali

WWW Webpages Hyperlinks

Rete di interazione

tra proteine

Proteine Reazioni chimiche

Esempi

Rete delle collaborazioni

scientifiche

Nodi: scienziati

Links: articoli scritti in collaborazione

Pesi dei link: possono dipendere da

•Numero degli articoli

•Numero degli autori di un dato articolo

•Numero delle citazioni

Rappresentazione grafica

Differenti livelli di

risoluzione

Internet

Meta-population networks

City a

City j

City i

Nodi: struttura sociale (esempio: città)

Links: vie di spostamento/traffico

interazioni

gene-proteina

Interazioni

proteina-proteina

PROTEOMA

GENOMA

Citrate Cycle

METABOLISMO

Reazioni

biochimche

Piano della lezione

1) Breve introduzione ai concetti base di

teoria dei grafi

2) Approccio statistico: Ensemble di grafi,

distribuzioni di probabilità e correlazioni

3) Reti pesate.

Obiettivo

Definire una serie di osservabili che

permettano di caratterizzare un sistema

complesso e che forniscano indicazioni per

spiegare i meccanismi microscopici che

hanno portato alla formazione del sistema

Universalità

Reti di origine molto diversa

Hanno qualcosa in comune?

Esistono proprietà universali?

La rappresentazione in termini di teoria dei grafi è

lo strumento giusto per rispondere….

1) Introduzione alla teoria dei grafi

- Definizioni di base

- Matrice di adiacenza

- Densità

- Cammini e connettività

- Alberi

- Centralità

- Clustering

Teoria dei grafi

Grafo G=(V,E)

• V=insieme di vertici i=1,…,N

• E=insieme di links (i,j)

Link ordinario:

Link diretto :

i j

i j

Bidirezionale

comunicazione/

interazione

Numero massimo di links

• Non diretti: N(N-1)/2

• Diretti: N(N-1)

Teoria dei grafi

Grafo completo:

(interazione “tutti con tutti”)

Matrice di adiacenza

N nodi i=1,…,N

aij= 1 if (i,j) E

0 if (i,j) E

0 1 2 3

0 0 1 1 1

1 1 0 1 1

2 1 1 0 1

3 1 1 1 0

0

3

1

2

Matrice di adiacenza

N nodi i=1,…,N

aij= 1 if (i,j) E

0 if (i,j) E

0 1 2 3

0 0 1 0 0

1 1 0 1 1

2 0 1 0 1

3 0 1 1 0

0

3

1

2

Simmetrica se i link non

sono diretti.

Matrice di adiacenza

N nodi i=1,…,N

aij= 1 if (i,j) E

0 if (i,j) E

0 1 2 3

0 0 1 0 1

1 0 0 0 0

2 0 1 0 0

3 0 1 1 0

0

3

1

2

Non simmetrica

Se i links sono diretti

Densità di un grafo

Densità di un grafo: D=|E|/(N(N-1)/2)

Numero dei links

Massimo num. di links possibile D=

Grafo “sparso”: D <<1 Matrice di adiacenza

con pochi 1 e molti 0

Rappresentazione: lista dei vicini di ogni nodo

l(i, V(i))

V(i)= vicini di i

Cammini G=(V,E)

Cammino di lunghezza n = lista ordinata di

• n+1 vertici i0,i1,…,in V

• n links (i0,i1), (i1,i2)…,(in-1,in) E

i2 i0 i1

i5

i4

i3

Ciclo/loop = cammino chiuso (i0=in)

Alberi

Un albero è un grafo senza cicli

• N nodi, N-1 links

Cammini e connettività

G=(V,E) è connesso se e solo se esiste un cammino

che connette ogni coppia di nodi di G .

È connesso

• non è connesso

• è formato da due componenti

Cammini e connettività

G=(V,E)=> distribuzione delle componenti connesse

Componente gigante= componente la cui

dimensione cresce in modo proporzionale

al numero di vertici N

Esistenza di una

componente gigante

Una frazione

macroscopica dei nodi

del grafo è connessa

Cammino minimo (shortest path)

i

j

Cammino minimo tra i e j: numero minimo di links

necessari a congiungere i e j

distanza l(i,j)= cammino

minimo tra i and j

Diametro di un grafo= max(l(i,j))

Cammino minimo medio = ij l(i,j)/(N(N-1)/2)

Grafo completo: l(i,j)=1 per tutte le coppie i,j .

“Piccolo mondo”(Small-world): “piccolo” diametro

Effetto “Small World”

L’esperimento di Milgram

Milgram, Psych Today 2, 60 (1967)

Dodds et al., Science 301, 827 (2003)

“Sei gradi di separazione”

SMALL-WORLD

Esempio: Internet

Distribuzione delle distanze

tra due nodi

Internet:

Esempio: Rete aereoportuale

IATA database

V = 3100 aereoporti

E = 17182 link pesati

wij #passeggeri / (unità di tempo)

Centralità

Come quantificare l’importanza di un nodo?

• Grado (degree)=numero di vicini =j aij

i

ki=5

(grafi diretti: kin, kout)

“Betweenness centrality”

Per ogni coppia di nodi (l,m) , definisco:

slm numero di cammini minimi tra l e m

silm num. di cammini minimi che passano per i

bi è la somma silm

/ slm su tutte le coppie (l,m)

i

j

bi è grande

bj è piccola

NB: quantità simile: “load” li= silm

NB: generalizzazione: “link betweenness centrality”

Importante: è una quantità basata sui cammini

“Clustering

”

C(i) = # di links tra 1,2,…n vicini

k(k-1)/2

1

2

3

k

Clustering: c’è un’alta probabilità che i miei amici si conoscano!

(esempio tipico: social networks)

Coefficiente di clustering di un nodo

i

Clustering

Coefficiente di clustering medio di un grafo

C=i C(i)/N

2) Approccio statistico

- Distribuzione di probabilità dei gradi

- Correlazioni a più punti

- Rappresentazione spettrale

- Assortatività e dissortatività

Distribuzione dei gradi

•Lista dei gradi k1,k2,…,kN Non molto utile!

•Istogramma:

Nk= numero dei nodi di grado k

•Distribuzione:

P(k)=Nk/N=probabilità che un nodo scelto a

caso abbia grado k

•Distribuzione cumulativa:

P>(k)=probabilità che un nodo scelto

a caso abbia grado almeno k

Distribuzione dei gradi

P(k)=Nk/N= probabilità che un nodo scelto a caso

abbia grado k

Media=< k > = i ki/N = k k P(k)=2|E|/N

Fluttuazioni: < k2 > - < k > 2

< k2 > = i k2i/N = k k

2 P(k)

< kn > = k kn P(k)

Grafo “sparso”: < k > << N

Correlazioni a più punti dei gradi

P(k): non è sufficiente a descrive un network

Reti “assortative”:

Nodi di grado alto

preferiscono connettersi con

altri nodi di grado alto.

Ex: social networks

Reti “dissortative”:

Nodi di grado alto

preferiscono connettersi a nodi

di grado basso.

Ex: technological networks

Correlazioni a più punti dei gradi

Misura della correlazione: P(k’,k’’,…k(n)|k): probabilità condizionale che un nodo di

grado k sia connesso a nodi di grado k’, k’’,…

Caso più semplice: P(k’|k): probabilità condizionale che un nodo di grado k

sia connesso ad un nodo di grado k’

Correlazioni a più punti dei gradi

misura “pratica” di correlazione :

Grado medio dei primi vicini

i

k=3 k=7

k=4 k=4

ki=4 knn,i=(3+4+4+7)/4=4.5

Grado medio dei primi vicini

“Spettro di correlazione”:

Costruito mettendo assieme

nodi con lo stesso grado

Class di grado k

Esempio: rete casuale e scorrelata

P(k’|k) indipendente da k

(ricorda: P(k’|k) = prob. che un link di grado k

punti ad un nodo di grado k’)

proporzionale

a k’ stesso

Punc(k’|k)=k’P(k’)/< k >

numero di link uscenti da un nodo di grado k’

numero di link uscenti da un nodo qualsiasi

Assortatività

• Comportamento Assortativo :

knn(k) è una funzione crescente di k

Esempio: social networks

• Comportamento Dissortativo:

knn(k) è una funzione decresente di k

Esempio: internet (struttura gerarchica)

3) Reti pesate

1) Definizioni ed esempi

2) Coefficiente di clustering pesato

3) Assortatività pesata

Reti pesate

Nelle reti reali i links:

• Portano traffico (reti di trasporti, Internet…)

• Hanno intensità diverse (social networks…)

Descrizione generale: pesi

i j wij

aij: 0 or 1

Wij: variabile continua

- Collaborazioni scientifiche: numero di articoli in

comune

●Internet, emails: numero di emails scambiati

●Aereoporti: numero di passeggeri

●Reti metaboliche: flussi

●Reti economiche: numero di azioni possedute

●…

Pesi: esempi

In generale si pone: wii=0

Ed il peso è simmetrico: wij=wji

Reti Pesate

I pesi stanno sui link (weigths)

Forza (Strength) di un nodo:

si = j V(i) wij

=>Generalizza in modo naturale la nozione di grado alle reti pesate

=>Esempio: quantifica il traffico totale che passa per un nodo.

Coefficiente di clustering

pesato

si=16 ci

w=0.625 > ci

ki=4 ci=0.5

si=8 ci

w=0.25 < ci

wij=1

wij=5

i i

Coefficiente di clustering

pesato

Se i pesi sono random: C = Cw

C < Cw : piu pesi sui grafi completi (cliques)

C > Cw : meno pesi sui grafi completi (cliques)

i j

k (wjk)

wij

wik

Coefficiente di clustering medio

C=i C(i)/N

Cw=i Cw(i)/N

Rappresentazione spettrale del Clustering:

Assortatività pesata

ki=5; knn,i=1.8

1

5 5

5

5

i

Assortatività pesata

ki=5; knn,i=1.8

5

1 1

1

1

i

Assortatività pesata

ki=5; si=21; k

nn,i=1.8 ; knn,i

w=1.2: knn,i > knn,iw

1

5 5

5

5

i

ki=5; si=9; k

nn,i=1.8 ; knn,i

w=3.2: knn,i < knn,iw

5

1 1

1

1

i

Assortatività pesata

“Participation ratio”

1/ki se tutti i pesi sono uguali vicino a 1 se alcuni pesi dominano