COMPORTAMENTI LOCALI E
FENOMENI GLOBALI
Vincenzo Auletta
STRUTTURA DELLE RETI SOCIALI
COMPORTAMENTI LOCALI E FENOMENI
GLOBALI
Le network sono uno strumento utilissimo per
descrivere il rapporto tra i comportamenti locali dei
singoli ed i fenomeni globali che si verificano in una
popolazione
Come l’informazione viaggia nella rete?
Come diversi archi possono svolgere funzioni diverse
nella diffusione delle infromazioni?
Come in una rete sociale diversi nodi possono svolgere
ruoli distinti e come fare a riconoscerli?
Come questi processi condizionano l’evoluzione della rete
nel tempo?
Au
tun
no 2
01
2
1
Stru
ttura
delle
Reti S
ocia
li
ESPERIMENTO DI GRANOVETTER (1970)
Granovetter per la sua tesi di dottorato intervistò
numerose persone che avevano appena trovato
lavoro per come erano venuti a conoscenza
dell’offerta di lavoro
Nella maggior parte dei casi da contatti personali
Più spesso da conoscenti che da amici
Conclusione sorprendente
Gli amici dovrebbbero essere quelli che più ci tengono ad
aiutare e fornire notizie utili
Perché i conoscenti sono più utili nella ricerca di un
nuovo lavoro?
Au
tun
no 2
01
2
2
Stru
ttura
delle
Reti S
ocia
li
TESI DI GRANOVETTER
Due diversi modi di vedere l’amicizia
A livello locale
L’amicizia può essere forte o debole
A livello globale
L’amicizia può legare due nodi vicini o lontani nella rete
Spiegazione di Granovetter
Le informazioni viaggiano sui link che collegano parti
diverse della rete
Questi link tendono a rappresentare amicizie deboli
Teoria della “Strength of Weak Ties”
Au
tun
no 2
01
2
3
Stru
ttura
delle
Reti S
ocia
li
TRIADIC CLOSURE
In una rete sociale se due nodi hanno un amico in
comune hanno buone probabilità di diventare amici
in futuro
Motivazioni sociologiche
I due nodi hanno maggiori occasioni di incontrarsi e
frequentarsi
Se hanno un amico comune tendono a fidarsi dell’amico
e ad accettare l’altro
L’amico comune tende a favorire la loro amicizia per non
doversi dividere tra i due
Au
tun
no 2
01
2
4
Stru
ttura
delle
Reti S
ocia
li
B C
A
COEFFICIENTE DI CLUSTERIZZAZIONE
Se osserviamo l’evolversi di una rete sociale nel
tempo noteremo la tendenza alla chiusura di tutti i
triangoli
Coefficiente di clusterizzazione
Probabilità che due nodi scelti a caso tra gli amici di un
nodo siano amici tra loro
Più è forte la triadic closure maggiore sarà il coefficiente
di clusterizzazione
Bearman e Moody hanno scoperto empiricamente
che ragazze con basso coefficiente di
clusterizzazione sono più propense al suicidi
Au
tun
no 2
01
2
5
Stru
ttura
delle
Reti S
ocia
li
FORZA DEL LEGAME
Secondo Granovetter il legame interpersonale può
essere di tue tipi
strong: amicizia
weak: conoscenza
Proprietà locale
Proprietà della Strong Triadic Closure
Ipotesi operativa di Granovetter
Se A ha legami strong con B e C allora con alta
probabilità c’è un’amcicizia tra B e C
Può essere strong o weak
Au
tun
no 2
01
2
6
Stru
ttura
delle
Reti S
ocia
li
B C
A
S S
S o W
BRIDGE
Un bridge è un arco che collega due componenti
distinte della rete
Proprietà globale della rete
Un bridge è un arco che non appartiene ad un
triangolo
In una rete sociale i bridge sono rari
Au
tun
no 2
01
2
7
Stru
ttura
delle
Reti S
ocia
li
B
A
C
D
F
E
G
H bridge
LOCAL BRIDGE
Un local bridge è un arco che riduce la distanza tra una coppia di nodi
Svolge funzione simile al bridge
Proprietà globale della rete
Au
tun
no 2
01
2
8
Stru
ttura
delle
Reti S
ocia
li
Lo span di un local
bridge è la distanza tra i
suoi estremi se
togliessimo l’arco
Maggiore lo span più
importante il ruolo di
coesione dell’arco
B
A
C
D
F
E
G
H local
bridge
I L
M N O
Span = 4
STRENGTH OF WEAK TIES
Assumiamo la Strong Triadic Closure
Se un nodo ha almeno due strong ties allora ogni local bridge a cui è adiacente è un weak tie
Au
tun
no 2
01
2
9
Stru
ttura
delle
Reti S
ocia
li
• Quindi
Se la rete ha un numero sufficiente di strong ties allora ogni local bridge è un weak tie
Le informazioni cruciali viaggiano sui weak tie
Collega una proprietà globale (local bridge) ad un comportamento locale (strength of tie)
B
C A
l.b.
• Sia AB un local bridge
• AB e BC strong ties
• BC non può esistere perchè AB non può stare in un triangolo
• BC esiste per STC -- CONTRADDIZIONE
• Quindi AB non può essere uno strong tie
FORZA DEI LEGAMI IN DATA-SET REALI
Per molti anni non si è potuto verificare le teorie di Granovetter su network di grandi dimensioni e in contesti realistici Mancanza di dati concreti
Oggi abbiamo dati per reti “who-talks-to-whom” di grandi dimensioni Facebook, social networks, tabulati telefonici, email
Onnela e al. 2007 Dati di un provider di telefonia cellulare che copriva il 20%
della popolazione statunitense
Periodo di osservazione 18 settimane
Due utenti sono collegati se hanno scambiato almeno una telefonata in entrambe le direzioni
La forza del legame è misurata dal numero di minuti di comunicazione
Au
tun
no 2
01
2
10
Stru
ttura
delle
Reti S
ocia
li
NEIGHBORHOOD OVERLAP
Neighborhood overlap di A e B ( NO(A, B) )
NO(A, B) = #(vicini comuni ad A e B)/ #(vicini ad A o B)
Se AB è un local bridge NO(A, B) = 0
Nodi con piccolo neighborhood overlap sono “quasi” dei
local bridge.
Au
tun
no 2
01
2
11
Stru
ttura
delle
Reti S
ocia
li
B
A
C
D
F
E
G
H
I L
M N O
0
1/6
1/4
RISULTATI EMPIRICI SU FORZA DEI LEGAMI
E NEIGHBORHOOD OVERLAP
Conferma la connessione tra la forza dei legami
(locale) e la neighborhood overlap (globale)
Au
tun
no 2
01
2
12
Stru
ttura
delle
Reti S
ocia
li
Archi ordinati in
maniera decrescente per
forza del legame
Ad ogni arco è assegnato
il suo percentile
IPOTESI DI ONNELA ET AL.
La rete è fatta da comunità densamente legate da
legami forti collegate da legami deboli
I legami deboli svolgono un ruolo fondamentale nel
tenere unita la comunità
Esperimento:
1. Cancella gli archi uno alla volta in ordine decrescente
di forza
La dimensione della componente gigante diminuisce
gradualmente
2. Cancella gli archi uno alla volta in ordine crescente di
forza
1. La dimensione della componente gigante diminuisce molto
più velocemente
Au
tun
no 2
01
2
13
Stru
ttura
delle
Reti S
ocia
li
FORZA DEI LEGAMI NEI SOCIAL NETWORKS
L’utilizzo sempre più diffuso dei social networks
come ha modificato il comportamento degli utenti?
Numerosi esperimenti condotti su principali social
networks (facebook, twitter)
Gli utenti di un social network tendono ad avere
molti più contatti ma con minor forza dei legami
Molto diffuso il fenomeno del passive engagement
una persona ne segue un’altra attraverso le notifiche ma senza
mantenere contatti diretti
Le informazioni fluiscono molto più velocemente
Au
tun
no 2
01
2
14
Stru
ttura
delle
Reti S
ocia
li
RUOLO DEI NODI IN UNA SOCIAL NETWORK
La discussione precedente ha riguardato gli archi
della rete
Archi diversi svolgono ruoli differenti
E per i nodi?
Possiamo individuare ruoli diversi dei nodi a seconda
della loro posizione nella rete?
Au
tun
no 2
01
2
15
Stru
ttura
delle
Reti S
ocia
li
EMBEDDEDNESS E STRUCTURAL HOLES
Embeddedness di un arco AB = #(vicini comuni ad A e B) È il numeratore della funzione di neighborhood overlap
Un local bridge ha embeddedness nulla
La fiducia tra i due nodi adiacenti cresce con l’embeddedness dell’arco che li unisce
Se un nodo è adiacente ad archi con alta embeddedness ha più facilità di relazione e maggiore fiducia nei suoi vicini
Uno structural hole indica l’assenza di connessioni tra due aree della rete Tali buchi sono coperti dai local bridge
Un nodo adiacente ad uno structural hole può avere dei vantaggi dalla sua posizione Controlla il passaggio delle informazioni
Conosce le cose prima degli altri
Au
tun
no 2
01
2
16
Stru
ttura
delle
Reti S
ocia
li
UN ESEMPIO A
utu
nn
o 2
01
2
17
Stru
ttura
delle
Reti S
ocia
li
A è circondato da archi con alta embeddedness È incluso in una comunità molto coesa
B, C e D si trovano su uno structural hole
Controllano tutte le interazioni tra le varie comunità
CENTRALITÀ DI UN NODO
Misura il ruolo svolto dal nodo nella rete
Diverse misure di centralità legate a aspetti diversi
della rete
Degree centrality
Closeness centrality
Betweenness centrality
Eigenvector centrality
Definite in modo da fornire un valore in [0, 1]
Misurano l’”importanza” del nodo
Au
tun
no 2
01
2
18
Stru
ttura
delle
Reti S
ocia
li
DEGREE CENTRALITY
Degree centrality di z
grado(z)/(n-1)
Misura l’importanza di un nodo in base al numero dei
suoi vicini
Au
tun
no 2
01
2
19
Stru
ttura
delle
Reti S
ocia
li
B
E C
A
D
G
F 1/3
1/3
1/2 1/2 1/3
1/3
1/3
CLOSENESS CENTRALITY
Closeness centrality di z
(n-1)/∑u≠zd(u,z)
Inverso della distanza media
Misura la velocità con cui un nodo viene
raggiunto/raggiunge da tutti gli altri
Au
tun
no 2
01
2
20
Stru
ttura
delle
Reti S
ocia
li
B
E C
A
D
G
F 6/15
6/15
6/11 6/11 3/5
6/15
6/15
CLOSENESS CENTRALITY CON PARAMETRO
DI DECADIMENTO
Per far pesare di più i collegamenti con i nodi vicini
si può definire la centrality usando un parametro di
decadimento 0 < < 1
∑u≠zd(u,z)
Pesa maggiormente in nodi vicini
Per 1 tende alla dimensione della componente in
cui si trova il nodo
Per 0 tende al grado
Au
tun
no 2
01
2
21
Stru
ttura
delle
Reti S
ocia
li
BETWEENESS CENTRALITY
Betweenness centrality di z
2 / (n-1)(n-2) ∑u≠v, z ≠ u,v Pz(u,v) / P(u,v)
P(u,v) = # cammini minimi tra u e v
Pz(u,v) = # cammini minimi tra u e v passanti per z
Misura quanto il nodo z è cruciale per la comunicazione
tra tutte le coppie di nodi
Au
tun
no 2
01
2
22
Stru
ttura
delle
Reti S
ocia
li
B
E C
A
D
G
F 0
0
8/15 8/15 9/15
0
0
EIGENVECTOR CENTRALITY
Misura l’importanza di un nodo in funzione
dell’importanza dei suoi vicini
Cosa vi ricorda?
Cz(G) = ∑u≠z G u,z Cu(G)
In forma matriciale C(G) = G C(G)
C(G) è un autovettore per G e è l’autovalore corrispondente
Scegliamo l’autovalore più grande che per le reti considerate è
sempre nonnegativo
Au
tun
no 2
01
2
23
Stru
ttura
delle
Reti S
ocia
li
GRAPH PARTITIONING
Dalla discussione precedente ricaviamo un’idea di struttura di una rete sociale Un insieme di comunità fittamente connesse legate insieme da
legami occasionali
Definizione volutamente informale
Come possiamo individuare le aree fittamente connesse Identificare le comunità della rete è vitale per gli esperti di
marketing
Problema algoritmico non banale
Numerosi metodi euristici per il graph partitioning Metodi agglomerativi
Si parte dai singoli e si cerca di aggregarli in gruppi
Metodi divisivi
Si parte dalla rete in generale e si cerca di dividerla in sottoreti connesse in modo sparso tra loro
Au
tun
no 2
01
2
24
Stru
ttura
delle
Reti S
ocia
li
UN ESEMPIO DI PARTIZIONAMENTO DI UNA
RETE IN COMUNITÀ Au
tun
no 2
01
2
25
Stru
ttura
delle
Reti S
ocia
li
GRAPH PARTITIONING PER DIVISIONE
Basta individuare i local bridge?
No
Au
tun
no 2
01
2
26
Stru
ttura
delle
Reti S
ocia
li
Possibile soluzione
Calcoliamo la betweenness degli archi
Gli archi con alta betweenness sono quelli su cui passa la maggior parte dell’informazione
GRAPH PARTITIONING PER DIVISIONE
Algoritmo di Girvan-Newman
1. Trova gli archi con più alta betweeness e rimuovili dal
grafo
Se il grafo si divide in più componenti hai trovato le regioni in
cui si divide il grafo
2. Ricalcola la betweeness di ogni arco e torna a passo 1
Se una componente si divide in sottocomponenti queste sono
le regioni annidate nella regione padre
3. Procedi fin quando rimangono archi nel grafo
L’algoritmo può essere adattato per calcolare
anche la betweenness dei nodi
Au
tun
no 2
01
2
27
Stru
ttura
delle
Reti S
ocia
li
ESEMPIO A
utu
nn
o 2
01
2
28
Stru
ttura
delle
Reti S
ocia
li
CALCOLO DELLA BETWEENNESS DEGLI
ARCHI
L’algoritmo di Girman-Newman ad ogni passo deve
ricalcolare la betweenness di tutti gli archi
rimanenti nel grafo
Dipende dal numero di cammini minimi tra ogni coppia
di nodi
Si può fare efficientemente?
Idea
Utilizziamo una BFS da ogni nodo u
Calcoliamo come un’unità di flusso si distribuisce nella
rete a partire da un nodo u
Au
tun
no 2
01
2
29
Stru
ttura
delle
Reti S
ocia
li
ALGORITMO PER IL CALCOLO DELLA
BETWEENNESS
Algoritmo
1. A partire da ogni nodo u esegui una BFS e costruisci l’albero dei percorsi minimi
2. Per ogni nodo v, calcola quanti cammini minimi ci sono da u a v Se il nodo v si trova al k-imo livello dell’albero i cammini
minimi da u a v hanno lunghezza k e passano per i padri di v nell’albero
Il numero dei cammini minimi per v è la somma del numero di cammini minimi per i suoi padri
3. Determina quanto flusso attraversa ogni arco del grafo Bottom up
Ad ogni nodo assegna un’unità di flusso più tutto quello che gli arriva dai figli
Ogni nodo distribuisce equalmente il proprio flusso tra i padri
Au
tun
no 2
01
2
30
Stru
ttura
delle
Reti S
ocia
li
ESEMPIO A
utu
nn
o 2
01
2
31
Stru
ttura
delle
Reti S
ocia
li
La rete
L’albero della BFS da A
ESEMPIO A
utu
nn
o 2
01
2
32
Stru
ttura
delle
Reti S
ocia
li
Numero di
cammini
minimi da A Flusso
sull’arco
EFFICIENZA DELL’ALGORITMO DI GIRMAN-
NEWMAN
L’algoritmo richiede di ricalcolare ad ogni passo la
betweenness di tutti gli archi
Non scala per reti di grandi dimensioni
Approcci alternativi
Approssimazione della betweenness
Utilizzo di algoritmi alternativi di graph partitioning
basati sia su approccio agglomerativo che divisivo
E’ un argomento di ricerca attiva in questo
momento
Au
tun
no 2
01
2
33
Stru
ttura
delle
Reti S
ocia
li
Top Related