Metodi matematici per l’analisi di sistemi complessi

Metodi matematici per l’analisi di sistemicomplessi

Possamai Lino

Dipartimento di MatematicaUniversità degli Studi di Padova

23 marzo 2009

Metodi matematici per l’analisi di sistemi complessi

IntroduzioneGraph theory

Un grafo è una coppia G=(V,E) diinsiemi in cui V={v1, ..., vn} sono i nodimentre E={..., (vi , vj), ...} rappresentanogli archi.

Un grafo G può essere orientato(diretto) oppure no. Nel primo caso, se(u, v) ∈ E allora non è detto che valgaanche (v , u) ∈ E . Nei grafi nonorientati, (u, v) ∈ E ⇔ (v , u) ∈ E

Si definisce cammino p da a � b uninsieme di nodi {a, x1, ..., xn, b} oequivalentemente un insieme di architale che {(a, x1), ..., (xn, b)}.


IntroduzioneGraph theory

Un grafo si dice pesato se esiste la funzione w : E → R.

Il peso di un cammino p è rappresentato dapw(p) =

∑ki=1 w(xi−1, xi).

Se il grafo non è pesato, allora si può assumere chew(a) = 1, ∀a ∈ E .

Per ogni coppia di nodi u, v è possibile definire la distanzaminima

δ(u, v) =

{ ∞min{pw(p) | p cammino tra u e v}

Una volta calcolata la distanza tra δ tra ogni coppia di nodi, ilvalore (finito) più grande rappresenta il diametro di G.


IntroduzioneStrutture Dati

Ci sono diversi modi perrappresentareanaliticamente un grafo

mediante matricibinarie n × n {aij} incui aij = 1 se il nodo iè adiacente al nodo j ,0 altrimenti.mediante liste diadiacenza.

Molto spesso la scelta diuno rispetto all’altrodipenderà dall’algoritmoutilizzato e dal fatto che ilgrafo sia denso oppuresparso


IntroduzioneStrutture Dati

Esistono altre strutture datiche rappresentano ungrafo in maniera compatta

Per alcuni algoritmi di visitadei grafi, come il BreadthFirst Search, utilizzatomolto spesso nel calcolodelle metriche, risulta lapiù efficiente

Adatta anche per il calcoloGPGPU


DegreeMedio, in/out

Il grado di un nodo rappresenta la somma dei nodi adiacenti a sestesso. Formalmente, se il grafo non è diretto (topologico):

ki =∑

j

aij 〈k〉 =

∑i ki

n=

2kn − 1

Rispettivamente, se il grafo è orientato,

k ini =

∑j

aji kouti =

∑j

aij

per cui ki = kouti + k in

i .


Distribuzione P(k) del grado dei nodiConnettività

È la probabilità che unnodo scelto a caso abbiagrado k oequivalentemente lafrazione dei nodi di grado k

È fondamentale percaratterizzare la topologiadel grafo che si staanalizzando.

Nel caso di grafi diretti, cisaranno due distribuzioniP(kin) e P(kout).


Shortest path (L)

L è una metrica che rappresenta la distanza media diseparazione tra ogni coppia di nodi presenti in G:

L(G) =1

n(n − 1)

∑i �=j∈G

δij

Rappresenta una caratteristica globale della rete.

Quando il grafo non è connesso, L → ∞. In questi casi si tendea considerare il giant cluster (connesso).


Esempio

a � b = 1, a � c = 11, a � d =5, a � e = 3

b � a = 1, b � c = 13, b � d =6, b � e = 4

c � a = 11, c � b = 13, c �

d = 6, c � e = 8

d � a = 5, d � b = 6, d � c =6, d � e = 2

L ≈ 5


Indice di clusterizzazione (C)

Non è sufficiente L per descriverequanto un grafo sia connessolocalmente

Si può utilizzare per esempio ilcoefficiente di clustering locale Ci

Ci =# of edges in Gi

ki(ki − 1)/2

e mediarlo rispetto al numero dinodi n in G, per cui

C(G) =1n

∑i∈G

Ci


Facebook


EfficienzaGlobale e locale

L’efficienza, viceversa, può essere calcolata anche quando il grafo èdisconnesso (nei grafi reali questo succede molto spesso) evitando lesituazioni in cui L diverge

Eglob = E(G) =

∑i �=j∈G εij

n(n − 1)=

1n(n − 1)

∑i �=j∈G

1δij


Esempio

a � b = 1, a � c = 1/11, a �

d = 1/5, a � e = 1/3

b � a = 1, b � c = 1/13, b �

d = 1/6, b � e = 1/4

c � a = 1/11, c � b =1/13, c � d = 1/6, c � e = 1/8

d � a = 1/5, d � b = 1/6, d �

c = 1/6, d � e = 1/2

Eglob ≈ 0.23


EfficienzaGlobale e locale

Dato che l’efficienza è una metrica calcolata a partire da qualsiasi ungrafo, la possiamo utilizzare per analizzare le proprietà locali, inparticolare considerando sottografi di G:

Eloc =1N

∑i∈G

E(Gi)

con Gi sottografo indotto dai vicini del nodo i .Se il grafo non è pesato, allora Eglob, Eloc ∈ [0, 1] mentre se lo è (ed inparticolar modo quando i pesi sono in [0, 1)), bisogna normalizzare leprecedenti formule:

Eglob =E(G)

E(Gideal)Eloc =

1N

∑i∈G

E(Gi)

E(Gideali )

dove Gideali è il sottografo Gi completamente connesso.


Costo

Molto spesso, instaurare una connessione di una certa portata(rete di flusso) ha un costo.

Se vogliamo confrontare reti che hanno la stessa efficienza(globale) e vedere quale ha il costo minore, allora

Cost(G) =

∑i �=j∈G aijγ(δij)∑

i �=j∈G γ(δij)

dove γ rappresenta la funzione che calcola il costo che bisognasostenere per costruire una connessione di tale portata.

Quando il grafo non è pesato, C sarà pari a 2kn(n−1)

La variabile costo è molto importante perché nelle reti reali lerisorse sono limitate per cui la crescita delle reti deve essere untradeoff tra performance(efficienza) ed economicità.


Random networks

All’inizio si pensava che i sistemi complessi fosserocorrettamente approssimati da una rete random.

La specifica di queste reti (modello) avviene mediante l’utilizzodi un parametro p che rappresenta la probilità che due qualsiasinodi siano collegati e dal numero n di nodi.

Quando n è grande, il grado medio di connettività tra i nodi〈k〉 = np e P(k) è approssimata da una legge di Poisson:

P(k) =〈k〉k

k !e−〈k〉

Inoltre, vale |E | = p(n(n − 1)/2).


Small-World networks

Nel 1967 il sociologo Milgram, grazie ad alcuni esperimenti, hanotato che l’utilizzo delle reti random come approssimazionedelle reti reali non era corretto.

Le reti che aveva analizzato avevano L molto bassa e C alto,efficienza globale e locale alta rispettivamente per le due serie dimetriche proposte


Small-World networks

I modelli che sono utilizzati per creare queste reti partono da unlattice di cardinalità n in cui ogni nodo è collegato con gliimmediati vicini.

Successivamente, vengono ridisegnati alcuni archi rispetto aduna probabilità p.

Rappresenta una rete mista di regolarità e di casualità


Scale-free Networks

Le reti scale-free rappresentanoun’evoluzione delle retismall-world. Hanno le stesseproprietà delle reti small-worlded in più:

Presenza di nodi congrado elevato (hub)

P(k) segue la legge dellapotenza P(k) ∼ c · k−γ

con c costante diproporzionalità e γcoefficiente della legge dipotenza.

Per ragioni ancorasconosciute, per le reti SFvale γ ∈ [2, 3]


Correlated graphsAssortative/disassortative.

Se si vuole sapere come si collegano gliarchi della rete,

knn,i =1ki

∑j∈Ni

kj =1ki

n∑j=1

aijkj

knn(k) =∑k ′

k ′P(k ′|k)

dove P(k ′|k) è la probabilitàcondizionata che un link di un nodo congrado k sia collegato ad un nodo congrado k ′.

Rimane tutt’ora sconosciuto il motivoper cui le reti biologiche e tecnologichesiano disassortative mentre quellesociali assortative.


Perturbation Analysis

Le metriche presentate fino ad ora sono uno snapshot in undeterminato istante t della vita di un sistema complesso,biologico, sociale o tecnologico che sia.

Possiamo quindi utilizzare per vedere cosa succede al variare dit e al variare della configurazione del sistema.

Nel caso della perturbation analysis, vogliamo capire cosasuccede nel caso di eliminazione di nodi e cosa succede con letopologie smallworld/scalefree.


Perturbation AnalysisFailure

L’attacco non tiene contofondamentalmente dellatopologia della rete

L’ordine con cui vengonotolti gli archi è totalmentecasuale

Le reti scalefreemantengono un’efficienzamolto alta anche quando sirimuove più della metà deinodi.


Perturbation AnalysisAttack

Questa simulazione si basa sullacreazione di una graduatoria dinodi che possono essereeliminati dal sistema.

I nodi vengono ordinati in baseall’efficienza globale calcolatasulla rete da cui viene tolto quelnodo.

Viene quindi tolto in sequenza ilnodo con l’effetto distruttivomaggiore.

Nelle reti scalefree, a differenzadelle reti casuali, dopo averrimosso una piccola percentualedi nodi, la rete perdevelocemente la connettività.


Perturbation AnalysisSimulazioni


Analisi Telescopica

Prende spunto dal concetto di potererisolutivo dell’occhio umano, cioè lacapacità di vedere distinti due puntimolto vicini

Si fa in modo che l’algoritmo simuli latopologia della rete al variare delladistanza (fuzziness) e vedere comevariano le proprietà, identificando ilpunto in cui viene il cambiamento


Dalla teoria alla praticaSocial Network

Dalla teoria alla pratica


Riassunto metriche

Ricapitolando le metriche importanti sono:

〈k〉, P(k) (versioni in/out)

L, distanza di separazione media

C, indice di clusterizzazione

Eglob, efficienza globale

Eloc , efficienza locale

Costo

Costo/Eglob

knn(k)


Dalla teoria alla praticaReti analizzate e risultati ottenuti

Analisi di reti:

Sociali: Communities.com / VirtualTourist.comNeurali: Macaco / Gatto / C.elegansComunicazione: WWW ed internetTrasporto: Boston underground

Perturbation analysis


Dalla teoria alla praticaSocial Network

Graficamente difficili da rappresentare quando la taglia della rete ègrande

La rete non è connessa per cui le metriche L e C verranno calcolate sulcluster più grande.


Social NetworksRisultati

Rete |V | |E | 〈k〉 dmax L C

Communities 12.479 60.209 9.64 656 4.18 0.1067VirtualTourist 57.639 211.415 7.34 963 4.95 0.0442

C’è una certa relazione tra 〈k〉 e L. Più è grande il primo, più èprobabile che L sia basso perché ci saranno più connessioni

Un valore basso di L indica che con pochi passi si può andare da duequalsiasi zone remote della rete. Questo indica la presenza di diversiarchi di lungo raggio che collegano i cluster.

L’indice di clusterizzazione (C) è pari a 0.10, cioè ogni nodo (in media)avrà una rete di vicini che è collegata al 10%.


Social NetworksRisultati

Rete Eglob Eloc Cost Costo/Eglob

Communities 0.238 0.1314 0.0007 0.0032VirtualTourist 0.201 0.0562 0.0001 0.0006

Globalmente la rete funziona allo stesso modo; alti valori di E glob (danotare che è pari a 1 quando G è completo).

Localmente, VirtualTourist è meno connesso perché ha anche menoarchi (lo si vede dal costo!)

Se vediamo C/E , VT è la rete più economica ed efficiente allo stessotempo


Random Network

Rete Eglob Eloc dmax L C 〈k〉Communities 0.238 0.1314 656 4.18 0.1067 9.64Random 0.223 0.0007 22 4.46 0.0007 8

La topologia random si identifica subito dallo calcolo delle metriche

Assenza di nodi hub (grado max)Eloc bassissimaGrafico P(k)Grafico associatività

0

0.02

0.04

0.06

0.08

0.1

0.12

0.14

0 5 10 15 20 25

P(k)

k

Degree Distribution

degree

1

10

1 10 100

knn(k)

k

Network Correlation

knn

1

10

1 10 100

P(k)

k

Degree Distribution

degree


Network Correlation

Proprietà assortative/disassortative possono avere effetto sullatopologia della rete

Assortative tende a separare la rete in comunità (fig. a)

Disassortative: gli hub si collegano con nodi di grado basso (fig. b - retedi interazione tra proteine - yeast)


Neural NetworksConnessioni tra neuroni

Rete Eglob Erandomglob Eloc Erandom

loc Cost

Macaque 0.52 0.57 0.70 0.35 0.18Cat 0.69 0.69 0.83 0.67 0.38

Unweighted: alta efficienza globale e locale (fault tolerance) con uncosto contenuto, si utilizzano solamente 18% e 36% di tutti i possibiliarchi.

Eglob uguale rispetto alla versione random, mentre E loc più grande: ogniregione della corteccia celebrale è mescolata con il resto e ha seguitouna crescita a metà tra costo, fault tolerance e interazioni tra regioni


Neural NetworksConnessioni tra neuroni


loc Cost

C. elegans 0.46 0.48 0.47 0.12 0.06

Rete Eglob Eloc Cost

C. elegans (weighted) 0.35 0.34 0.18

Se confrontiamo la rete C. elegans, notiamo come il valore di E glob siauguale a quello di Eloc sintomo che la rete si comporta nello stessomodo sia globalmente che localmente

Essendo un multigrafo, il peso degli archi è dato dal reciproco delnumero di collegamenti


Communication NetworkWWW e Internet


loc Cost

WWW 0.28 0.28 0.36 0.000001 0.00002Internet 0.29 0.30 0.26 0.0005 0.006

Sebbene il WWW sia una rete virtuale mentre Internet fisica, a livelloglobale trasportano informazione allo stesso livello

A livello locale, la tendenza alla creazione di comunità nel caso delWWW, porta ad avere un valore di E loc più grande

Se confrontiamo i valori del Costo rispetto alle altre reti, vediamo comel’economicità è il principio base nella costruzione di reti di questo tipo.


Reti di trasporto


MBTA 0.63 0.03 0.002MBTA + bus 0.72 0.46 0.004

Molto efficiente globalmente (manca solo il37% per la rete ideale)

Povera localmente: non è fault tolerant. Undanneggiamento in una stazione provocauna forte diminuzione dell’efficienza tra lastazione precedente e la successiva.


Reti di trasporto


MBTA 0.63 0.03 0.002MBTA + bus 0.72 0.46 0.004

Costo molto basso: è il prezzo da pagareper la mancanza di ridondanza.

Non si considera la ridondanza durante lacostruzione perché la rete metropolitana èun sottosistema di uno che comprende altrereti come quella dei bus.


Network Failure

Removed Node E(G − nodei) ∆E/E k

1 New Jersey 0.1155 0.573 92 NYC 0.1270 0.530 93 Chicago 0.1947 0.280 154 Amsterdam 0.2051 0.241 95 Atlanta 0.2088 0.227 146 Washington 0.2152 0.203 2

Eglob originale è pari a 0.2701


Hijackers NetworkSeptember 2001


Hijackers NetwokSeptember 2001

Removed Node E(G − nodei) ∆E/E k

1 Mohamed Atta 0.4291 0.150 162 Salem Alhazmi 0.4484 0.112 83 Hani Hanjour 0.4554 0.098 104 Mamoun Darkazanli 0.4586 0.091 45 Marwan Al-Shehhi 0.4587 0.091 146 Nawaf Alhazmi 0.4611 0.203 9

Eglob originale è pari a 0.5047

Da notare come persone con grado molto basso (4) siano molto alte inclassifica


Campionamento

Abbiamo avuto la necessità, per ragioni computazionali, di limitare larete in questione e abbiamo deciso di effettuare un campionamentodella rete

Rete |V | |E | 〈k〉 dmax L C

VirtualTourist 57.639 211.415 7.34 963 4.95 0.0442VT Camp 1 10.000 22.262 4.45 243 5.77 0.0371VT Camp 2 10.000 21.441 4.28 187 5.79 0.0301

Rete Eglob Eloc Cost C/Eglob

VirtualTourist 0.201 0.0562 0.0001 0.0006VT Camp 1 0.173 0.0371 0.0004 0.0025VT Camp 2 0.172 0.0357 0.0004 0.0024


Campionamento

Con 1/6 dei nodi, L aumenta solamente del 16%. Anche C diminuiscedel 16%.

Efficienza globale e locale diminuiscono solo marginalmente

Il costo è aumentato perché togliendo una frazione dei nodi, noncorrisponde a togliere la stessa frazione degli archi.

P(k) rimane sostanzialmente inalterata


Campionamento

(a)

10^-5

10^-4

10^-3

10^-2

10^-1

10^0

10^0 10^1 10^2 10^3

P(k

)

k

degree distribution of vtCamp40k.net network

degree

(b)

10^-5

10^-4

10^-3

10^-2

10^-1

10^0

10^0 10^1 10^2 10^3

P(k

)

k


degree

(c)

10^-5

10^-4

10^-3

10^-2

10^-1

10^0

10^0 10^1 10^2 10^3

P(k

)

k


degree

(d)


Campionamento

10^-4

10^-3

10^-2

10^-1

10^0

10^0 10^1 10^2 10^3

P(k

)

k


degree

(e)

10^-4

10^-3

10^-2

10^-1

10^0

10^0 10^1 10^2 10^3

P(k

)

k


degree

(f)

Da notare come all’aumentare del numero di nodi eliminati, P(k) ha lastessa caratteristica

In un certo senso il campionamento rappresenta un network failure


Dalla teoria alla pratica

Q&A


Metodi matematici per l’analisi di sistemi complessi

Education

Transcript of Metodi matematici per l’analisi di sistemi complessi