Post on 19-Jan-2019
transcript
Tecniche
Social Network
Analysis (SNA)
e applicazioniDott. Marco Stella
CIFI
Seminario IISFA – Social Network Analysis
Casa dell’Aviatore
Roma, 21 aprile 2017
Agenda
2
• Introduzione alla SNA
• Reti: definizioni e proprietà
• Uso della SNA nell’analisi criminale
• Simulazioni con Gephi
• Esercitazione pratica con Gephi
Introduzione
Una possibile definizione…
… l’analisi delle reti sociali o anche teoria della retesociale, è una moderna metodologia di analisi dellerelazioni sociali sviluppatasi a partire dai contributi diJacob Levi Moreno, il fondatore della sociometria,scienza che analizza le relazioni interpersonali.
In realtà le origini della SNA possono essere ricollocatecon la nascita della teoria dei grafi…ma questa èun’altra storia!
3
Introduzione
La SNA (dall’inglese Social NetworkAnalysis) trova ora applicazione in diversescienze sociali:
- Sociologia
- Antropologia
- Economia
- Management
- Commercio internazionale
- Diffusione dell’informazione
- Studio delle istituzioni
- Funzionamento delle organizzazioni 4
IntroduzioneLa SNA ha trovato inoltre di recente diverseapplicazioni in:
- Fisica
- Biochimica
- Genetica
- Computer science
- Criminologia
pur mantenendo convenzionalmente l’appellativo«social», a ricordo della sua origine.
L’analisi dell’uso del termine SNA nellaletteratura scientifica mostra negli ultimi anniuna crescita esponenziale del ricorso a questamodalità di rappresentazione computabile deifenomeni complessi ed interdipendenti.
5
Introduzione
COMPLEX NETWORKS 2017
6th International Conference on Complex Networks and Their Applications – Lyon (France)
Nov 29, 2017 – Dec 1, 2017
http://www.complexnetworks.org/
COMPLEX NETWORKS 2016
5th International Workshop on Complex Networks and their Applications – Milan (Italy)
Nov 29, 2016 – Dec 2, 2016 6
COMPLEX NETWORKS 2015
The fourth International Workshop on Complex Networks and their Applications
– Bangkok, Thailand
November 23-27, 2015
COMPLEX NETWORKS 2014
Third International Workshop on Complex Networks and their Applications
– Marrakesh, Morocco
November 23-27, 2014
COMPLEX NETWORKS 2013
Second Workshop on Complex Networks and their Applications – Kyoto, Japan,
December2-5, 2013
COMPLEX NETWORKS 2012
International Workshop on Complex Networks and their Applications –
Sorrento – Naples, Italy
November 25-29, 2012
IntroduzioneARGOMENTI PRINCIPALI
• Models of Complex Networks
• Structural Network Properties
• Complex Networks and Epidemics
• Community Structure & Discovery
• Motif Discovery
• Complex Networks Mining
• Dynamics on and of Complex Networks
• Link Prediction
7
• Multiplex Networks
• Network Controllability
• Synchronization in Networks
• Algorithms for Network Analysis
• Networks Visual Representation
• Large-scale Graph Analytics
• Social Reputation, Influence, and Trust
• Information Spreading in Social Media
• Rumor and Viral Marketing
• Recommendation Systems and Networks
• Financial and Economic Networks
• Complex Networks and Mobility
• Biological and Technological Networks
• Mobile call Complex Networks
• Political networks
Introduzione
Nella teoria delle reti sociali la società è vista e studiatacome rete di relazioni, più o meno estese e strutturate.Il presupposto fondante è che ogni attore si relazionacon gli altri e questa sua interazione plasma e modificail comportamento di entrambi.
Lo scopo principale dell’analisi di un network èappunto quello di individuare e analizzare tali legami tragli «individui» (nodi).
In sintesi, l’oggetto di studio della SNA è una rete… 8
Introduzione
Una possibile definizione di RETE può essere:
“Intreccio di linee, reali o ideali, che
s’incrociano, cui ci si riferisce per indicare un
sistema di collegamenti o di comunicazioni
oppure una struttura complessa articolata in
più punti”.
Vi sono però nuovi spunti di riflessione … 9
10
Introduzione
• Crescente importanza delle attività di relazione
• Fattori che spingono alla formazione di reti
• Si fa «rete» per ampliare gli obiettivi di business
• Il networking è rischioso
• Occorre uno sforzo per gestire le reti
11
Introduzione
In un mondo che diventa sempre più
«connesso» è importante comprendere:
• i meccanismi e le leggi generali che
permettono una trasmissione efficiente
delle informazioni, dell’energia o altro;
• cosa può rendere vulnerabile una rete.
12
Introduzione
Inizialmente le reti si svilupparono a solo scopodi studio, come branca della matematica, eseppure già verso la fine del ‘700 Eulero avessefondato la teoria dei grafi per determinare qualioperazioni fossero applicabili a un grafo in basealle sue proprietà, ci si limitava allo studio di grafiregolari.
Solo a partire dalla seconda metà del ‘900, siiniziò a considerare le reti come dei sistemicomplessi, passando dal mero studio alla lorogenesi per mezzo di modelli matematici, fino alloro utilizzo in campo sociale e naturale.
13
Introduzione
Da un punto di vista topologico Internet e il web sono
grafi, vale a dire insiemi di vertici uniti da archi.
La teoria dei grafi è stata inaugurata da Eulero nel 1736
per risolvere un problema pratico che affliggeva gli
abitanti di Königsberg.
La città di Königsberg ha una geografia particolare: si
trova alla confluenza di due fiumi, comprende un isolotto
ed è divisa in quattro parti che al tempo di Eulero erano
unite tramite sette ponti.
14
IntroduzioneIl matematico rappresentò ciascuna delle quattro zone della cittàcon un cerchio (“vertice”), e indicando ogni ponte con una linea(“arco”) e fornì una dimostrazione matematica dell’impossibilità ditrovare un percorso che, partendo da una qualsiasi delle quattrozone della città, permettesse di attraversare ciascun ponte soltantouna volta ritornando infine al punto di partenza, dando così originealla cosiddetta teoria dei grafi.
RETI
Definizioni e proprietà
16
Reti: definizioni e proprietà
Come si può rappresentare una rete
La rappresentazione classica di una rete è quellache viene fatta disegnando dei punti (detti nodi) edelle linee che li collegano (archi).
17
Reti: definizioni e proprietà
In matematica, una rete viene definita come una
famiglia di oggetti che viene chiamata “grafo”,
definito come una coppia di insiemi:
• un insieme V di nodi (o vertici);
• un insieme E delle connessioni fra i nodi
(detti archi, legami o link).
V = (v1,v2,v3,v4,v5)
E = (e1,e2,e3,e4,e5,e6)
18
Reti: definizioni e proprietàUna rete o un grafo G(V,E) può essere
rappresentato da una matrice (detta matrice di
adiacenza) che abbia i nodi come elementi di
riga o di colonna e contenga un valore diverso da
zero all’incrocio se i due nodi sono connessi.
v1 v2 v3 v4 v5
v1 0 1 1 0 0
v2 1 0 1 0 1
v3 1 1 0 1 1
v4 0 0 1 0 0
v5 0 1 1 0 0
19
Reti: definizioni e proprietà
Grado di connettività di un nodo
Il grado di un nodo è dato dal numero di archi
emergenti dal nodo, equivalente cioè al numero
di nodi direttamente raggiungibili dal nodo in
esame, detti anche nodi primi vicini.
Nodo 1 2 3 4 5 6
Grado 2 3 2 3 3 1
20
Reti: definizioni e proprietàCoefficiente di aggregazione
Misura quanto i primi vicini
del nodo i sono connessi fra
loro rimuovendo i.
Nella nostra rete, se
consideriamo il nodo 5, i nodi
primi vicini (1,2) restano
connessi tra loro, mentre il
nodo p.v. 4 viene isolato dai
predetti nodi 1 e 2.
21
Reti: definizioni e proprietà
22
Reti: definizioni e proprietà
23
Reti: definizioni e proprietà
Tipologie di reti complesse
Rete casuali: in una rete di tal genere ogni coppia di
nodi ha la stessa probabilità p di essere
connessa. Per p prossima allo zero, i
nodi saranno prevalentemente isolati.
Se invece p tende a 1, i nodi della rete
tendono ad essere connessi a tutti gli
altri nodi.
24
Reti: definizioni e proprietàTipologie di reti complesse
Reti a piccolo mondo: (cd. small-world) mostrano un
coefficiente di aggregazione molto più
elevato rispetto alle reti casuali.
Reti senza scala: (cd. scale-free) mostrano una
caratteristica «evolutiva» che ricorre a
due meccanismi: uno di crescita e
l’altro di connessione preferenziale.
25
Reti: definizioni e proprietàReti «scale-free»
Le caratteristiche essenziali di tali reti si traducono, in
altre parole, nei seguenti aspetti:
- la crescita, che fa sì che ad ogni
intervallo di tempo un certo numero di
nuovi nodi si aggiunge alla rete;
- la connessione preferenziale, dovuta
al fatto che i nuovi nodi si collegano con
maggiore probabilità a nodi già ricchi di
connessioni.
26
Reti: definizioni e proprietàEffetti di rete
In una rete scale-free, la rimozione dei nodi a
maggiore connessione porta immediatamente ad un
aumento del diametro e alla disintegrazione della
rete in cluster isolati, mentre la rimozione casuale di
altri nodi non ha effetti particolarmente sensibili.
Nodo a maggiore
connessione
Nodi a connessione
ridotta
27
Reti: definizioni e proprietàEffetti di rete
Ad esempio, un attacco mirato ad alcuni importanti
hub della rete Internet ha portato più di una volta alla
paralisi di gran parte del sistema. Mentre la
scomparsa di singoli elementi, poco connessi, non
inficia minimamente il funzionamento regolare del
resto della rete.
28
Reti: definizioni e proprietà
Fra le tante reti esistenti in natura (cd.
reti reali) una delle prime che vengono
in mente è la rete sociale dei rapporti
fra persone.
In questa rete, i nodi sono gli individui
ed esiste un collegamento fra due di
essi se si conoscono o sono parenti.
Esiste dunque un’alta probabilità che
due nodi collegati ad un altro siano
collegati tra loro.
29
Reti: definizioni e proprietàEffetti di rete
Le reti scale-free sono estremamente eterogenee e la
loro topologia è dominata da un numero
relativamente ridotto di nodi molto collegati, che
uniscono il resto degli elementi meno connessi del
sistema.
Il semplice modello base di
costruzione di una tale rete
può essere arricchito
utilizzando meccanismi di
connessione preferenziale
più complesso.
30
Reti: definizioni e proprietàCaratteristiche di una rete scale-free
31
Reti: definizioni e proprietàEffetti di rete: concetto di densità
A = rete casuale
B = rete SF
C = rete a stella
Uso della SNA
nell’analisi criminale
33
Uso della SNA nell’analisi criminale
Analisi delle reti criminali
«- Mio marito è stato vittima di un informatore della sua organizzazione,
non della nostra.
- Questo non è vero Signora Ayala. La vostra rete oramai è
compromessa.» – Dal film TRAFFIC, 2001
«Il Web cambia le organizzazioni. Oggi vincono le più flessibili. Come
Al Qaeda» - L’Espresso, 2007
«La ‘Ndrangheta (…) un micidiale impero criminale con ramificazioni in
tutto il mondo e con uomini sparsi nelle posizioni più strategiche (…)»
- Libero, 2013
«Nel mondo del crimine organizzato, l’uso spregiudicato della violenza
va di pari passo all’acume organizzativo e commerciale» - La Stampa,
2013
«Strategia di sicurezza interna dell’UE: smantellare le reti criminali
internazionali» - europa.eu, 2011
34
Uso della SNA nell’analisi criminale
Analisi delle reti criminali
«I casi (ndr. Investigazioni) dimostrano che spesso una rete criminale è
composta non da individui ma da gruppi criminali organizzati.» –
«L’intera azione può essere condotta da una sola banda, oppure da una
combinazione di numerose cellule» – Digesto di casi di criminalità
organizzata, 2012
«Era membro del Brothers’ circle, un network criminale segretissimo
che è finito nel mirino del Dipartimento del Tesoro americano» -
Ilfattoquotidiano, 2013
«Nella mafia cinese non c’è nessuna «super testa di dragone», piuttosto
«dragoni a più teste» che operano indipendentemente gli uni dagli altri
nel business del malaffare. Un network di diversi sodalizi criminali
che sanno scambiarsi, anche a livello europeo e internazionale, una
serie di favori» - La Repubblica, 2013
35
Uso della SNA nell’analisi criminale
Analisi delle reti criminali
L’analisi delle reti sociali
«criminali» mediante
l’applicazione delle teorie
della Social Network
Analysis, permette di meglio
comprendere quali sono le
dinamiche che caratterizzano
le diverse organizzazioni
criminali che sono state
censite nel tempo.
36
Uso della SNA nell’analisi criminale
Creazione delle reti criminali
L’analisi necessita della definizione delle entità (nodi)
che compongono la rete sociale «criminale» e della
tipologia di legame che si può instaurare tra di loro
(collegamenti).
Occorre determinare
pertanto la rete oggetto di
studio.
37
Uso della SNA nell’analisi criminale
Creazione delle reti criminali
Le entità (nodi) che vengono individuate nel modello
sono le seguenti:
gruppi criminali
soggetti (componenti dei gruppi)
luoghi di influenza criminale
38
Uso della SNA nell’analisi criminale
Creazione delle reti criminali
Le relazioni (link) possibili che vengono individuate
nel modello sono le seguenti:
[gruppo – luogo]
[gruppo – soggetti]
39
Uso della SNA nell’analisi criminale
Il modello che si viene a creare, aggiungendo i
collegamenti, ha pertanto la seguente struttura:
Prestanome
CLAN B
CLAN C
CLAN A
40
Uso della SNA nell’analisi criminale
Il modello nella forma semplificata ha la seguente
struttura equivalente:
41
Uso della SNA nell’analisi criminale
Il modello permette di recuperare ictu oculi alcune
importanti informazioni:
42
Uso della SNA nell’analisi criminale
Visualizzazione network
È possibile inoltre realizzare il
modello al fine di visualizzare
tutte le informazioni censite
mediante software di analisi
visuale (come ad esempio
Gephi, Analyst’s Notebook).
43
Uso della SNA nell’analisi criminale
Analisi criminale con l’ausilio della SNA
Il software Analyst’s Notebook permette di definire i
seguenti indici connessi alla SNA sulla rete così
definita:
• Centralità (cd. centrality)
• Livello (cd. degree)
• Vicinanza (cd. closeness)
• Coinvolgimento (cd. betweenness)
44
Uso della SNA nell’analisi criminale
Analisi criminale con l’ausilio della SNA
La Centralità è un concetto chiave nell’analisi delle reti
sociali.
Una rete fortemente centralizzata è dominata da una
entità (o nodo) che controlla il flusso di informazioni e
può divenire un punto di chiusura della
comunicazione.
Una rete meno centralizzata non ha singoli punti di
chiusura. Così i nodi possono veicolare informazioni
anche se alcuni dei canali di comunicazione sono
bloccati.
45
Uso della SNA nell’analisi criminale
Analisi criminale con l’ausilio della SNA
Il Livello (cd. degree) permette di individuare le entità
che possono essere le più attive nella rete in base al
numero di collegamenti diretti con altre entità.
Ad esempio, più un nodo (un clan, un soggetto o un
luogo di influenza) mostra collegamenti tra entità e
maggiore sarà il suo “livello” nella rete sociale.
Tale indice fornisce
pertanto l’importanza
dimensionale del “nodo”
nella rete complessiva.
46
Uso della SNA nell’analisi criminale
Analisi criminale con l’ausilio della SNA
La Vicinanza indica le entità che possono avere un
migliore accesso alle altre parti della rete e visibilità di
attività nel resto della rete. Tale indice esprime la
propensione dei gruppi criminali, sotto il profilo
soggettivo, a creare legami e collegamenti con altri
sodalizi e, sotto il profilo territoriale, ad essere presenti
e quindi avere interessi
su più aree, comprese
quelle in cui operano
altri clan.
47
Uso della SNA nell’analisi criminale
Analisi criminale con l’ausilio della SNA
Il Coinvolgimento indica le entità che possono
controllare il flusso delle informazioni tra le diverse
parti della rete.
Nella rete sociale criminale tale indice evidenzia il
livello di importanza di taluni nodi (gruppi e/o soggetti)
che manifestano una
maggiore intraprendenza
per l’evoluzione
dell’organizzazione
criminale.
48
Uso della SNA nell’analisi criminale
Analisi criminale con l’ausilio della SNA
Da un punto di vista prettamente
investigativo, tale indice
rappresenta un’importante cartina
al “tornasole” proprio perché
dovrebbe permettere, focalizzando i
principali sforzi investigativi proprio
sui nodi maggiormente coinvolti, di
disarticolare la rete relazionale
criminale, operante in talune aree
del Paese che mostrano una
maggiore influenza criminale.
49
Uso della SNA nell’analisi criminale
Effetto «gatekeeper»
Tali nodi sono i gatekeeper della rete, cioè coloro che
mostrano un’elevata capacità di organizzare e
disciplinare - proprio come fa un portiere di un
condominio, ad esempio con la posta ricevuta - i flussi
di comunicazione tra le diverse entità della rete.
È evidente che l’assenza
di tali figure genererebbe
un disordine ovvero
l’inesistenza della stessa
rete sociale.
50
Uso della SNA nell’analisi criminale
Analisi criminale con l’ausilio della SNA
La seguente immagine mostra una rete criminale
visualizzata su Analyst’s Notebook.
51
Uso della SNA nell’analisi criminale
52
Uso della SNA nell’analisi criminale
Analisi criminale con l’ausilio della SNA
Gruppi criminali presenti in una determinata area
53
Uso della SNA nell’analisi criminale
Analisi criminale con l’ausilio della SNA
Possibilità di isolare le entità appartenenti a specifiche
organizzazioni criminali
54
Uso della SNA nell’analisi criminale
Analisi criminale con l’ausilio della SNA
Possibilità di isolare le entità appartenenti a specifiche
organizzazioni criminali
55
Uso della SNA nell’analisi criminale
Analisi criminale con l’ausilio della SNA
Possibilità di isolare le entità appartenenti a specifiche
organizzazioni criminali
56
Uso della SNA nell’analisi criminale
Analisi criminale con l’ausilio della SNA
Possibilità di definire il DNA delle organizzazioni criminali
Di seguito, la struttura teorica «media» di un Clan per O.C.
Organizzazione
CriminaleCapoclan Affiliato Collegato Fiancheggiatore Prestanome
Org. Crim. 1 1,9 23,4 0,4 0,3 0,0
Org. Crim. 2 1,0 7,7 0,4 0,7 0,4
Org. Crim. 3 1,2 9,3 0,2 0,2 0,2
57
Uso della SNA nell’analisi criminale
Analisi criminale con l’ausilio della SNA
Possibilità di definire il DNA delle organizzazioni criminali
Di seguito, la densità su struttura tipo G-S:
Numero Legami Numero Nodi Densità
L/(N*(N-1)/2)
Densità
MediaOrganizzazione
criminaleL N
Org. Crim. 1
25 26 0,08
0,0927 26 0,08
28 23 0,11
Org. Crim. 2
7 8 0,25
0,276 7 0,29
6 7 0,29
Org. Crim. 3
6 7 0,29
0,325 6 0,33
5 6 0,33
58
Uso della SNA nell’analisi criminale
Analisi criminale con l’ausilio della SNA
Possibilità di definire il DNA delle organizzazioni criminali
59
Uso della SNA nell’analisi criminale
Analisi criminale e la community detection
Possibilità di individuare all’interno della rete delle sottocomunità
60
Uso della SNA nell’analisi criminale
Analisi criminale e la community detection
61
Uso della SNA nell’analisi criminale
Analisi criminale e la community detection
62
Uso della SNA nell’analisi criminale
Analisi criminale e la community detection
Simulazioni con Gephi
64
Simulazioni con Gephi
Applicazioni della SNA alla comprensione di
fenomeni di criminalità e di ricostruzione dei fatti
- Il caso: attentati terroristici 11 settembre 2001
Analisi dei flussi di finanziamento ricostruiti su atti
ufficiali della National Commission on Terrorist Attacks
Upon the United States (Monograph on Terrorist
Financing)
Esercitazione pratica
66
Esercitazione pratica Applicazioni della SNA
- Costruzione di una rete: funzioni di importazione,
visualizzazione e analisi delle principali metriche,
utilizzo di layout e formattazione condizionale dei
risultati
- Modularità e community detection
- Analisi di un contesto reale: comprendere
l’orientamento dei social network
Conclusioni
“Il futuro è delle strutture senza centri vitali”
da «The Starfish and the Spider»
R. Beckstrom – O. Brafman
GRAZIE PER L’ATTENZIONE
Tecniche
Social Network
Analysis (SNA)
e loro applicazioniDott. Marco Stella
CIFI – Contatti: marcosideris@gmail.com
Seminario IISFA
Casa dell’Aviatore
Roma, 21 aprile 2017