1.Complex networks
Indice
•
•
•
•
Reti complesse e sistemi complessi
Esempi di reti reali complesse
Perchè complesse?
Alcune proprietà: Small World, Robustezza,
Resilienza.
• Che cosa ci possiamo chiedere a proposito
delle reti complesse?
• Storia della teoria delle reti complesse.
http://en.wikipedia.org/wiki/File:Complex_systems_organizational_
map.jpg
Non esiste una definizione esatta di sistema complesso ma molti
esempi:
In un sistema complesso semplici regole possono dare origine ad un
comportamento complesso (movimento di stormi di uccelli)
Il risultato è > della somma delle parti perché si deve aggiungere la
loro interazione.
Apparentemente i sistemi con proprietà emergenti o strutture
emergenti sembrano superare il principio entropico e
sconfiggere la seconda legge della termodinamica, in quanto
creano e aumentano l'ordine nonostante la mancanza di un
controllo centrale. Questo è possibile perché i sistemi aperti
possono estrarre informazione e ordine dall'ambiente. La
seconda legge della termodinamica in realtà si riferisce ad un
sistema chiuso: ….
http://it.wikipedia.org/wiki/Emergenza#Propriet.C3.A0_emer
genti
Le reti complesse possono essere considerate lo scheletro
dei sistemi complessi
Le reti sono ovunque…..
•
•
•
•
•
•
social network
organizational network
influence networks and key opinion leaders
contagion and disease networks
alumni & association networks
covert and criminal networks
Data Mining Email to Discover Social Networks and
Emergent Communities
Red, blue, or green: departments
Yellow: consultants
Grey: external experts
http://www.orgnet.com/email.html
“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”
Il forum del progetto ManMade
• La rete del progetto ManMade
Il progetto ManMade stesso è stato visto come
una rete di ricercatori di diverse istituzioni che
collaboravano tra loro su diverse Tasks.
• Network Analysis
Lo svolgimento del progetto è stato analizzato sulla
base delle informazioni salvate nel forum.
10
Topics and users k-cores
Forum from Nov 2007 to January 2009
The main k-core is composed
of individuals only.
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.
Collaboration Network
La visualizzazione di una rete può aiutare nella sua semplificazione
www.orgnet.com
9-11 Terrorist (?) Network
Connecting multiple pairs of
dots reveals an emergent
network of organization.
World-wide internet traffic. Kenneth C. Cox, Stephen
G. Eick, and Taosong He, 1996
Road and Airlines Network
-
-
Reti bipartite
Esempi:
Fornitori-magazzini (Trasporto)
Macchine-Jobs (assegnamento)
Attori-film
Autori-articoli
Direttori-consigli d’amministrazione
Lettori-giornali
Ricercatori-convegni
I nodi di un insieme sono in relazione grazie
a quelli dell’altro
Reti bipartite
Often these networks are converted
using a one-mode projection with fully
connected subgraphs.
Le reti 2-mode vengono proiettate per
poter usare le misere delle reti 1-mode
Image: Newman et al., PRE 64, 026118 (2001)
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
•Internet
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?
Cosa vuol dire che una rete è complessa?
Complessa=complicata?
I nodi di una stessa rete complessa 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
Fino ad ora sembra che complessa voglia dire complicata ovvero
che non siamo in grado di capire completamente il suo
funzionamento e quindi dovuta alla nostra ignoranza.
Ma allora nel momento in cui capiamo esattamente come funziona
una rete smette di essere complessa?
Esiste una definizione esatta di rete complessa?
Che caratteristiche deve avere una rete per essere considerata
complessa sia prima che dopo aver capito come funziona?
In letteratura si è cercato di definire la complessità a partire da una
rete statica con un solo tipo di nodi e di link (vedi figura di Solé)
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.
FIG. 3 A zoo of complex
networks. In this qualitative space,
three relevant characteristics are
included:
randomness, heterogeneity and
modularity.
The first introduces the amount of
randomness involved in the
process of network’s building. The
second measures how diverse is
the link distribution and the third
would measure how modular is
the architecture.
Non esiste una definizione esatta di rete complessa.
La figura di Solé ci aiuta a confrontare diversi tipi di
complessità.
Alcune caratteristiche riconosciute usualmente in
letteratura di una rete complessa sono
•Tra ordine e casualità
•grande
Alcune proprietà comuni delle reti reali complesse
•
•
•
•
•
Reti grandi: n grande
m dello stesso ordine di grandezza di n
Quindi la densità è in genere bassa
La distanza media molto piccola (Small World)
I gradi dei nodi hanno una distribuzione molto eterogenea
e quindi il grado medio non è significativo
The Small World Effect
Complex Network Theory – An Introduction
Niloy Ganguly
La proprietà di Small World
Anche se le reti sociali sono molto grandi, la distanza media tra i
nodi è breve.
Esperimento di Milgram, sociologo statunitense
• Persone obiettivo in Boston (Massachussetts)
• Mittenti in Omaha (Nebraska) e Wichita (Kansas),
• Ad ogni mittente è stato richiesto di inviare una lettera
direttamente all’obiettivo oppure ad un suo amico il più
possibile vicino all’obiettivo. Agli amici è stato chiesto di fare
lo stesso.
Risultato: Le persone erano separate da circa 6 passaggi (“six
degrees”)
S. Milgram, The small world problem, Psych. Today, 2 (1967), pp. 60-67.
Proprietà di robustezza ad attacchi casuali
Internet
•Robustezza rispetto ad attacchi
casuali
•Vulnerabilità rispetto ad attacchi
selettivi
Liljeros et al. Nature 2001
4781 Swedes; 18-74;
59% response rate.
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
Ruolo dei centri (hub)
La presenza di centri rende la rete più robusta ad attacchi casuali
La presenza di centri fa si che l’informazione si diffonda più
velocemente (ma anche virus biologici o informatici, etc)
Proprietà di clustering
«Gli amici dei miei amici
sono amici tra di loro»
Reti regolari=
Tutti i nodi hanno lo stesso grado
Alcune domande sulle reti reali
• Perchè le reti reali hanno certe proprietà? Perchè non sono random o
regolari?
• 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?
• Lo studio dell’anatomia della rete è importante perchè la struttura ne
determina il comportamento (e viceversa)
• 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 create dall’uomo
(elettriche, Internet) può aiutare ad individuarne i punti critici e
renderle più robuste ispirandosi ad esempio a quelle create dalla
natura.
Emergenza in natura
http://it.wikipedia.org/wiki/Emergenza#Strutture_emergenti_in_natura
•
•
•
•
“Le strutture emergenti sono più della somma delle loro parti, perché l'ordine
emergente non si forma se le varie parti coesistono solamente: è necessario che
interagiscano. “
“un esempio biologico è una colonia di formiche. La regina non dà ordini, né
dice alle formiche cosa fare. Ogni singola formica reagisce a stimoli, in forma di
odori chimici provenienti dalle larve, dalle altre formiche, da intrusi, cibo e
immondizia, e si lascia dietro una traccia chimica che, a sua volta, servirà da
stimolo alle altre. …. Nonostanze la mancanza di un ordine centralizzato, le
colonie di formiche esibiscono un comportamento complesso ed hanno
dimostrato la capacità di affrontare problemi geometrici. Ad esempio,
localizzano un punto alla distanza massima da tutte le entrate della colonia per
disporvi i corpi morti. “
Altri esempi si trovano nei comportamenti di animali che vivono in gruppo:
lupi, uccelli.
La coscienza è un fenomeno emergente?
Storia 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 solo occhio dal 1738 e
completamente cieco dal 1766
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
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à delle reti regolari
cioè in cui tutti i nodi hanno lo stesso grado. Ad esempio i lattici
in cui tutti i nodi sono anche legati ai loro vicini
Paul Erdos (Budapest 1913-Varsavia 1996)
• Paul Erdos ha dato importanti contributi alla teoria dei grafi
ma anche alla teoria della probabilità, etc.
• Scrisse 1475 articoli e collaborò con 511 scienziati
• Era una persona eccentrica
• 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à p
Reti random
Il modello di rete Small World di Watts-Strogatz
Watts e Strogatz nel 1998 hanno proposto un modello che concilia la
proprietà di alto clustering con quella di distanza media corta.
A partire da un lattice ad anello si ricollegano i link con una certa
probabilità p
Lattice= rete regolare (tutti i nodi hanno lo stesso grado) ed
inoltre sono collegati ai loro vicini
Il modello di Watts-Strogatz
Reti Scale free
• Tuttavia il modello SW non spiega come le reti arrivano ad avere
questa proprietà.
• 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.
Pajek 1.28
http://vlado.fmf.uni-lj.si/pub/networks/pajek/
Software for Social Network Analysis
It allows the visualization and the study of networks
Adobe SVG Viewer 3.03
http://www.adobe.com/svg/viewer/install/mainframed.html
SVG è una tecnologia che permette di visualizzare oggetti grafici vettoriali
Le figure espresse mediante SVG possono essere dinamiche e interattive.
Octave-3.2.4
http://www.gnu.org/software/octave/
GNU Octave è un linguaggio free ad alto livello per il calcolo numerico.
Il linguaggio è compatibile con Matlab.
Alternative a Matlab
http://www.dedoimedo.com/computers/scientific.html
Scilab
FeeMat
Etc..
File .m per il calcolo di misure di reti (G. Bounova)
http://www.mit.edu/~gerganaa/download.html
Introduzione ad OCTAVE
Esercizi Pajek:
Costruire una rete con Pajek e visualizzarla
Reti libro pajek
Esercizi Octave:
aprire e lanciare un m.file
Inserimento e calcoli con matrici e vettori
grafici