Reti Complesse
Indice
• Sistemi complessi e reti complesse
• Esempi di reti reali complesse
• Alcune proprietà: Piccolo mondo,
Clustering, Centri.
• Storia della teoria delle reti complesse.
Sistemi Complessi
Gli scienziati guardando qualcosa cercano di capire come riesce a fare
ciò che fa ovvero il suo funzionamento….
Una delle osservazioni più importanti nella storia della scienza è che
ogni cosa è fatta di parti e quindi sembra ragionevole cercare di
capire come funziona ogni singola parte.
Poi si scopre che ogni parte è a sua volta fatta di parti e allora si
cerca di capire il funzionamento delle singole parti e così via…fino a
dimenticare l’oggetto principale dello studio iniziale, il tutto.
Es: corpo umano sistema nervoso, scheletrico, ecc. organi
molecole atomi particelle elementari.
Per poi scoprire che anche le piante e le rocce sono fatte dalle stesse
particelle elementari.
Le parti possono essere universali ma il modo in cui interagiscono
è specifico di ogni sistema.
Per capire come un sistema sia in grado di fare quello che fa è
importante capire la relazione tra le parti (sguardo sistemico)
A volte il problema (se c’è) non è nelle parti ma nella loro
relazione (esempio Beer Game)
La teoria dei sistemi complessi è il nuovo (dagli anni ‘80 in poi)
approccio della scienza per studiare come le relazioni tra le parti
possono dare origine a comportamenti collettivi: il tutto è più
delle parti
ES: sistemi sociali formati da relazioni tra individui, cervello
formato da relazioni tra neuroni.
Complesso non vuol dire complicato
Un sistema si dice complesso proprio quando il tutto è più
della somma delle parti ovvero quando emergono proprietà
dovute all’interazione tra le parti che le singole parti non
hanno (ad esempio la mente umana)
Un sistema si dice complicato invece quando il suo
funzionamento si può comprendere dal funzionamento delle
singole parti (esempio: un’automobile, un orologio svizzero,
una navicella schuttle, etc..)
A partire dagli anni 80 si è incominciato a studiare la realtà dal
punto di vista sistemico riconoscendo in alcuni sistemi dei
fenomeni emergenti non spiegabili dal comportamento delle
singole parti
La rappresentazione di un sistema complesso come
rete aiuta a comprenderne il comportamento.
RETE
un insieme di punti e di linee che li connettono
Esempi
•
•
•
•
Reti di organizzazioni
Reti di contagio
Reti di attività (PM): Critical Path Method
Reti di citazioni
Email data Mining to discover social networks and
emergent communities
Red, blue, or green: departments
Yellow: consultants
Grey: external experts
“Social graph of the email flows amongst a large project
team. In addition to the network visualizations, network
metrics were generated to see how well the various
departments and groups were interacting. The diagram shows
the project network soon after the missed deadline. Several
of the hubs in this network were under-performing and often
came across as bottlenecks. Project managers saw the need
for more direct integration between the departments (more
project team members). This intervention improved the
information flow, and reduced the communication load on
the hubs, whose performance improved later in the project”
http://www.orgnet.com/email.html
Rete del progetto ManMade
Forum from Nov 2007 to January 2009
The highest ranked topic is
T1.4 (meetings).
Most topics are on the
periphery indicating that
interaction of these topics
amongst users has yet to
start.
E-mail data from
forum
Rete nascosta
rete di terroristi dell’attentato
dell’11 settembre 2001
9-11 Terrorist (?) Network
Connecting multiple pairs of
dots reveals an emergent
network of organization.
www.orgnet.com
Rete delle collaborazioni scientifiche
http://www.visualcomplexity.com
http://orgnet.com/
http://diseasome.eu/map.html
Reti di trasporti
-
Trasporti stradali
Trasporti aerei
Reti (catene) alimentari
Reti bipartite/2-mode networks
Esempi:
Fornitori-clienti (Trasporto)
Macchine-Jobs (assegnamento)
Autori-articoli
Direttori-consigli d’amministrazione
Ricercatori-convegni
I nodi di un insieme sono in relazione
grazie a quelli dell’altro
….
Altri esempi di reti reali: naturali o manmade
Social networks:
•Collaboration networks of researchers
•Phone calls networks
•E-mail networks
Technological networks
•Electric power grid
•Railways
•Road networks
Information networks
•Citation networks between academic papers
•World Wide Web
Biological networks
•Food web
•Neural networks
La struttura risultante da reti di diverso tipo (persone, proteine,
connessioni internet) a volte è simile.
E’ una rete sociale, tecnologica o
biologica?
Il funzionamento del sistema si può
dedurre dalla sua struttura?
Quali sono i nodi più importanti per il
funzionamento del sistema?
• La struttura di una rete ne determina il comportamento (e viceversa)?
• Come si sono formate le reti reali? Sono state create da un essere supremo
intelligente o sono emerse da semplici leggi che governano le loro
componenti?
• Possiamo costruire reti simili artificialmente?
• Conoscere la struttura delle reti sociali può aiutare a prevenire la
diffusione delle malattie o controllare la diffusione dell’informazione?
• Studiare la struttura delle reti tecnologiche (elettriche, Internet) può
aiutare ad individuarne i punti critici e renderle più robuste ispirandosi ad
esempio alla struttura delle reti naturali?.
Reti Reti Complesse
I nodi di una rete possono essere di diverso tipo e nodi dello
stesso tipo avere diversi stati
FRES1010
Complex Adaptive Systems
Eileen Kraemer
Fall 2005
Gli archi possono essere di diverso tipo e avere stati
differenti
Diverso colore
Diverso spessore
FRES1010
Complex Adaptive Systems
Eileen Kraemer
Fall 2005
Le reti complesse possono evolvere
FRES1010
Complex Adaptive Systems
Eileen Kraemer
Fall 2005
Esiste una definizione esatta di rete complessa?
Che caratteristiche deve avere una rete per essere considerata
complessa?
In letteratura si è cercato di definire la complessità a partire da una rete
statica con un solo tipo di nodi e di link (Solé, 2004)
A complex network is a network with non-trivial topological features, with patterns of
connection between their elements that are neither purely regular nor purely random.
•Randomness: come
evolve la rete;
•Heterogeneity: come
sono distribuiti i gradi dei
nodi
•Modularity: presenza di
comunità
Non esiste una definizione esatta di rete complessa.
La figura di Solé ci aiuta a confrontare diversi tipi di
complessità quindi sembra dire che la complessità è un
concetto relativo e non assoluto.
Una rete complessa
•E’ una rete intermedia tra una completamente ordinata
ed una completamente casuale.
• Ha una struttura (modularità)
•E’ eterogenea: ci sono nodi con grado molto alto ed
altri con grado molto basso.
Alcune proprietà comuni delle reti reali complesse
• Reti con tanti nodi: n grande
• Numero di link m dello stesso ordine di grandezza di n
Quindi la densità è in genere bassa
• La distanza media è molto piccola. Esperimento di
Milgram e proprietà di Piccolo Mondo (Small World
property).
• Sottoinsiemi molto connessi (alto clustering; modello di
Watts e Strogatz)
• I gradi dei nodi hanno una distribuzione eterogenea. Sono
presenti pochi nodi con grado molto alto e molti con grado
basso (presenza di centri, reti Scale Free)
La proprietà di Piccolo Mondo (Small World)
Esperimento di Milgram (sociologo statunitense)
(New York 1933-New York 1984)
•
Ad un certo numero di persone in Omaha (Nebraska) e Wichita (Kansas) è
stato chiesto di inviare delle lettere a persone obiettivo (in generale sconosciute)
a Boston (Massachussetts).
•
Ad ogni mittente è stato chiesto di inviare la lettera direttamente
all’obiettivo, se conosciuto, oppure ad un suo amico il più possibile vicino
all’obiettivo. Agli amici era stato chiesto di fare lo stesso.
Risultato: le lettere che hanno raggiunto l’obiettivo l’ hanno fatto in meno di 6
passaggi (“six degrees”) da qui la conclusione che nelle reti sociali la distanza
media tra i nodi è piccola ovvero vale la proprietà di Piccolo Mondo
S. Milgram, The small world problem, Psych. Today, 2 (1967), pp. 60-67.
PresidenteObama
Repubblica
Rettore
LIUC
CRUI
Ministro
io
Implicazioni della proprietà di Small World
Proprietà di alto clustering (presenza di
sottogruppi più connessi)
Le reti reali oltre alla proprietà di Piccolo Mondo hanno
anche la proprietà di avere un alto clustering:
Ad esempio in una rete Facebook (ego-network): i miei
amici sono spesso amici tra di loro
io
La proprietà di Alto Clustering è spesso presente nelle reti
sociali insieme a quella di Piccolo Mondo
l=distanza media tra i nodi
C=clustering
Costruzione di una rete Small World con Alto
Clustering (modello di Watts-Strogatz)
Watts e Strogatz nel 1998 hanno proposto un modello che concilia la
proprietà di Alto Clustering con quella di Piccolo Mondo.
A partire da un lattice ad anello si ricollegano i link con una certa
probabilità p
Rete Random: distanza
media bassa e
clustering basso
Rete Lattice: Distanza
media alta e clustering alto
Rete Small World: distanza
media bassa e clustering
alto
Lattice= rete regolare (tutti i nodi hanno lo stesso grado) ed
inoltre sono collegati ai loro vicini.
Le reti reali oltre ad essere Piccolo Mondo e avere
Alto Clustering hanno anche centri:
reti Scale Free
• Molte reti reali mostrano la proprietà del “rich get richer” e
quindi pochi nodi con alto grado e tanti con basso grado e di
conseguenza disomogeneità nella distribuzione dei gradi dei nodi.
• Come possiamo generare una rete con queste proprietà?
• Introducendo il meccanismo del “Preferential Attachement”
Barabasi et Albert (1999).
Si parte da una rete random iniziale e si aggiungono nodi che si
collegano in modo preferenziale, ovvero con probabilità maggiore,
a nodi con alto grado.
Random/Small World
Scale free
Implicazioni della presenza di centri (hub)
•Robustezza rispetto ad attacchi casuali
•Vulnerabilità rispetto ad attacchi selettivi
9-11 Terrorist (?) Network
?
La vulnerabilità ad attacchi
selettivi può essere una
proprietà desiderata: come si
possono condurre le indagini in
una rete nascosta?
Complex Network Theory – An Introduction
Niloy Ganguly
Storia dello sviluppo della teoria delle reti complesse
Leonard Euler
(Basilea 1707-San Pietroburgo 1783)
• Eulero ha lavorato in quasi tutte le aree della matematica:
geometria, calcolo, trigonometria, algebra, teoria dei
numeri ed in diverse aree della fisica.
•
Tutto il suo lavoro è raccolto nell’ Opera Omnia, che
consiste in 886 libri.
• Ha lavorato vedendo
da un occhio solo dal 1738
e completamente cieco dal 1766.
Problema dei 7 ponti di Konigsberg
Konisberg "Collina del re“. Nome portato fino al 1946 dalla città
capoluogo della Prussia Orientale, poi annessa all'URSS e
chiamata Kalininingrad.
Problema dei 7 ponti di Konigsberg
E’ possibile attraversare tutti i ponti una volta sola?
Con la soluzione di questo problema Eulero fonda la teoria dei grafi (e delle reti)
N0=4 no sol
Soluzione di Eulero: N0=numero di nodi con grado dispari
1. Se N0>2 non ci sono soluzioni
2. Se N0=2, esiste solo una soluzione a partire da un nodo di grado dispari
3. Se N0<2 ci sono soluzioni a partire da qualsiasi nodo
Grafi Regolari
• Dopo la morte di Eulero la teoria dei grafi ha ricevuto contributi
da altri importanti matematici quali: Hamilton, Kirchhoff,
Cayley
• Gli studi si sono concentrati sulle proprietà dei grafi regolari
cioè in cui tutti i nodi hanno lo stesso grado. Ad esempio i lattici
in cui tutti i nodi sono legati ai loro vicini.
Grafi Random
Paul Erdos (Budapest 1913-Varsavia 1996)
• Paul Erdos dette importanti contributi alla
teoria dei grafi
• Lavorò insieme a Alfred Renyi sull’analisi
delle reti sociali trovando delle analogie con i
grafi random (in cui l’esistenza di un link tra
una coppia di nodi ha probabilità costante p)
• Scrisse 1475 articoli e collaborò con 511
scienziati.
• Era una persona eccentrica
Esempio di Rete random
Software
Pajek 3.13
http://mrvar.fdv.uni-lj.si/pajek/
Software per la Social Network Analysis
VOS viewer
http://www.vosviewer.com/
Per costruire la propria rete Facebook:
NodeXL Template 2014
http://nodexl.codeplex.com/
Social net Importer
http://socialnetimporter.codeplex.com/