Analisi delle interazioni tra utenti in gruppi di Facebook · Nel corso del primo capitolo si...
114
Transcript of Analisi delle interazioni tra utenti in gruppi di Facebook · Nel corso del primo capitolo si...
Università degli Studi di Messina
Dipartimento di Matematica e Informatica
Corso di Laurea Triennale in Informatica
Analisi delle interazioni tra utenti in
gruppi di Facebook
Laureando: Relatore:
Giovanni Rizzotti Prof. Dott. Giacomo Fiumara
Anno Accademico 2012/2013
Indice
1 Le Reti Sociali 71.1 La Rete Sociale . . . . . . . . . . . . . . . . . . . . . . . . . . 71.2 Elementi della Rete Sociale . . . . . . . . . . . . . . . . . . . 81.3 Numero di Dunbar . . . . . . . . . . . . . . . . . . . . . . . . 81.4 Densità di una rete . . . . . . . . . . . . . . . . . . . . . . . . 91.5 Social Network o Social Media? . . . . . . . . . . . . . . . . . 9
2 Teoria dei Gra� 112.1 Descrizione del Grafo . . . . . . . . . . . . . . . . . . . . . . . 112.2 De�nizioni matematiche . . . . . . . . . . . . . . . . . . . . . 122.3 Tipologie di Grafo . . . . . . . . . . . . . . . . . . . . . . . . 13
2.3.1 Grafo Orientato . . . . . . . . . . . . . . . . . . . . . . 132.3.2 Grafo Non Orientato . . . . . . . . . . . . . . . . . . . 152.3.3 Grafo Pesato . . . . . . . . . . . . . . . . . . . . . . . 16
2.4 Applicazioni . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172.5 Rappresentazione di un Grafo . . . . . . . . . . . . . . . . . . 17
2.5.1 Liste di Adiacenza . . . . . . . . . . . . . . . . . . . . 182.5.2 Matrici di Adiacenza . . . . . . . . . . . . . . . . . . . 19
2.6 Cammini e Cicli . . . . . . . . . . . . . . . . . . . . . . . . . . 202.6.1 Ciclo Hamiltoniano . . . . . . . . . . . . . . . . . . . . 21
2.7 Gra� connessi . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3 Le Reti Complesse 233.1 Metriche e Misure di Centralità . . . . . . . . . . . . . . . . . 25
3.1.1 Degree Distribution . . . . . . . . . . . . . . . . . . . . 253.1.2 Centrality . . . . . . . . . . . . . . . . . . . . . . . . . 263.1.3 Degree centrality . . . . . . . . . . . . . . . . . . . . . 273.1.4 Closeness centrality . . . . . . . . . . . . . . . . . . . . 293.1.5 Betweenness centrality . . . . . . . . . . . . . . . . . . 303.1.6 Coe�ciente di Clustering . . . . . . . . . . . . . . . . . 313.1.7 Eccentricity . . . . . . . . . . . . . . . . . . . . . . . . 32
1
3.1.8 Modularity (Community Detection) . . . . . . . . . . . 333.2 Tipologie di Reti Complesse . . . . . . . . . . . . . . . . . . . 34
3.2.1 Scale-Free Networks . . . . . . . . . . . . . . . . . . . 343.2.2 Grafo Random . . . . . . . . . . . . . . . . . . . . . . 373.2.3 Modello Erd®s-Rènyi . . . . . . . . . . . . . . . . . . . 383.2.4 Six Degrees of Separation . . . . . . . . . . . . . . . . 403.2.5 Small-World Networks . . . . . . . . . . . . . . . . . . 41
4 Facebook 464.0.6 I Gruppi . . . . . . . . . . . . . . . . . . . . . . . . . . 47
4.1 Facebook Development . . . . . . . . . . . . . . . . . . . . . . 484.1.1 SDK . . . . . . . . . . . . . . . . . . . . . . . . . . . . 494.1.2 Le Applicazioni . . . . . . . . . . . . . . . . . . . . . . 504.1.3 FQL (Facebook Query Language) . . . . . . . . . . . . 524.1.4 Permessi . . . . . . . . . . . . . . . . . . . . . . . . . . 554.1.5 Access Tokens . . . . . . . . . . . . . . . . . . . . . . . 56
5 Progetto 585.1 Obiettivi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 585.2 Strumenti di progettazione . . . . . . . . . . . . . . . . . . . . 59
5.2.1 Linguaggi di Programmazione . . . . . . . . . . . . . . 595.2.2 DBMS . . . . . . . . . . . . . . . . . . . . . . . . . . . 615.2.3 GraphML (Graph Markup Language) . . . . . . . . . . 62
5.3 L'Applicazione Facebook . . . . . . . . . . . . . . . . . . . . . 635.3.1 Access Token . . . . . . . . . . . . . . . . . . . . . . . 64
5.4 Script PHP per l'acquisizione dei dati . . . . . . . . . . . . . . 645.4.1 L'esecuzione con Cron . . . . . . . . . . . . . . . . . . 70
5.5 Schema Entity-Relationship del database . . . . . . . . . . . . 705.6 Script PHP per la veri�ca dei dati acquisiti . . . . . . . . . . . 715.7 Estrazione dati e statistiche . . . . . . . . . . . . . . . . . . . 73
5.7.1 GraphML . . . . . . . . . . . . . . . . . . . . . . . . . 77
6 Analisi 806.1 Gra� . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 846.2 Metriche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 936.3 Andamento temporale post e commenti . . . . . . . . . . . . . 1006.4 Tipologia di allegati . . . . . . . . . . . . . . . . . . . . . . . . 103
7 Conclusioni e Sviluppi Futuri 105
2
8 Bibliogra�a e Sitogra�a 1088.1 Le Reti Sociali . . . . . . . . . . . . . . . . . . . . . . . . . . . 1088.2 Teoria dei gra� . . . . . . . . . . . . . . . . . . . . . . . . . . 1098.3 Reti complesse . . . . . . . . . . . . . . . . . . . . . . . . . . 1098.4 Facebook . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1128.5 Progetto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
3
Introduzione
Parte della disumanità del computer sta nel fatto
che, una volta programmato e messo in funzione,
si comporta in maniera perfettamente onesta.
Isaac Asimov, Il vento è cambiato, 1983
Questo progetto di Tesi si pone l'obiettivo di analizzare le interazioni che
avvengono tra gli utenti iscritti a dei gruppi chiusi all'interno di Facebook.
Facebook è un social network che sta prendendo sempre più piede e conta
oltre 1.20 miliardi di utenti attivi. Il proliferare di questo e di altri servizi
di social network, fa sì che le persone possano comunicare ed interagire tra
loro in enormi comunità virtuali e che l'analisi delle reti sociali possa essere
estesa anche a questa tipologia di comunità.
Facebook mette a disposizione dell'utente, tra le tante cose, i gruppi cioè dei
luoghi virtuali all'interno dei quali è possibile condividere interessi comuni e
interagire grazie a due strumenti principali: i post ed i commenti. I gruppi
di Facebook possono essere di tre tipologie: Aperto, Chiuso o Privato; molto
semplicemente, i contenuti di un gruppo aperto possono essere visionati an-
che dai non iscritti al gruppo, mentre i contenuti dei gruppi di tipo chiuso e
privato sono fruibili dai soli iscritti.
4
Sono stati presi in esame quattro gruppi che di�eriscono per tematiche
discusse, numero di iscritti ed intensità dell'attività. Per poter procedere
con l'analisi delle interazioni tra gli utenti e dell'attività nei di�erenti gruppi,
è stato necessario acquisire e memorizzare i vari post e commenti presenti
all'interno dei vari gruppi.
L'interfacciamento a Facebook è avvenuto attraverso delle API messe a di-
sposizione da Facebook stesso che permettono l'utilizzo di diverse funzionalità
legate al social network; avendo necessità di prelevare i dati dai gruppi è sta-
to utilizzato l'FQL, un linguaggio di interrogazione che permette appunto di
interrogare il database di Facebook per ottenere alcune informazioni riguar-
do i post ed i commenti presenti sul social network. I dati così estratti sono
trattati e successivamente memorizzati all'interno di un database personale.
Il passo successivo è stato quello di sviluppare un applicativo che consentisse
l'interrogazione del database personale al �ne di estrarre dei dati, trattarli e
produrre alcuni �le necessari per le operazioni di analisi.
L'analisi dei dati ha permesso di dimostrare come non sempre i gruppi siano
luogo di socializzazione tra utenti, poiché ci si ritrova con un numero elevato
di componenti che evidenziano una frammentazione nelle interazioni ed, in
certi casi, una totale assenza di interazione.
Il resto di questa Tesi è organizzato come segue.
Nel corso del primo capitolo si presentano le Reti Sociali e l'analisi delle
reti sociali; nel secondo si passa alla descrizione della teoria dei gra� : cosa
sia un grafo, le tipologie di gra� e le diverse metodologie di rappresentazione
dei gra�.
Nel capitolo 3 vi è una discussione sulle Reti Complesse: dalle metriche alle
varie tipologie di reti complesse.
5
Il capitolo 4 è dedicato, dopo una piccola introduzione a Facebook, alla descri-
zione dello sviluppo con Facebook: gli SDK, le API, le applicazioni, l'FQL
ed i vari metodi di accesso.
Nel capitolo 5 si discute sul progetto vero e proprio: gli obiettivi, un dia-
gramma di sequenza, gli strumenti di progettazione, la descrizione dei vari
script PHP, dell'applicativo che interroga il database personale succitato e
delle varie query utilizzate.
Nel capitolo 6 sono presenti i risultati dell'analisi, corredati da gra�, gra�ci
e tabelle.
Le conclusioni e gli sviluppi futuri concludono la Tesi.
6
Capitolo 1
Le Reti Sociali
L'Analisi delle Reti Sociali (Social Network Analysis) è una metodologia di
analisi che si occupa dello studio delle reti sociali e si fonda sull'idea in base
alla quale è possibile considerare la società come un intreccio complesso di
relazioni sociali strutturate. È proprio quest'intreccio a costituire il punto
focale dell'analisi poiché ogni fenomeno sociale può essere visto in termini
relazionali e strutturali, a patto di esprimerlo in termini di attori e relazioni
tra questi attori.
Attualmente l'Analisi delle Reti Sociali trova applicazione in diverse scienze
sociali (la sociologia, la psicologia, l'economia) e nei campi �sico, biochimico
e genetico.
1.1 La Rete Sociale
La Rete Sociale (Social Network) è costituita da attori sociali e relazioni
de�nite tra tali attori; è dunque possibile de�nire la Rete Sociale come una
struttura di relazioni le cui caratteristiche possono essere usate per spiegare
il comportamento delle persone che costituiscono la rete stessa.
7
Figura 1.1: Esempio di una Rete Sociale
1.2 Elementi della Rete Sociale
Gli elementi che costituiscono una Rete Sociale sono:
� Nodi: possono essere singoli individui, gruppi, istituzioni, luoghi;
� Relazioni: legano i soggetti che compongono la rete e sono rappresen-
tate gra�camente mediante linee, frecce o archi. Le relazioni possono
essere: reciproche, simmetriche, asimmetriche.
1.3 Numero di Dunbar
Nelle reti sociali vale il principio del numero di Dunbar, conosciuto anche
come la regola dei 150. Il principio a�erma che le dimensioni di una rete
sociale in grado di sostenere relazioni stabili sono limitate a circa 150 membri.
Questo numero è stato calcolato attraverso studi di sociologia e soprattutto
di antropologia, in relazione alla dimensione massima di un ecovillaggio.
Nella psicologia evoluzionista si ipotizza che tale numero possa costituire un
limite per abilità media degli esseri umani di riconoscere dei membri e tenere
traccia degli avvenimenti emotivi di tutte le persone di un gruppo. Secondo
8
altri è il numero massimo di abitanti di un villaggio al di sopra del quale si
sviluppano fenomeni di parassitismo sociale.
1.4 Densità di una rete
Ogni rete sociale, esprimibile mediante un grafo, è caratterizzata da una
densità. Dato che nel grafo i nodi identi�cano gli individui e gli archi i legami
che si instaurano tra essi, la densità di una rete rende un'idea di quanto sia
e�ciente l'interscambio relazionale tra i vari elementi della rete.
Una densità della rete pari ad uno indica che tutti gli elementi della rete
instaurano legami tra loro; in caso contrario, si ha una densità pari a zero
(assenza di comunicazione/relazione).
L'analisi delle reti sociali ha evidenziato come le reti piccole e dense risultano
talvolta meno utili di reti più ampie e con legami deboli, poiché queste ultime
si presterebbero meglio allo scambio di nuove idee e opportunità, favorendo
in questo modo i processi di innovazione.
1.5 Social Network o Social Media?
Spesso si fa confusione tra Social Network e Social Media. Mentre il primo è
un concetto teorico che descive delle relazioni, i Social Media sono un modo
per condividere contenuti con un vasto pubblico. In altri termini, è possibile
de�nire un Social Media come un gruppo di applicazioni basate sul Web
che permettono lo scambio e la creazione di contenuti generati dagli utenti.
Inoltre, i Social Media sono la piattaforma digitale nella quale nascono e
crescono le community, un insieme di persone con interessi o valori comuni
che si incontrano online per pensare e condividere insieme.
9
Secondo i professori Andreas Kaplan e Michael Haenlein, esistono sei tipi di
social media:
� Blog e microblog (es. Twitter);
� Siti di social networking (es. Facebook);
� Mondi virtuali di gioco (es. World of Warcraft);
� Mondi virtuali sociali (es. SecondLife);
� Progetti collaborativi (es. Wikipedia);
� Content communities: comunità che condividono materiale multi-
mediale, ad esempio YouTube.
Figura 1.2: Social Media
10
Capitolo 2
Teoria dei Gra�
In matematica ed in Informatica la teoria dei gra� si occupa di problemi che
possono essere rappresentati mediante gra�ci in cui compaiono punti (nodi)
e linee che congiungono i punti (archi). Attraverso i gra� è possibile sche-
matizzare situazioni e processi per consentirne l'analisi.
Il primo testo che prende in considerazione i gra� come entità matematiche
è la pubblicazione di Eulero sui �Sette ponti di Königsberg�. Nella secon-
da metà del XX secolo gli studi e i risultati si sono sviluppati ampiamente
in contemporanea allo sviluppo del calcolo automatico. L'introduzione del
computer ha consentito lo sviluppo di indagini sperimentali sui gra� ed ha
richiesto alla teoria dei gra� di indagare su algoritmi e modelli di forte im-
patto applicativo.
Nel giro di cinquant'anni la teoria dei gra� si è molto sviluppata e trova
applicazione in diversi campi.
2.1 Descrizione del Grafo
Per grafo si intende una struttura costituita da:
11
� oggetti semplici, detti vertici o nodi;
� collegamenti tra i vertici che possono essere:
� orientati (archi), il grafo è detto orientato;
� non orientati (spigoli o edges), il grafo è detto non orientato;
Generalmente un grafo è ra�gurato da punti che rappresentano nodi e
segmenti o curve che rappresentano gli archi o gli spigoli e collegano i nodi.
Il posizionamento dei nodi e la forma degli archi o spigoli è irrilevante; infatti
lo stesso grafo può essere disegnato in diversi modi senza che le sue proprietà
vengano modi�cate.
Figura 2.1: Esempio di Grafo con 6 nodi e 5 Archi
2.2 De�nizioni matematiche
Più formalmente, è possibile de�nire grafo una coppia G = (V, E) di in-
siemi, dove V è l'insieme dei nodi (o vertici) v1 . . . vn, ed E l'insieme degli
archi (o spigoli) e1 . . . en; due vertici v1, v2 connessi da un arco e1 prendono
nome di estremi dell'arco che viene anche identi�cato con la coppia formata
dai suoi estremi (v1, v2).
12
Si ha un grafo semplice se il grafo è sprovvisto di multiarchi; in caso con-
trario si ha un multigrafo.
Il numero di archi incidenti in un vertice v ∈ V costituisce il Grado di v. Il
Grado massimo di G è il grado del vertice di G con il maggior numero di
archi incidenti mentre il Grado minimo di G è il grado del vertice di G
che ha meno archi incidenti. Quando il grado massimo ed il grado minimo
coincidono con un numero k, si ha un Grafo Regolare.
2.3 Tipologie di Grafo
Esistono varie tipologie di grafo:
� Grafo Orientato
� Grafo Non Orientato
� Grafo Pesato
2.3.1 Grafo Orientato
Un grafo G = (V,E) è orientato se le coppie di nodi sono ordinate.
Viene de�nito un insieme G = (V, E), dove V è l'insieme dei vertici di G,
mentre E è l'insieme degli archi orientati di G.
La Figura 2.2 mostra un grafo orientato, dove l'arco ei si dice uscente da vh
ed entrante in vk.
Un arco orientato è caratterizzato da un verso.
2.3.1.1 De�nizioni Base
� Dato V=v1...vn, l'insieme degli archi orientati E = e1, . . . , en, è formato
da coppie ordinate di nodi;
13
Figura 2.2: Esempio di Grafo Orientato
� In particolare, è composto da una testa (rappresentata solitamente dal-
la punta di una freccia), che raggiunge un vertice in entrata, e una coda,
che lo lascia in uscita;
� Detto (u, v) un arco di un grafo orientato, si dice che:
� l'arco esce dal vertice u;
� l'arco entra nel vertice v;
� In un grafo orientato gli archi possono essere percorsi in un solo verso.
2.3.1.2 Grado di un grafo orientato
In un grafo orientato il grado uscente di un vertice è il numero di archi uscenti
dal vertice. Nel caso dei gra� orientati si distinguono il grado entrante di
un vertice v ed il grado uscente (rispettivamente de(v) e du(v)): il primo è
dato dal numero di spigoli entranti in v, mentre il secondo è dato dal numero
di spigoli uscenti. In un grafo orientato una sorgente è un vertice il cui
grado entrante è nullo.
14
La connessione V (vi, vj) non ha lo stesso signi�cato della connessione V (vj, vi),
essendo presente una relazione d'ordine dei vertici collegati.
2.3.2 Grafo Non Orientato
Gli elementi dell'insieme E sono coppie non ordinate di elementi di V. Ogni
arco non orientato di G corrisponde ad una coppia non ordinata di nodi di
G con ek = (vi, vj).
La presenza di un arco tra una coppia di nodi indica una relazione tra i nodi
stessi.
Figura 2.3: Esempio di Grafo non Orientato
In un grafo non orientato, G è un insieme di vertici e archi dove la
connessione V (vi, vj) ha lo stesso signi�cato della connessione V (vj, vi).
2.3.2.1 De�nizioni Base
� Se e ∈ E(G) ed e = (u, v), con u, v ∈ V (G), allora si dice che i vertici
u e v sono tra loro adiacenti e costituiscono gli estremi dello spigolo e;
� Se per ogni coppia di vertici u, v ∈ V (G) esiste al piú un solo spigolo
(u, v) ∈ E(G), allora il grafo G è semplice.
15
� un arco (v, v) è de�nito come loop;
2.3.2.2 Grado di un Grafo non orientato
Un arco (u, v) di un un grafo non orientato si dice che è incidente sui vertici
v e u; In un grafo non orientato, il grado di un vertice v, detto d(v), (dove d
stà per degree), è dato dal numero di archi incidenti su di esso;
se d(v) = 0 allora v è un vertice isolato, mentre se d(v) = n..1 (v è adiacente
ad ogni altro vertice del grafo), v è universale.
2.3.3 Grafo Pesato
Un grafo pesato è una struttura cui vengono associati dei pesi ad ognuno
dei suoi vertici o ad ognuno dei suoi archi.
Figura 2.4: Esempio di Grafo Pesato e Orientato
Il peso è un'informazione o dato che può essere di vario tipo (numerico,
alfabetico etc..); esiste una funzione peso che associa ad un arco un valore
w : E → R, ovvero un arco (u, v) ha peso w(u, v).
16
Il grafo è detto pesato se ad ogni arco viene associato un numero reale (peso),
il cui criterio di scelta dipende dal caso di utilizzo del grafo. Un grafo privo
di questo dato viene de�nito come semplice e non pesato. Il grafo pesato
può essere sia orientato (diretto), che non orientato (non diretto).
Esempio: in una rete stradale, ogni tratta viene de�nita come un arco da un
punto di partenza ad un punto di destinazione, in questo caso si potrebbe
associare un peso ad ogni tratta che ne rappresenta la distanza.
2.4 Applicazioni
In informatica, i gra� vengono utilizzati per schematizzare programmi, cir-
cuiti, mappe di siti e reti di computer.
Ad esempio, la struttura dei link delle pagine Web, come tutti gli ipertesti,
può essere rappresentata da un grafo orientato, dove i vertici sono le pagine
e gli archi rappresentano un link tra una pagina e l'altra.
I gra� orientati sono anche utilizzati per rappresentare le macchine a stati
�niti, diagrammi di �usso, schemi entità-relazione, reti di Petri etc.
Un grafo può essere esteso assegnando un peso a ciascun arco del grafo: in
questo caso si parla di gra� pesati (weighted), utilizzati per rappresentare le
strutture in cui le connessioni a due a due hanno alcuni valori numerici.
2.5 Rappresentazione di un Grafo
Vi sono diversi modi per rappresentare un grafo:
� Liste di Adiacenza;
� Matrici di Adiacenza;
17
2.5.1 Liste di Adiacenza
Una tecnica per la rappresentazione dei gra� molto utilizzata in informatica
prevede l'utilizzo di n liste L1, . . . , Ln di vertici, denominate liste di adiacenza
del grafo G.
Per ogni vertice vi ∈ V (G) vengono memorizzati i suoi vertici adiacenti nella
lista Li. Si rappresenta un grafo G = (V,E) con un vettore Adj di liste, cioè
una lista per ogni vertice del grafo. Per ogni vertice u, Adj[u] contiene tutti
i vertici v adiacenti ad u, ovvero quei vertici v tali per cui esiste un arco
(u, v) ∈ E.
Figura 2.5: Esempio di Lista di adiacenza
Nel caso di Gra� pesati, si memorizza il peso w(u, v) insieme al vertice v
nella lista per il vertice u.
2.5.1.1 Vantaggi
In generale la rappresentazione con liste di adiacenza è preferibile a quella me-
diante matrici di adiacenza perchè più compatta e consente di implementare
algoritmi più e�cienti dal punto di vista della complessità computazionale.
18
2.5.1.2 Svantaggi
Con una rappresentazione del grafo mediante liste di adiacenza è necessario
scorrere tutte le liste di adiacenza di ogni vertice del grafo per contare in quali
di queste liste è presente il vertice v. Nel caso peggiore, quando il grafo è
completo e il vertice v è l'ultimo vertice di ogni lista, il numero di operazioni
complessive sarà dell'ordine di O(n2) e non più lineare.
2.5.2 Matrici di Adiacenza
Un grafo può essere rappresentato utilizzando una matrice.
Unamatrice di adiacenza è una matrice quadrata binariaM di ordine n = |V |
che ha come indici di righe e colonne i nomi dei vertici del grafo. Nella
posizione (i, j) della matrice si trova un 1 se e solo se esiste nel grafo un arco
che va dal vertice i al vertice j, altrimenti si trova uno 0.
Figura 2.6: Esempio di matrice di adiacenza
Se il grafo è non orientato, per de�nizione risulta (vi, vj) ∈ E(G) ⇔
(vj, vi) ∈ E(G), pertanto la matrice di adiacenza sarà simmetrica rispetto
alla diagonale principale.
Se ogni arco e = (u, v) ∈ E(G) del grafo è associato ad un peso w(u, v)
non nullo, allora è possibile modi�care la rappresentazione del grafo con una
19
matrice di adiacenza in modo da poter tenere traccia anche dei pesi associati
agli archi ponendo: Mi,j = w(vi, vj) se (vi, vj) ∈ E e Mi,j = 0 altrimenti.
Nel caso di Gra� pesati, il peso viene memorizzato nell'elemento Mi,j, so-
stituendolo al valore 1, altrimenti se non esiste l'arco, all'elemento viene
assegnato valore 0. Ad esempio se l'insieme dei vertici del grafo rappresen-
ta una serie di punti su una carta geogra�ca, il peso degli archi può essere
interpretato come la distanza dei punti che questi connettono.
2.5.2.1 Vantaggi
� La rappresentazione con matrice di adiacenza è semplice;
� Se il grafo è piccolo non vi è sostanziale di�erenza di e�cienza con la
rappresentazione tramite liste di adiacenza.
Solitamente si preferisce la rappresentazione con liste di adiacenza perché,
quando il grafo è sparso, fornisce una rappresentazione compatta del grafo.
Se invece il grafo è denso, la matrice di adiacenza può essere preferita perché
è più rapido accedere alle informazioni in essa contenute.
2.6 Cammini e Cicli
Un cammino p dal vertice u al vertice v sul grafo G = (V,E) è una suc-
cessione di vertici p = (wi,1 , wi,2 , ...., wi,k ) tali che u = wi,1 , v = wi,k e
(wh, wh + 1) ∈ E(G) per ogni h = 1, 2, ...., k − 1.
La lunghezza del cammino è il suo numero di archi.
Un cammino, tale che tutti i nodi ed archi che lo compongono siano distinti,
viene de�nito semplice. In generale si indica con Pk il cammino semplice di
lunghezza k − 1 con k vertici.
20
Un ciclo Ck è un cammino (wi,1, wi,2, ...., wi,k, wi,k+1) in cui wi,1 = wi,k+1; con
la notazione Ck si indica un ciclo semplice, composto da k vertici distinti e
da k archi.
Figura 2.7: Esempio di Cammino e Ciclo in un grafo
2.6.1 Ciclo Hamiltoniano
I cammini hamiltoniani prendono il nome da William Rowan Hamilton che
inventò un gioco da tavolo (il puzzle di Hamilton o icosian game) che consi-
steva nel trovare un cammino chiuso sul bordo di un dodecaedro.
Un cammino in un grafo (orientato o non orientato) è detto hamiltoniano
se tocca tutti i vertici del grafo una e una sola volta.
La determinazione di un cammino hamiltoniano è la ricerca di una permuta-
zione (p0, p1, ..., pn−1) dei nodi tale che (pi, pi+1) ∈ E per ogni 0 ≤ i ≤ n− 2
dove E rappresenta l'insieme di archi del Grafo.
Si ha un ciclo hamiltoniano quando in un cammino hamiltoniano esiste un
arco che collega l'ultimo vertice con il primo, in maniera tale da realizzare
un ciclo che visita tutti i vertici per poi ritornare al punto di partenza.
Un grafo viene detto Hamiltoniano se contiene almeno un ciclo hamiltoniano.
È opportuno osservare che non tutti i gra� contengono un cammino hamil-
toniano.
21
Figura 2.8: Esempio di Ciclo Hamiltoniano
2.7 Gra� connessi
Un grafo non orientato G si dice connesso se per ogni coppia di vertici
u, v ∈ V (G) esiste un cammino p di u, v che li collega.
In un grafo orientato G due vertici u, v2 ∈ (G) si dicono fortemente connessi
se in G esistono due cammini p1 di u, v e p2 di v, u; se questi cammini non
esistono, ma i due vertici sono connessi da un cammino nel corrispondente
grafo non orientato, allora i due vertici si dicono debolmente connessi.
22
Capitolo 3
Le Reti Complesse
Una semplice de�nizione di rete potrebbe essere: �Intreccio di linee, reali o
ideali, che s'incrociano, cui ci si riferisce per indicare un sistema di collega-
menti o di comunicazioni oppure una struttura complessa articolata in più
punti� (Dizionario Italiano Devoto Oli).
Negli ultimi anni però, il termine ha assunto signi�cati più vasti ed una più
grande importanza rispetto alla de�nizione semplicistica succitata.
Gli studi sui diversi tipi di rete (reti sociali, reti fra aziende, reti telematiche,
reti biologiche, reti di trasporto, etc.), ed il fatto che queste reti sembrano
avere caratteristiche in comune, ne permettono la comprensione, l'analisi e
la previsione di comportamenti.
Fisici, matematici, sociologi ed economisti si impegnano sempre più per af-
�nare i risultati delle ricerche nel campo delle reti perché, in un mondo che
diventa sempre più �connesso�, è importante capire i meccanismi che per-
mettono una trasmissione e�ciente delle informazioni e cosa può rendere
vulnerabile una rete.
Lo studio delle reti complesse può essere considerato come una nuova di-
sciplina scienti�ca che trova applicazione nei più svariati campi: reti neurali,
modelli di tra�co, intelligenza arti�ciale, organismi biologici, Internet ecc.
23
Figura 3.1: Esempio di Rete Complessa
Grazie all'avvento di tecnologie informatiche più potenti, è stato possibile
e�ettuare con maggiore facilità simulazioni più complete e la comprensione
di tali modelli ha consentito studi sempre più approfonditi.
Un modo e�ciente per studiare un sistema complesso è quello di scomporlo
in parti più semplici, comprenderne il funzionamento e poi cercare di ricom-
porre il sistema originale.
Molti sistemi complessi possono essere rappresentati in termini di reti di ele-
menti che interagiscono: è quindi possibile applicare lo studio delle reti.
Come già detto, esistono diverse tipologie di reti, ma essenzialmente sono
tutte caratterizzate da un insieme di nodi e di connessioni tra i nodi. Le in-
terazioni fra i nodi attraverso le connessioni costituiscono il comportamento
globale del sistema. Il tipo ed il numero di nodi di una rete condizionano
molto il comportamento �nale del sistema, ma è molto importante, ai �ni
24
della comprensione del sistema, lo studio della topologia e della forma della
rete.
In de�nitiva, una rete complessa è una struttura di rete che presenta alcune
caratteristiche topologiche non immediatamente intuibili e solitamente non
presenti nelle reti semplici.
3.1 Metriche e Misure di Centralità
Le caratteristiche di una rete che consentono di valutarne le peculiarità
vengono de�nite metriche; le principali sono:
� Degree Distribution;
� Centrality;
� Clustering coe�cient.
3.1.1 Degree Distribution
Il grado distribuzione P (k) di una rete è una frazione dei nodi della rete con
grado k. Quindi, se ci sono n nodi in totale e nk di essi hanno grado k, si ha
P (k) = nk/n.
Il grado di distribuzione è molto importante nello studio delle reti reali come
Internet, delle reti sociali e delle reti teoriche.
Il modello più semplice di rete, il grafo random di Bernoulli, nel quale n
nodi possono essere collegati con probabilità indipendente p (o 1−p), ha una
distribuzione binomiale di grado:
P (k) =
(n− 1
k
)pk(1− p)n−1−k
25
de�nita come Distribuzione di Poisson nel caso di n molto grande.
Nella teoria delle probabilità la distribuzione di Poisson è una distribuzione
di probabilità discreta che esprime le probabilità per il numero di eventi che
si veri�cano, successivamente ed indipendentemente, in un dato intervallo di
tempo, sapendo che mediamente se ne veri�ca un numero λ. La distribuzione
di Poisson P (λ) è de�nita come:
P (n) = exp−λλn
n!
dove λ è il numero medio di eventi per intervallo di tempo, mentre n è il
numero di eventi per intervallo di tempo di cui si vuole la probabilità.
La maggior parte delle reti nel mondo reale ha però un grado di distribuzione
molto di�erente da questo; una grande quantità è altamente �right-skewed�
cioè la maggior parte dei nodi ha un basso grado, ma una piccola parte di
questi nodi, ha un alto grado. Alcune reti, come per esempio Internet ed
alcuni social networks, hanno un grado di distribuzione che segue approssi-
mativamente la seguente legge di potenza: P (k) ∼ k−y dove y è una costante.
Se la frequenza con cui si veri�ca un evento varia come potenza di un at-
tributo di tale evento, allora segue una legge di potenza cioè una relazione
matematica tra due quantità. Nel caso delle distribuzioni di probabilità, una
distribuzione che obbedisce alla legge di potenza è denominata power law
distribution.
3.1.2 Centrality
Nella teoria dei gra� e nell'analisi delle reti, la centralità di un nodo misura
la sua importanza all'interno di un grafo. Ad esempio, può indicare quanto
in�uente sia una persona all'interno di una rete sociale o quanto viene uti-
26
Figura 3.2: Esempio di Degree Distribution
lizzata correttamente una strada in una rete urbana. I concetti di centralità
si sono sviluppati inizialmente nel campo dell'analisi delle reti sociali e molti
dei termini utilizzati per misurare la centralità ri�ettono la loro origine so-
ciologica.
Le principali misure di centralità ampiamente utilizzate per l'analisi delle reti
sociali sono:
� Degree centrality;
� Closeness centrality;
� Betweenness centrality.
3.1.3 Degree centrality
La degree centrality è de�nita come il numero totale di collegamenti (archi)
incidenti su un nodo nel grafo. Il grado può anche essere visto come il rischio
che un nodo catturi ciò che circola all'interno della rete (come virus o altre
informazioni). Il grado di centralità di un vertice, per un dato grafo con
27
vertici e archi, è de�nito come Cd(v) = deg(v).
Dato un grafo non orientato G = (V,E), il grado di un nodo v ∈ V , de�nito
come δ(v), rappresenta il numero di archi incidenti in v.
deg(v) =∑i∈E
ev,i
con:
ev,i =
1 se(v, i) ∈ E,
0 altrimenti
Figura 3.3: Esempio di Degree Centrality di cui il nodo n1 ne detiene ilmassimo valore (3 archi collegati)
Nel caso di un grafo orientato, si possono de�nire due tipi misure di
Degree centrality:
� InDegree;
� OutDegree.
3.1.3.1 InDegree
Dato un grafo orientato G = (V,E) l'InDegree di un nodo v ∈ V , de�nito
come degin(v), rappresenta il numero di archi entranti in v.
28
degin(v) =∑i∈E
ei,v
con:
ev,i =
1 se(i, v) ∈ E,
0 altrimenti
3.1.3.2 OutDegree
Dato un grafo orientato G = (V,E), l'OutDegree di un nodo v ∈ V , de�nito
come degout(v), rappresenta il numero di archi uscenti da v:
degout(v) =∑i∈E
ev,i
con:
ev,i =
1 se(v, i) ∈ E,
0 altrimenti
Figura 3.4: Esempio di nodi con InDegree e OutDegree
3.1.4 Closeness centrality
Nei gra� connessi esiste una distanza metrica naturale tra tutte le coppie di
nodi, de�nita dalla lunghezza dei loro percorsi più brevi. La lontananza di
un nodo v è de�nita come la somma delle distanze da tutti gli altri nodi, e la
29
sua vicinanza è de�nita come l'inverso della lontananza. Quindi il nodo più
centrale è quello che ha la distanza minore rispetto a tutti gli altri nodi. La
vicinanza può essere considerata come una misura di quanto tempo ci vorrà
per di�ondere informazioni da s a tutti gli altri nodi in sequenza.
La di�usione di informazioni viene de�nita dall'uso dei cammini minimi
(shortest paths).
Quindi la closeness è una metrica che rappresenta la distanza minima (la più
vicina o veloce) tra un nodo e un altro, come:
CC(v) =∑t∈V \v
2−dG(v,t)
Dato un grafo G = (V,E) (fortemente) connesso e detta dG(u, v) la distanza
fra i vertici u, v ∈ V , si de�nisce la Closeness Centrality Cc(v) di un vertice
v ∈ V come:
Cc(v)def=
n− 1∑t∈V \v dG(u, v)
(3.1)
3.1.5 Betweenness centrality
La Betweenness è una misura di centralità di un vertice all'interno di un grafo,
che de�nisce la quantità di volte in cui un nodo agisce come ponte lungo il
percorso più breve tra due nodi. É stata introdotta da Linton Freeman come
una misura per quanti�care il controllo dell'uomo sulle comunicazioni tra
altri umani in una rete sociale. Secondo Freeman, i vertici che hanno un'alta
probabilità di essere in uno shortest path casuale tra due vertici casuali,
hanno un'alta betweennes.
La betweenness di un vertice v in un grafoG = (V,E) con V vertici è calcolata
come segue:
30
� Per ogni coppia di vertici (s, t) bisogna calcolare i percorsi più brevi
tra loro;
� Per ogni coppia di vertici (s, t) si determina la frazione di cammini
minimi che passano attraverso il vertice in questione (v);
� Si sommano queste frazioni su tutte le coppie di vertici (s, t).
La forma più compatta per rappresentare la betweenness è:
CB(v) =∑
s6=v 6=t∈V
σst(v)
σst
Dove σst è il numero totale di cammini minimi dal nodo s al nodo t, mentre
σst(v) è il numero di questi percorsi che passano attraverso v.
3.1.6 Coe�ciente di Clustering
Nella maggior parte delle reti, ed in particolare nelle reti sociali, i nodi ten-
dono a creare gruppi caratterizzati da una densità relativamente elevata di
legami. Il coe�ciente di clustering misura la tendenza di due nodi che sono
adiacenti ad un nodo comune, di essere connessi l'uno con l'altro. In altre
parole questa proprietà misura l'importanza di un nodo, valutando il numero
di archi del grafo nel caso in cui il nodo preso in esame fosse estratto dalla
rete.
Per esempio, nelle reti sociali il clustering rappresenta il principio secondo
il quale due amici di un individuo hanno una buona probabilità di essere
amici tra di loro, infatti le reti con alto clustering hanno un elevato numero
di triangoli (tripla di nodi dove almeno 2 di essi hanno un elevata probabilità
di essere connessi).
Esistono 2 tipi di coe�ciente di clustering:
31
� globale
� locale
Il coe�ciente di clustering globale o�re un'indicazione generale del
clustering nella rete e può essere applicato sulle reti orientate e non. Questo
coe�ciente è basato sulle cosiddette triplette di nodi, ognuna delle quali
è costituita da tre nodi che sono collegati da due (tripletta aperta) o tre
(tripletta chiusa) legami non orientati.
Il coe�ciente di clustering globale è rappresentato dal rapporto tra il numero
di triplette chiuse (o 3 triangoli) sul numero totale di triplette.
Il coe�ciente di clustering locale di un vertice (nodo) in un grafo quanti�ca
quanto vicino siano i suoi vicini per formare un grafo completo.
3.1.7 Eccentricity
La metrica Eccentricity rappresenta la massima distanza tra un vertice v ed
un qualsiasi altro vertice. L'insieme dei vertici (di un grafo non orientato)
e la funzione distanza formano uno spazio metrico, se e solo se il grafo è
collegato.
Esistono 2 principali misure di Eccentricity:
� Il raggio di un grafo che rappresenta l'eccentricity minima di ogni
vertice;
� Il diametro di un grafo che è la massima eccentricity di ogni vertice.
Per trovare il diametro di un grafo, bisogna trovare il percorso più breve
tra ogni coppia di vertici, dove la lunghezza massima di uno di questi
percorsi è il diametro del grafo;
32
3.1.8 Modularity (Community Detection)
La modularità misura la forza di divisione di una rete in moduli (chiamati
anche gruppi o comunità). Le reti con elevata modularità hanno connessioni
dense tra i nodi all'interno dei moduli stessi ma connessioni sparse tra i nodi
nei di�erenti moduli. Una buona suddivisione possiede alti valori di modu-
larità.
All'interno dei moduli la densità sarà alta ma fra un modulo e l'altro ci sa-
ranno pochi collegamenti e quindi una densità inferiore.
L'uso più comune della modularità è fatto per l'ottimizzazione delle tecniche
per determinare le comunità nelle reti.
Si consideri una rete composta da n nodi connessi da m archi, sia ai j un ele-
mento della matrice di adiacenza della rete; il valore di ai j è quindi l'insieme
degli archi che connettono i nodi i e j. Si supponga di stabilire una divisione
dei vertici in un certo numero di gruppi, la modularità di questa divisione
è de�nita come la frazione degli archi che vanno verso questo gruppo meno
quello che ci si aspetterebbe se gli archi fossero distribuiti casualmente. Nella
versione più comune di questo concetto, la casualità degli archi è stabilita in
modo da preservare il grado di ogni nodo.
In tal caso il numero di archi che collegano i due vertici seguono la casualità:
ki · kj2 ·m
dove ki è il grado di un vertice i.
Il minor numero di archi attesi tra i due nodi è:
ai,j −ki · kj2 ·m
Sommando tutte le coppie di vertici nello stesso gruppo, la modularità Q
33
è de�nita come:
Q =1
2m
∑i,j
[ai,j −ki · kj2 ·m
]δ(ci, cj)
Dove δ è il grado delle community c.
Il suo valore può muoversi nell'intervallo [−1; 1]: è positivo se il numero degli
archi presenti è maggiore del numero di quelli attesi, altrimenti è negativo.
3.2 Tipologie di Reti Complesse
Esistono due classi molto note e molto studiate di reti complesse che sono:
� Scale-Free Networks
� Small-World Networks
3.2.1 Scale-Free Networks
Una rete è chiamata scale-free se il suo grado di distribuzione, cioè la proba-
bilità che un nodo selezionato in maniera casuale abbia un certo numero di
link, segue una particolare funzione matematica chiamata Power of Law. La
legge di potenza implica che la Degree Distribution di queste reti non abbia
una scala caratteristica, ma al contrario, una rete con scala ben de�nita è
caratterizzata dal fatto che ogni nodo ha (approssimativamente) lo stesso
grado. Esempi di rete a scala singola includono il Modello Erd®s-Rényi
(ER) con grafo casuale.
L'interesse per le reti scale-free è cominciato alla �ne degli anni '90 con la
scoperta della legge di potenza del grado di distribuzione nelle reti del mondo
reale, come il World Wide Web.
Alcune reti che seguono questa legge (e altri tipi speci�ci di struttura) pos-
sono essere altamente resistenti alla cancellazione casuale di vertici.
34
Figura 3.5: Esempio di Scale-Free Network
Quando il grafo è uniformemente casuale i vertici critici sono quelli con il
grado più alto e sono critici se in caso di una loro cancellazione si potrebbe
avere un'instabilità del grafo e delle sue componenti connesse.
Mentre i gra� casuali (ER) hanno una distanza media dell'ordine di log(N)
tra i nodi, dove N è il numero di nodi, il grafo Scale-Free può avere una
distanza di log(log(N)). Questi gra� sono chiamati ultra small-world net-
works.
3.2.1.1 Caratteristiche delle Scale-Free Network
Una rete scale-free è una rete il cui grado di distribuzione segue una legge di
potenza, almeno asintoticamente. Cioè, data una frazione P (k) di nodi nella
rete avente connessioni k con altri nodi va per grandi valori di k come:
P (k) ∼ k−γ
35
dove γ è un parametro il cui valore è tipicamente nell'intervallo 2 < γ < 3,
anche se a volte può trovarsi al di fuori di questi limiti.
In una rete con una distribuzione Scale-Free, alcuni vertici hanno un gra-
do con ordine di grandezza maggiore rispetto alla media; questi vertici sono
spesso chiamati hub (perno o centro). Le proprietà Scale-free sono stret-
tamente correlate alla robustezza della rete rispetto al fallimento, perché i
grandi Hub sono seguiti da quelli più piccoli; questi ultimi, a loro volta, sono
seguiti da altri nodi con un grado ancora più piccolo e così via.
Questa gerarchia è tollerante ai guasti, infatti anche se avviene un guasto e
la maggior parte dei nodi sono quelli con un piccolo grado, la probabilità che
un hub possa risentirne è quasi trascurabile. D'altra parte, se si rimuovono
dalla rete degli Hub importanti, questa viene trasformata in un insieme di
gra� isolati e si ha una rete compromessa. Gli Hub possono quindi essere sia
un punto di forza che di debolezza nelle reti Scale-free.
Un'altra importante caratteristica delle reti scale-free è la distribuzione del
coe�ciente di clustering, che diminuisce all'aumentare del grado di ogni no-
do. Anche questa distribuzione segue una legge di potenza e ciò implica che
i nodi di basso grado appartengono a dei sotto-gra� molto densi collegati tra
loro tramite gli Hub.
Se si considera una rete sociale in cui i nodi sono persone e i collegamenti so-
no i rapporti tra le persone conoscenti, è facile vedere che le persone tendono
a formare comunità, cioè piccoli gruppi in cui tutti conoscono tutti. Inoltre, i
membri di una comunità hanno anche un rapporto di conoscenza con persone
al di fuori di quella comunità. Alcune persone, tuttavia, sono collegate ad
un gran numero di comunità (ad esempio: celebrità, politici etc.) e possono
essere considerate come gli hub responsabili del fenomeno small-world.
Attualmente, le caratteristiche di una rete scale-free, variano al variare del
36
meccanismo utilizzato per generarle. Per esempio, le reti generate con l'at-
taccamento preferenziale, tipicamente hanno i nodi con il più alto grado al
centro della rete, connessi insieme a formare un nucleo. La rimozione casuale
di un gran numero di nodi non ha conseguenze importanti sulle connessioni
della rete, suggerendo che tali topologie potrebbero essere utili per la sicurez-
za. Una caratteristica �nale concerne la distanza media tra due vertici in una
rete: come con la maggior parte delle reti disordinate, anche con il modello
Small-World, questa distanza è molto ridotta rispetto a una rete altamente
ordinata come un grafo o reticolo. Alcuni esempi di reti scale-free sono:
� Social network, comprese le reti di collaborazione, ad esempio la rete
delle collaborazioni degli attori cinematogra�ci;
� molti tipi di reti di computer, tra cui Internet ed il World Wide Web;
� alcune reti �nanziarie come la rete di pagamento bancario online;
� reti Aeree, stradali, ferroviarie etc.
3.2.2 Grafo Random
In matematica con il termine grafo random ci si riferisce alle distribuzioni di
probabilità applicate ai gra�. I gra� random possono essere descritti sem-
plicemente dalla distribuzione di probabilità o da un processo random che
li genera. Da un punto di vista matematico i gra� random sono usati per
rispondere alle domande riguardo le proprietà dei gra� tipici e solitamente,
con il termine grafo random, ci si riferisce quasi esclusivamente al modello
Erd®s-Rènyi.
Le applicazioni pratiche di questo tipo di grafo si possono trovare in tutti i
campi in cui le reti complesse hanno bisogno di essere modellate.
37
3.2.3 Modello Erd®s-Rènyi
Il modello Erd®s-Rènyi è uno dei modelli più strettamente connessi alla ge-
nerazione di gra� casuali ed imposta un arco tra ogni coppia di nodi con
la stessa probabilità, indipendentemente dagli altri archi. Prende il nome
da Paul Erd®s e Alfred Rényi, che per primi hanno introdotto uno dei due
modelli (utilizzabili nel metodo probabilistico per provare l'esistenza di gra�
che soddisfano diverse proprietà) nel 1959, mentre l'altro modello è stato
introdotto in modo indipendente e contemporaneamente da Edgar Gilbert.
Il matematico Paul Erd®s si occupò, tra le altre cose, di studiare le caratteri-
stiche dei gra� casuali e dimostrò che basta una piccola percentuale di archi
rispetto al totale per avere un grafo connesso, dove il grado di separazione di
tali gra� è straordinariamente piccolo.
3.2.3.1 De�nizione
Esistono due varianti del modello di Erd®s-Rényi:
� Modello G(n,m), un grafo viene scelto in modo uniforme a caso dalla
raccolta di tutti i gra� che hanno n nodi e m archi. Per esempio, un
grafo G(3,2) dove ciascuno dei tre gra� ha 3 vertici e 2 archi sono inclusi
con probabilità di 1/3.
� Modello G(n,p), un grafo viene costruito collegando nodi in modo
casuale. Ciascun arco è incluso nel grafo con probabilità p indipendente
da ogni altro arco.
Equivalentemente, tutti i gra� con n nodi ed m archi hanno la stessa proba-
bilità di:
pM(1− p)(n2)−M
38
Il parametro p in questo modello può essere pensato come una funzione
peso; quando p aumenta da 0 a 1, diventa sempre più probabile che il modello
includa gra� con più archi ed è sempre meno probabile che includa gra� con
meno archi. Il caso particolare p = 0, 5 corrisponde al caso in cui sono scelti
tutti i gra� su n vertici con uguale probabilità.
Sebbene p e M possono essere �ssi in questo caso, potrebbero anche essere
funzioni che dipendono da n. Ciò signi�ca che, come n tende all'in�nito,
la probabilità che un grafo su n vertici con probabilità di arco 2ln(n)/n è
collegato, tende a 1.
3.2.3.2 Proprietà del modello G(n, p)
Un grafo G(n, p) ha in media (n/2)p archi e la distribuzione del grado di
qualsiasi particolare vertice è binomiale:
P (deg(v)) =
(n− 1
v
)pk(1− p)n−1−k
dove n è il numero totale di vertici nel gra�co, quindi:
P (deg(v))→ (np)ke−np
k!
quando
n→∞, np = cost
Questa è una distribuzione di Poisson per n grande e np = costante. I
risultati includono che:
� Se np < 1, allora un grafo G(n, p) quasi certamente non ha componenti
connessi di dimensioni maggiori di O(log(n)).
39
� Se np = 1, allora un grafo G(n, p) quasi sicuramente avrà una grande
componente la cui dimensione è di ordine n2/3.
� Se np → c > 1, dove c è una costante, un grafo G(n, p) avrà quasi
sicuramente una componente unica gigante contenente una frazione
positiva dei vertici. Nessun altro componente conterrà più di O(log(n))
vertici.
� Se p < (1−ε) ln nn
un grafo G(n, p) quasi certamente contiene vertici
isolati, quindi è scollegato.
� Se p < (1+ε) ln nn
un grafo G(n, p) sarà quasi sicuramente connesso.
Dove ln nn
è quindi una soglia per la connessione di G(n, p).
3.2.4 Six Degrees of Separation
La teoria dei sei gradi di separazione è un'ipotesi secondo cui qualunque
persona può essere collegata ad una qualunque altra attraverso una catena
di conoscenze con non più di 5 intermediari, cioè in un limite massimo di 6
passi. Tale teoria è stata proposta per la prima volta nel 1929 dallo scrittore
ungherese Frigyes Karinthy nel racconto omonimo pubblicato nel volume
Catene 1.
Il concetto venne ripreso dal sociologo Stanley Milgram che in un celebre
esperimento dimostrò nel 1967 che e�ettivamente la separazione media risultò
essere uguale a sei. Fu allora che venne coniata l'espressione sei gradi di
separazione.
Nel 2011, un gruppo di informatici dell'Università degli Studi di Milano, in
collaborazione con due informatici di Facebook, ha e�ettuato un esperimento
su scala mondiale per calcolare il grado di separazione tra tutte le coppie di
40
individui su Facebook. In media, i gradi di separazione sono 4.74: il 92%
delle coppie è separato da non più di 4 gradi.
Figura 3.6: Sei gradi di separazione
3.2.5 Small-World Networks
Figura 3.7: Esempio di rete Small-World
L'ipotesi Small-World descritta da Karinthy e testata sperimentalmente
da Stanley Milgram (1967), si fonda sull'idea in base alla quale due persone
41
arbitrarie sono collegate da solo sei gradi di separazione, vale a dire il diame-
tro del grafo corrispondente al numero di connessioni sociali non è più grande
di sei.
Il loro modello ha dimostrato che un grafo regolare (il cui diametro è pro-
porzionale alla dimensione della rete), con l'aggiunta di un piccolo numero di
collegamenti a lungo raggio, può essere trasformato in un small-world in cui
il numero medio di archi tra due vertici è molto piccolo, mentre il coe�ciente
di clustering rimane grande.
È noto che una grande varietà di gra� astratti espongono proprietà dello
Small-World, ad esempio gra� casuali e reti scale-free. Inoltre, anche le reti
del mondo reale, come il World Wide Web mostrano anche questa proprietà.
Come descritto precedenemente, il coe�ciente di clustering è un parametro
che rappresenta la densità dei triangoli della rete (triple di vertici); per esem-
pio, i gra� sparsi e casuali hanno un coe�ciente di clustering estremamente
piccolo mentre le reti del mondo reale spesso hanno un coe�ciente signi�-
cativamente più grande. Gli scienziati indicano questa di�erenza come un
suggerimento che gli archi sono correlati nelle reti del mondo reale.
La teoria illustra come sia possibile conciliare due aspetti apparentemente
contraddittori: il fatto che nonostante ogni elemento tenda ad avere relazioni
prevalentemente con pochi altri (alta aggregazione) non impedisce di otte-
nere comunque una sua vicinanza, tramite pochi intermediari, con qualsiasi
altro elemento della rete (basso grado di separazione).
3.2.5.1 De�nizione
Una rete Small-World è un tipo di grafo matematico nel quale la maggior
parte dei nodi non sono vicini tra loro, ma possono essere raggiunti da tutti
gli altri tramite un piccolo numero di passi.
42
Nello speci�co, una rete small-world è de�nita come una rete in cui la distanza
L tipica tra due nodi scelti a caso (il numero di passi richiesti) cresce propor-
zionalmente al logaritmo del numero di n nodi della rete, che è: L ∝ log N .
Una certa categoria di reti small-world è stata identi�cata come una classe
di gra� random da Duncan Watts e Steven Strogatz nel 1998. Essi hanno
rilevato che i gra� possono essere classi�cati in base a due caratteristiche
strutturali indipendenti: il coe�ciente di clustering e la distanza media da
nodo a nodo (nota anche come lunghezza media del percorso più breve, Ave-
rage Shortest Path). Gra� puramente casuali, costruiti secondo il modello
Erd®s-Rényi, presentano una piccola lunghezza media del percorso più cor-
to (variando tipicamente con il logaritmo del numero di nodi) con un basso
coe�ciente di clustering.
Watt e Strogatz hanno misurato che in e�etti molte reti reali hanno una bassa
lunghezza media del percorso più breve, ma anche un coe�ciente di clustering
signi�cativamente superiore a quello previsto per ogni caso di�erente.
3.2.5.2 Proprietà delle reti Small-World
Le Small-World Network tendono a contenere cliques (gruppi), cioè delle
sotto-reti che hanno quasi tutte le connessioni tra due nodi al loro interno.
De�nizione di Clique: Nella teoria dei gra�, una clique è un insieme V
di vertici in un grafo non orientato G, tale che, per ogni coppia di vertici in
V, esiste un arco che li collega. In modo equivalente, si potrebbe dire che il
sottografo indotto da V è un grafo completo. La dimensione di una clique è
de�nita come il numero di vertici che contiene.
Ciò deriva dalla proprietà che de�nisce un elevato coe�ciente di clustering.
In secondo luogo, la maggior parte delle coppie di nodi saranno collegate da
43
almeno un percorso breve. Tipicamente vi è una sovrabbondanza di nodi
nella rete con un elevato numero di connessioni (noto come grado elevato).
Gli hub fungono da collegamenti comuni che mediano le lunghezze dei per-
corsi brevi tra gli altri archi.
Questa proprietà sono spesso analizzate come una frazione di nodi nella rete
che hanno un particolare numero di connessioni che vanno in essi (il grado di
distribuzione della rete). Reti con un maggiore numero di hub avranno una
maggiore frazione di nodi con grado elevato e di conseguenza la distribuzione
del grado sarà arricchito da elevati valori di grado. In particolare, se una
rete ha un grado di distribuzione che segue una distribuzione della legge di
potenza, viene considerata come una rete Small-World (note anche come reti
Scale-Free).
3.2.5.3 Esempi di reti Small-World
È possibile trovare esempi di reti Small-World in diverse applicazioni nel
mondo reale: mappe stradali, catene alimentari, reti elettriche, reti di neuroni
del cervello, reti di calcolatori e reti con in�uenze sociali.
3.2.5.4 Costruzione di una Small-World
Il meccanismo principale per la costruzione di queste reti è il meccanismo
di Watts-Strogatz che consiste nel costruirle in modo tale che il numero di
vicini di ogni vertice nella rete è delimitato, mentre la distanza da un altro
vertice (il diametro della rete) viene minimizzata.
3.2.5.5 Robustezza delle reti Small-World
Una possibilità è che le reti Small-World siano più resistenti alle perturbazioni
rispetto ad altre architetture di rete.
44
Nella legge di potenza distribuita delle reti Small-World, la cancellazione
casuale di un nodo causa raramente un notevole aumento della media-breve
lunghezza del percorso (o una drastica riduzione nel coe�ciente di clustering).
Ciò deriva dal fatto che la maggior parte dei percorsi più brevi tra i nodi del
�usso passano attraverso gli hub e se un nodo periferico viene eliminato, è
improbabile che possa interferire con il passaggio tra gli altri nodi.
In questo senso, le reti casuali sono vulnerabili alle perturbazioni casuali,
mentre piccole reti del mondo sono robusti.
Tuttavia, le Small-World, a di�erenza delle reti casuali, sono vulnerabili agli
attacchi mirati agli hub.
45
Capitolo 4
Facebook è un servizio di rete sociale lanciato nel febbraio 2004. Il sito, fon-
dato a Harvard negli Stati Uniti da Mark Zuckerberg e dai suoi compagni
di università Eduardo Saverin, Dustin Moskovitz e Chris Hughes, originaria-
mente era stato progettato esclusivamente per gli studenti dell'Università di
Harvard, ma fu presto aperto anche agli studenti di altre scuole della zona
di Boston, della Ivy League e della Stanford University.
Successivamente fu aperto anche agli studenti delle scuole superiori e poi a
chiunque dichiarasse più di 13 anni di età. Da allora Facebook raggiunse
un enorme successo: secondo Alexa dal giugno 2013 è diventato il sito più
visitato al mondo, superando Google. Facebook ha cambiato profondamente
il modo in cui gli individui socializzano ed interagiscono.
Figura 4.1: Logo di Facebook
46
È disponibile in oltre 70 lingue e nel Settembre 2013 conta 1.19 miliardi di
utenti attivi che e�ettuano l'accesso almeno una volta al mese, classi�candosi
come primo servizio di rete sociale per numero di utenti attivi.
Gli utenti possono accedere al sito previa registrazione gratuita, durante la
quale vengono richiesti dati personali come nome, cognome, data di nascita
e indirizzo email.
Completata la registrazione, gli utenti possono creare un pro�lo persona-
le, includere altri utenti nella propria rete sociale aggiungendoli come amici,
scambiarsi messaggi e ricevere le noti�che automatiche quando questi aggior-
nano i propri pro�li. Inoltre, gli utenti possono fondare e unirsi a gruppi per
condividere interessi in comune con altri utenti, organizzati secondo il luogo
di lavoro, la scuola, l'università o altre caratteristiche, condividere contenuti
multimediali ed utilizzare varie applicazioni presenti sul sito.
4.0.6 I Gruppi
Il gruppo è un luogo virtuale all'interno del quale si discute e si condividono
opinioni su un determinato argomento. Gli utilizzi che si fanno dei gruppi
sono i più svariati: ci sono gruppi con scopi commerciali, gruppi per campa-
gne di sensibilizzazione intorno a temi speci�ci, gruppi per lo svago, gruppi
per studenti, etc.
Per poter partecipare attivamente al gruppo e lasciare dei messaggi o com-
menti, è necessario che l'utente sia iscritto al gruppo; per quanto riguarda
la consultazione del contenuto, in base alle tipologie del gruppo elencate di
seguito, questa può avvenire anche senza l'iscrizione dell'utente.
Esistono tre tipologie principali di gruppi:
� Gruppo Aperti: dove l'iscrizione al gruppo è libera ed anche i non
iscritti possono vedere i post pubblicati;
47
� Gruppo chiuso: dove per iscriversi serve il permesso dell'amministra-
tore e non si possono visualizzare i post se non si è iscritti;
� Gruppo Segreto: non visibile a nessuno se non all'amministratore e
ai membri esplicitamente invitati.
L'amministratore, all'interno del gruppo, può decidere di inserire una
breve descrizione e dei Tag (parole chiave) per speci�care gli argomenti su
cui verte il gruppo e far si che questo possa essere trovato più facilmente dagli
utenti in fase di ricerca; altra possibilità è quella di far si che i post possano
essere scritti solo dagli Amministratori o da tutti gli utenti.
4.1 Facebook Development
Attraverso la pagina web https://developers.facebook.com/ è possibile acce-
dere all'area di Facebook dedicata agli sviluppatori per poter usufruire dei
vari strumenti messi a disposizione.
È necessario che l'utente che intende sviluppare applicazioni per Facebook,
abbia un account Facebook valido e, se non l'ha già fatto, che avvii la pro-
cedura per creare l'account di sviluppatore tramite alcuni semplici passi.
Dopo aver attivato l'account da sviluppatore, è possibile avere accesso a
diverse sezioni, tra le quali:
� Applicazioni
� Strumenti
� Documentazione
� Assistenza
48
È anche possibile scaricare diversi SDK (Software development kit)
in base all'ambiente di destinazione del progetto (iOS, Android, JavaScript,
PHP, Unity).
4.1.1 SDK
Un SDK (software development kit, traducibile in italiano come pacchetto
di sviluppo per applicazioni), indica genericamente un insieme di strumenti
per lo sviluppo e la documentazione di software. Molti SDK sono disponibili
gratuitamente e possono essere prelevati direttamente dal sito del produtto-
re: in questo modo si cerca di invogliare i programmatori ad utilizzare un
determinato linguaggio o sistema. Vi è anche un utilizzo orientato al merca-
to: alcuni programmi vengono venduti assieme al loro SDK permettendo ai
compratori di sviluppare ulteriori parti del programma comprato.
Gli SDK possono variare considerevolmente in quanto a dimensioni e tecno-
logie utilizzate, ma tutti possiedono alcuni strumenti fondamentali:
� librerie standard dotate di interfacce pubbliche dette API - Applica-
tion programming interface;
� documentazione sul linguaggio di programmazione per il quale l'SDK
è stato sviluppato e sugli strumenti a disposizione nell'SDK stesso;
� informazioni sulle licenze da utilizzare per distribuire programmi creati
con l'SDK;
4.1.1.1 API
Con API (Application Programming Interface), si indica ogni insieme
di procedure disponibili al programmatore, di solito raggruppate a formare
49
un set di strumenti speci�ci per l'espletamento di un determinato compito
all'interno di un certo programma.
Le API permettono di espandere le funzionalità di un programma: per uno
sviluppatore mettere a disposizione un set di API di un suo software signi�ca
dare la possibilità ad altri di interagire con la sua piattaforma e, soprattutto,
estendere le funzioni e le caratteristiche della struttura base della piattafor-
ma.
Lo scopo principale delle API è quello di ottenere un'astrazione ad un più
alto livello, di solito tra l'hardware e il programmatore o tra software a bas-
so ed alto livello, sempli�cando così il lavoro di programmazione. Le API
permettono infatti di evitare ai programmatori di riscrivere ogni volta tut-
te le funzioni necessarie al programma in basso livello, favorendo quindi il
riutilizzo del codice.
4.1.2 Le Applicazioni
Giorno dopo giorno, su Facebook, è possibile trovare un nuovo gioco, un nuo-
vo quiz o una nuova attività.
Ognuna di queste attività è merito di un'applicazione che, grazie allo sforzo
degli sviluppatori, permette all'utente di visualizzare foto, postare un mes-
saggio od una nota e così via.
Le applicazioni presenti in Facebook sono migliaia e continuano a crescere
vertiginosamente. Non tutte le applicazioni sono state sviluppate da Face-
book, ma buona parte di esse sono merito di programmatori non legati in
alcun modo a Facebook.
Un'applicaziome su Facebook può quindi essere de�nita come un'applicazio-
ne Web, ospitata su uno spazio a propria disposizione, il cui utilizzo si fonde
con l'interazione con Facebook stesso.
50
Facebook non mette a disposizione dello sviluppatore uno spazio per ospitare
il codice dell'applicazione, quindi come avviene per un sito personale, bisogna
a�darsi a servizi di hosting.
Per quanto riguarda il concetto di fusione con Facebook, ci si riferisce al fatto
che le applicazioni possono interagire, per esempio, con la lista degli amici
dell'utilizzatore, dandogli l'impressione che Facebook e l'applicazione siano
un tutt'uno.
Lo sviluppatore può segliere due approcci di�erenti per lo sviluppo dell'ap-
plicazione: iFrame e FBML.
4.1.2.1 iFrame
L'applicazione sviluppata secondo quest'approccio, verrà visualizzata all'in-
terno di un iFrame, una vera e propria cornice nella pagina Facbook. Ciò
signi�ca che il browser considererà l'applicazione come se fosse completa-
mente separata dal resto degli elementi di Facebook, anche se continuerà ad
esistere un �lo sottile (le API) che la tiene legata a Facebook.
Quando l'utente visita la pagina contenente l'applicazione, Facebook rispon-
derà restituendogli i propri elementi (testata, pubblicità, etc.) e successiva-
mente verrà contattato il server (su cui è ospitata l'applicazione) che eseguirà
il codice scritto dallo sviluppatore.
Il risultato �nale verrà mostrato all'utente all'interno dell'iFrame.
4.1.2.2 FBML
In questo caso caso, Facebook e l'applicazione sono un tutt'uno: all'apertura
dell'applicazione ogni elemento della pagina (compresa l'applicazione stessa)
verrà caricato sequenzialmente come se fose un unico listato di codice.
La di�erenza principale tra iFrame e FBML è che il client non contatterà
51
mai il server dello sviluppatore direttamente: la richiesta iniziale è rivolta
sempre a Facebook che poi contatterà il server, il server richiamerà le API
necessarie e risponderà con una pagina scritta in FBML che verrà convertita
da Facebook in HTML classico e visualizzata all'utente.
4.1.2.3 Creazione di una nuova Applicazione
Il processo di creazione di una nuova applicazione è semplice, basterà scegliere
un nome ed accettare i termini di licenza di Facebook.
Un'applicazione Facebook è caratterizzata da due elementi importantissimi:
� Application ID: è un campo numerico non modi�cabile e generato
automaticamente da Facebook al momento della creazione dell'appli-
cazione e serve per identi�carla univocamente.
� Application Secret: chiave generata automaticamente da Facebook
che permette di autenticare la sessione ed e�ettuare le chiamate API
protette.
Application ID ed Application Secret sono di fondamentale importanza
quando si lavora con i vari SDK messi a disposizione da Facebook.
4.1.3 FQL (Facebook Query Language)
Facebook è soprattutto un grande contenitore di informazioni, dai dati perso-
nali che si sceglie di comunicare, ai vari post e commenti che vengono scritti.
È ovvio che una tale mole di informazioni necessiti di un sistema adeguato
per poter essere interrogata agevolmente. A tal �ne, viene messo a disposi-
zione dello sviluppatore uno strumento chiamato FQL.
L'FQL (Facebook Query Language), il cui acronimo ricorda molto SQL, si
52
basa sugli stessi principi di quest'ultimo, con l'aggiunta di diverse limitazioni
atte a garantire l'integrità e la privacy dei dati.
La struttura di una query con FQL si presenta come segue:
Listato 4.1: Struttura di una Query FQL
SELECT [campi]
FROM [tabella]
WHERE [condizioni]
La clausola SELECT serve a speci�care quali campi selezionare da una
determinata tabella; possono essere più di uno e vanno separati con la virgo-
la.
La clausola FROM serve a speci�care su che tabella verrà e�ettuata la que-
ry ed in FQL, per motivi di e�cienza, è possibile speci�care una sola tabella
al suo interno.
La clausola WHERE serve a recuperare informazioni speci�che da una ta-
bella escludendone altre irrilevanti tramite l'imposizione di una o più condi-
zioni. In FQL, a di�erenza dell'SQL, si può agire soltanto su campi indiciz-
zati.
Le tre clausole appena descritte, sono obbligatorie.
Per conoscere le tabelle ed i campi sui quali è possibile agire tramite una
query FQL, Facebook mette a disposizione una speci�ca pagina della docu-
mentazione u�ciale. Ad esempio, per scrivere un'ipotetica query al �ne di
conoscere nome e cognome di un determinato utente, è su�ciente controllare
nella documentazione la lista di tutte le tabelle per notare che tali informa-
zioni sono memorizzate all'interno della tabella user e, aprendo la pagina
descrittiva della tabella, è speci�cato che il nome ed il cognome sono memo-
rizzati nei campi first_name e last_name, mentre l'identi�cativo univoco
nel campo uid.
53
Listato 4.2: Query FQL per ottenere nome e cognome di un utente
SELECT first_name , last_name
FROM user
WHERE uid=x
I risultati delle interrogazioni vengono forniti in uno dei due formati a
scelta tra JSON oppure XML. A seguire, i risultati della query 4.2.
Listato 4.3: Risultato query in formato JSON
[
{
"first_name ": "Mario",
"last_name ": "Rossi"
}
]
Listato 4.4: Risultato query in formato XML
<xml version ="1.0" encoding ="UTF -8"?>
<fql_query_response xmlns ="http :// api.facebook.com /1.0/" >
<user >
<first_name >Mario </first_name >
<last_name >Rossi </last_name >
</user >
</fql_query_response >
È possibile ra�nare la query con le due clausole facoltative ORDER
BY e LIMIT. La prima permette di ordinare il risultato della query, in base
ad una determinata colonna, in maniera crescente o decrescente; la seconda,
permette di limitare il risultato ad un numero massimo di righe (ad esempio,
una query che contiene la clausola LIMIT 5 restituirà non più di 5 risultati).
54
4.1.3.1 Multi-Query
La metodologia multi − query permette di inviare al server più query con
un'unica chiamata, ottenendo tutti i risultati contemporaneamente.
È quindi possibile scrivere delle query più complesse facendo sì che il risul-
tato della seconda query dipenda dal risultato della prima. Ad esempio, se
si volessero ottenere alcune informazioni riguardo agli utenti che intendono
partecipare ad un evento, normalmente sarebbero necessarie due query se-
parate (una per selezionare gli user id dalla tabella degli eventi ed un'altra
per selezionare le informazioni dalla tabella degli utenti conoscendo gli user
id), aspettando il risultato della prima per poter procedere con la seconda.
Con il metodo multi-query è possibile eseguire entrambe le query nello stesso
momento ottenendo tutti i dati contemporaneamente e prestazioni superiori
rispetto all'esecuzione di una serie di single− query.
4.1.4 Permessi
Durante le operazioni di login, l'applicazione richiede il permesso per accedere
al pro�lo pubblico e alla lista degli amici di un utente. Per poter accedere a
degli elementi addizionali del pro�lo o per pubblicare contenuti su Facebook
per conto dell'utente, è necessario richiedere opportuni permessi usando la
�nestra di dialogo del Login o durante l'esecuzione dell'applicazione.
Le categorie dei permessi sono le seguenti:
� Email permissions;
� Extended pro�le properties: per accedere ad alcune informazioni
che non sono incluse nel pro�lo pubblico;
55
� Extended permissions: per accedere alle informazioni più sensibili
del pro�lo e per permettere all'appllicazione di pubblicare qualcosa per
conto dell'utente;
� Open Graph permissions;
� Page permissions: per gestire le attività di amministrazione delle
pagine Facebook;
4.1.5 Access Tokens
Quando ci si connette ad un'applicazione usando il Login di Facebook, l'ap-
plicazione otterrà un access token che fornirà, temporaneamente, un accesso
sicuro alle API di Facebook.
Un access token è una stringa che identi�ca un utente, un'applicazione o una
pagina e può essere usato dall'applicazione per e�ettuare le chiamate graph
API. I token includono informazioni riguardo alla data in cui il token scadrà
e quale applicazione lo ha generato.
Una caratteristica importante degli access token è la portabilità: una volta
che un token è stato generato, può essere utilizzato da un qualsiasi client
mobile, browser o server.
4.1.5.1 User Access Token
L'User Access Token è il token più utilizzato ed è richiesto ogni volta che l'ap-
plicazione e�ettua una chiamata alle API per leggere, modi�care o scrivere
dati riguardanti una persona speci�ca su Facebook. Questo tipo di Token
può essere di due tipi:
� Short-lived: ha una validità di circa un'ora o due;
56
� Long-lived: ha una validità di circa 60 giorni;
I Token generati dall'interfaccia web di login sono di tipo short-lived ma
possono essere convertiti in long-lived.
4.1.5.2 App Access Token
Gli App Access Token sono utilizzati per e�ettuare richieste alle API di
Facebook da parte di un'applicazione piuttosto che dall'utente. Può quindi
essere utilizzato per modi�care i parametri dell'applicazione, creare e gestire
utenti di test etc.
4.1.5.3 Page Access Token
I Page Access token sono utilizzati nelle chiamate alle API di Facebook per
gestire le Pagine Facebook. Soltanto l'amministratore della pagina può ge-
nerare questo tipo di token, poiché richiesto un permesso esteso chiamato
manage_pages che fa riferimento ad una pagina speci�ca.
57
Capitolo 5
Progetto
5.1 Obiettivi
Il progetto di Tesi proposto consiste nell'acquisizione di post e commenti da 4
diversi gruppi di Facebook al �ne di poter e�ettuare diverse analisi. I gruppi
selezionati per l'analisi sono (in ordine di intensità di attività):
� Facebook in the Social Science (da adesso FSS)
� Facoltà di Scienze MM.FF.NN. C.d.L. Informatica (da adesso
INF)
� Insegnanti (da adesso INS)
� Il mercatino messinese (da adesso MER)
Il primo passo è consistito nella realizzazione di uno script PHP che,
tramite FQL, acquisisce i vari post e commenti di quattro gruppi di Facebook,
memorizzandoli all'interno di un database personale; l'esecuzione automatica
dello script ogni 30 minuti avviene tramite cron.
Non appena terminata la raccolta, è stato realizzato un ulteriore script PHP
58
Figura 5.1: Diagramma di sequenza
per acquisire eventuali dati mancanti veri�cando che in archivio non fossero
presenti commenti in riferimento a post non memorizzati e che, per ogni post,
fossero stati acquisiti tutti i commenti.
Successivamente, è stato sviluppato un applicativo in C# che si occupa di
analizzare i dati estratti e di produrre in otput dei �le di testo contenenti i
risultati di alcune query per poter creare dei gra�ci con il software GNUPlot
ed un �le in formato GraphML per poter e�ettuare una serie di analisi ed
estrarre le varie metriche attravero il software Gephi.
5.2 Strumenti di progettazione
5.2.1 Linguaggi di Programmazione
Per quanto riguarda gli script, si è preferito utilizzare il linguaggio di pro-
grammazione PHP.
59
PHP è un linguaggio di programmazione interpretato, originariamente con-
cepito per la programmazione di pagine web dinamiche. Attualmente è
utilizzato principalmente per sviluppare applicazioni web lato server, ma
può anche essere usato per scrivere script a riga di comando o applicazioni
stand-alone con interfaccia gra�ca.
Figura 5.2: Logo PHP
Il linguaggio riprende per molti versi la sintassi del C e del Perl ed è in
grado di interfacciarsi ad innumerevoli database tra cui MySQL, PostgreSQL
e Oracle e supporta numerose tecnologie come XML, SOAP, IMAP ed FTP.
I motivi per cui è stato scelto questo linguaggio sono molteplici, fra tutti
il fatto che Facebook mette a disposizione un SDK per potersi interfacciare
con il Social Network (ad esempio per poter e�ettuare le query FQL descritte
nel capitolo precedente) e per il fatto che il PHP è un punto di riferimento
quando si tratta di eseguire codice lato server.
Per realizzare l'applicativo che analizza i dati estratti si è scelto C#, un
linguaggio di programmazione orientato agli oggetti, sviluppato da Microsoft
all'interno dell'iniziativa .NET. C# prende spunto da Delphi, C++ e Java
per quanto riguarda la sintassi e da Visual Basic per gli strumenti di pro-
grammazione visuale e per la sua semplicità.
La scelta è ricaduta su questo linguaggio poiché molto semplice da utilizzare
e perché possiede tutti gli strumenti atti ad e�ettuare le varie operazioni di
analisi che si sono rese necessarie.
60
5.2.2 DBMS
Il DBMS (Database Management System) è un sistema software progetta-
to per consentire la creazione, manipolazione ed interrogazione e�ciente di
database (una collezione di dati strutturati). Il progetto di Tesi ha richiesto
un DBMS online (su uno spazio di hosting) per la memorizzazione dei post
e dei commenti ed un DBMS in locale per permettere al software in C# di
e�ettuare le varie query al �ne di svolgere le dovute analisi.
In entrambi i casi, la scelta è ricaduta su MySQL.
MySQL è il DBMS open source più di�uso al mondo ed è composto da
un client ed un server, entrambi disponibili per sistemi Unix, GNU/Linux e
Windows. L'interazione con i dati da parte di MySQL avviene sfruttando il
linguaggio di interrogazione strutturata SQL (Structured Query Language).
Figura 5.3: Logo MySQL
5.2.2.1 Brevi cenni sull'SQL
L'SQL è un linguaggio standardizzato per database basati sul modello rela-
zionale (RDBMS) progettato per:
� creare e modi�care schemi di database (DDL - Data De�nition Lan-
guage);
� inserire, modi�care e gestire dati memorizzati (DML - Data Manipula-
tion Language);
61
� interrogare i dati memorizzati (DQL - Data Query Language);
� creare e gestire strumenti di controllo ed accesso ai dati (DCL - Data
Control Language);
Originariamente progettato come linguaggio di tipo dichiarativo, si è suc-
cessivamente evoluto con l'introduzione di costrutti procedurali, istruzioni
per il controllo di �usso, tipi di dati de�niti dall'utente e varie altre estensioni.
5.2.3 GraphML (Graph Markup Language)
GraphML è un formato di �le basato su XML, per la rappresentazione di
strutture grafo. Nello speci�co, consiste in un linguaggio di markup per de-
scrivere le proprietà strutturali di un grafo e di un meccanismo di estensione
�essibile per aggiungere dati speci�ci dell'applicazione. È previsto il suppor-
to a diversi tipi di gra�, tra i quali: diretti, non orientati, pesati, misti e
gerarchici.
A seguire, un esempio di �le GraphML per rappresentare un grafo semplice
con 3 nodi e 2 archi:
Listato 5.1: Esempio di �le GraphML per un grafo con 3 nodi e 2 archi
<?xml version ="1.0" encoding ="UTF -8"?>
<graphml xmlns="http :// graphml.graphdrawing.org/xmlns"
xmlns:xsi="http :// www.w3.org /2001/ XMLSchema -instance"
xsi:schemaLocation ="http :// graphml.graphdrawing.org/xmlns
http :// graphml.graphdrawing.org/xmlns /1.0/ graphml.xsd" >
<graph id="G" edgedefault =" undirected">
<node id="n0"/>
<node id="n1"/>
<node id="n2"/>
62
<edge source ="n0" target ="n2"/>
<edge source ="n1" target ="n2"/>
</graph >
</graphml >
Il tag <edgedefault> può assumere valore undirected o directed a se-
conda che il grafo sia orientato o non orientato.
I nodi del grafo sono dichiarati all'interno del tag <node> ed ognuno di essi
ha un identi�catore univoco de�nito dall'identi�catore id.
Gli archi del grafo sono dichiarati all'interno del tag <edge> ed ognuno di
essi è caratterizzato da una sorgente (source) ed una destinazione (target),
entrambe obbligatorie. I valori della sorgente e della destinazione devono
corrispondere ad uno degli identi�catori dei nodi dichiarati in precedenza
all'interno del documento. È possibile, eventualmente, aggiungere dei con-
tenuti strutturati all'interno del tag <edge> servendosi del meccanismo
Data/Key (utile, ad esempio, per impostare il peso di un arco).
5.3 L'Applicazione Facebook
Il primo passo per la realizzazione del progetto è stato la creazione dell'Appli-
cazione Facebook dalla relativa pagina nella sezione Developers di Facebook.
I permessi necessari all'applicazione sono:
� user_groups: fornisce l'accesso alla lista dei gruppi di cui l'utente è
membro;
� user_videos: fornisce l'accesso ai dettagli dei video pubblicati;
� user_photos: fornisce l'accesso ai dettagli delle foto pubblicate
63
� read_stream: fornisce l'accesso a tutti i dettagli dei post scritti da
un determinato utente;
Alla prima esecuzione dell'applicazione, si presenta una �nestra che in-
forma l'utilizzatore riguardo a quali sono i permessi necessari e ne richiede
la concessione, senza la quale l'applicazione non può svolgere i suoi compiti.
5.3.1 Access Token
Ad ogni esecuzione dell'applicazione, dopo il login, viene generato un access
token di tipo short-lived, dopo aver veri�cato che l'utente abbia concesso i
permessi necessari.
Avendo la necessità di eseguire automaticamente lo script ogni 30 minuti tra-
mite un server cron, si è resa necessaria un'altra strada da percorrere, poiché
per il rilascio del token, è indispensabile e�ettuare il login su facebook.
Si è proceduto alla generazione manuale di un token di tipo short-lived tra-
mite lo strumentoGraph API Explorer messo a disposizione da Facebook.
Successivamente, attraverso una speci�ca richiesta HTTP a Facebook nella
quale bisogna inserire l'Application ID e l'Application Secret dell'applicazio-
ne precedentemente creata ed il Token generato in precedenza, si ottiene un
token di tipo long-lived valido per circa 60 giorni.
5.4 Script PHP per l'acquisizione dei dati
Nello script PHP per l'acquisizione dei dati vi è una prima parte dichiarativa,
all'interno della quale si memorizzano, in alcune variabili:
� Informazioni Database: host name, nome del database, username e
password;
64
� ID dei Gruppi: codice identi�cativo univoco di ogni gruppo dal quale
è necessario estrarre i dati;
� Application ID: ID dell'Applicazione Facebook;
� Application Secret: Secret dell'applicazione Facebook;
� Token esteso;
Listato 5.2: Prototipo funzione executeQuery
function executeQuery($gruppo ,$table_post ,$table_comment ,
$fbconfig ,$token)
La funzione executeQuery si occupa dell'esecuzione delle query FQL e
dell'archiviazione dei dati ed accetta come parametri in ingresso:
� $gruppo: l'id del gruppo da cui estrarre i dati;
� $table_post: nome della tabella che ospiterà i post;
� $table_comment: nome della tabella che ospiterà i commenti;
� $fbcon�g: array contenente l'Application ID e l'Application Secret;
� $token: token esteso;
Listato 5.3: Listato di codice PHP per l'interfacciamento con Facebook
require_once "facebook.php";
$facebook = new Facebook(array(
'appId ' => $fbconfig['appid '],
'secret ' => $fbconfig['secret ']));
$facebook ->setAccessToken($token );
65
Il primo comando del Listato 5.3 è necessario ogni qual volta si voglia
utilizzare l'SDK; inoltre occorre anche l'istanziazione di un nuovo oggetto
di tipo Facebook speci�cando l'Application ID e l'Application Secret. Con
l'ultimo comando del listato si imposta il token, precedentemente acquisito,
che sarà utilizzato dall'SDK.
Le query FQL per acquisire le informazioni riguardanti post e commenti,
sono e�ettuate su due tabelle:
� Stream: tabella contenente informazioni riguardo i post;
� Comment: tabella contenente informazioni riguardo i commenti a
determinati post;
Durante i vari test con le query FQL è stato notato come questa piat-
taforma messa a disposizione da Facebook è ancora molto acerba e so�re di
improvvisi problemi nel generare risposte a query che producono un numero
considerevole di record.
Se in una query FQL non viene speci�cato un LIMIT, Facebook lo imposta
automaticamente a 7, restituendo un massimo di 7 record. Sono quindi state
e�ettuate diverse prove per tentare di acquisire, con un'unica esecuzione dello
script, tutti i post di un gruppo, impostando un LIMIT 10000 ; nonostante
ciò la piattaforma Facebook, dopo aver restituito un certo numero di record,
va in crash e mostra un messaggio d'errore. È importante segnalare come
si sia veri�cata una situazione alquanto insolita, dal momento che il valore
massimo di LIMIT accettato varia da esecuzione ad esecuzione.
In generale, con un LIMIT 200 non ci sono mai stati problemi, motivo per
cui si è scelto come valore per le query riguardanti i post ipotizzando che è
molto di�cile per i gruppi presi in esame riuscire a generare un tra�co di
post superiore a 200 ogni mezz'ora.
66
Listato 5.4: Query per acquisire i post
SELECT post_id , actor_id , created_time , attachment ,
like_info , share_count , message FROM stream
WHERE source_id = 'ID DEL GRUPPO '
ORDER BY created_time ASC LIMIT 200
Quando Facebook viene interrogato riguardo i post (mediante la query
mostrata nel Listato 5.4), restituisce un determinato numero di record in
base al valore di LIMIT impostato. Una domanda potrebbe sorgere sponta-
nea: tra le decine, centinaia o migliaia di post di un gruppo, quali di questi
vengono restituiti come risultato della query? Facebook restituisce gli ultimi
post su cui si è agito, cioè gli ultimi creati (se sono nuovi post) oppure gli
ultimi in cui è stato inserito un commento. Ciò vuol dire che un post scritto
mesi fa ma appena commentato �risale� la lista dei post e viene restituito
per primo nel caso di un eventuale query FQL. È possibile notare questa
gestione dei post anche nel normale utilizzo di Facebook, perché all'interno
di un gruppo vengono mostrati per primi gli ultimi post scritti o quelli con
commenti recenti.
Attraverso la query mostrata nel Listato 5.4 si selezionano le informazioni
relative ai post pubblicati in un gruppo, e nello speci�co:
� post_id: l'id del post;
� actor_id: l'id dell'utente, del gruppo, della pagina o dell'evento che
ha pubblicato il post;
� created_time: data ed ora della pubblicazione del post espressi in
formato timestamp UNIX ;
� attachment: array contenente informazioni riguardanti l'eventuale
allegato del post;
67
� like_info: informazioni riguardo i mi piace del post;
� share_count: numero di volte che un post è stato condiviso;
� message: il messaggio vero e proprio del post;
Con la clausola WHERE viene speci�cato di selezionare le informazioni
riguardanti i post di un gruppo speci�co (source_id). In�ne, tramite la
clausola ORDER BY si ordinano in modo crescente i post in base alla data
di creazione.
Listato 5.5: Query per acquisire i commenti
SELECT id , post_id , fromid , time , comment_count ,
likes , text , attachment FROM comment
WHERE post_id in (SELECT post_id from #post)
ORDER BY time ASC LIMIT 5000;
Attraverso la query mostrata nel Listato 5.5 si selezionano le informazioni
relative ai commenti fatti ai post selezionati con la query precedente, e nello
speci�co:
� id: l'id univoco del commento;
� post_id: l'id del post cui il commento si riferisce;
� fromid: l'id dell'utente che ha scritto il commento;
� time: data ed ora della pubblicazione del post espressi in formato
timestamp UNIX ;
� comment_count: numero di risposte al commento;
� likes: numero di mi piace del commento;
68
� text: il testo del commento;
� attachment: il link o la foto allegati al commento;
Con la clausola WHERE viene speci�cato di selezionare le informazioni
riguardanti i commenti i cui post_id sono presenti tra i risultati della query
precedente cioè quelli relativi ai post selezionati con la query del Listato 5.4.
In�ne, tramite la clausola ORDER BY si ordinano in modo crescente i post
in base alla data di creazione.
La dichiarazione delle query del Listato 5.4 e del Listato 5.5 è avvenuta
all'interno degli elementi dell'array associativo $multiQuery.
Listato 5.6: Esecuzione delle Query
$param = array(
'method ' => 'fql.multiquery ',
'queries ' => $multiQuery ,
);
$fqlResult = $facebook ->api($param );
Nel Listato 5.6 si può notare la vera e propria esecuzione delle query viste
in precedenza per la quale è necessaria la dichiarazione di un array all'interno
del quale si speci�cano dei parametri:
� method: metodo di esecuzione della query (trattato nel capitolo pre-
cedente); è possibile scegliere tra fql.multiquery e fql.query;
� queries: query da eseguire;
I risultati delle query sono memorizzati all'interno dell'array $fqlResult.
A questo punto è necessaria la memorizzazione dei dati appena acquisiti.
Data la gestione dei post di Facebook vista in precedenza, è possibile che
69
all'interno dell'array $fqlResult ci siano dei post e dei commenti già presenti
all'interno del database su cui si va a scrivere. Utilizzando il comando SQL
INSERT IGNORE si evitano errori nel caso in cui si tenti di inserire un record
già presente all'interno dell'archivio, poiché nella tabella dei post si utilizza
come chiave primaria l'id del post e nella tabella dei commenti l'id del com-
mento.
Prima di e�ettuare l'inserimento dei dati acquisiti all'interno del database, si
è proceduto a sostituire la stringa dell'id utente con la corrispettiva stringa
in md5 per garantire l'anonimato; inoltre, il campo timestamp Unix è stato
convertito nel formato data ed ora accettato da MySQL.
5.4.1 L'esecuzione con Cron
Per l'esecuzione automatica dello script ad intervalli di tempo pre�ssati, al
�ne di garantire la continuità dell'acquisizione dei vari post e commenti, ci
si è avvalsi di un servizio web che mette a disposizione un server cron.
Cron consente la piani�cazione di comandi, registrandoli e mandandoli in
esecuzione periodicamente in maniera automatica.
È stato su�ciente registrarsi al servizio web e, nel pro�lo personale, creare
un nuovo job nel quale speci�care la pagina web da visitare. Come intervallo
tra un'esecuzione e l'altra è stato impostato il valore di 30 minuti.
5.5 Schema Entity-Relationship del database
In Figura 5.4 è rappresentato il diagramma ER delle tabelle utilizzate per
memorizzare i post ed i commenti acquisiti tramite le query FQL. Sono pre-
senti le tabelle Post e Comments collegate da una relazione opzionale di tipo
1:N, poiché ogni post può avere 0, 1 o N commenti ad esso collegati ma
70
Figura 5.4: Schema Entity-Relationship della base di dati
ogni commento può appartenere soltanto ad un post.
La tabella Post ha come chiave primaria il campo di tipo stringa post_id,
mentre la tabella Comments ha come chiave primaria il campo di tipo stringa
comment_id.
Trattandosi di una relazione 1:N è presente una foreign key (chiave ester-
na) che indica un vincolo di integrità referenziale tra le due tabelle. Tale
chiave identi�ca una colonna della prima tabella che referenzia una colonna
della seconda tabella, creando una sorta di collegamento tra le due. Nello
speci�co, la foreign key è nella tabella Comments rappresentata dal campo
post_id e si riferisce alla chiave primaria della tabella Post : post_id.
5.6 Script PHP per la veri�ca dei dati acquisiti
Dati i problemi di cui so�re l'FQL descritti nei paragra� precedenti, ed i
problemi di integrità dei dati acquisiti che ne conseguono, si è resa necessaria
la creazione di uno script PHP che cercasse di rimediare, quanto più possibile,
a tali problemi. I principali problemi di integrità dei dati che sono stati
riscontrati riguardano l'assenza di post cui alcuni commenti si riferiscono e
la mancanza di alcuni commenti relativi a determinati post.
Lo script svolge due funzioni attraverso le query al database MySQL ed alle
71
query FQL:
Listato 5.7: Query SQL per selezionare gli id dei post non presenti in archivio
SELECT DISTINCT(post_id) FROM Comments
WHERE post_id NOT IN (SELECT post_id FROM Post)
Attraverso la query del Listato 5.7 si selezionano gli id dei post presenti
nella tabella contenente i commenti acquisiti ma non presenti nella tabel-
la dei post, ed ognuno di questi viene memorizzato all'interno di un array.
Successivamente, viene preparata una stringa contenente tutti gli id appena
selezionati separati dalla virgola.
Listato 5.8: Query FQL per selezionare le informazioni sui post assenti
SELECT post_id , actor_id , created_time , attachment ,
like_info , share_count , message FROM stream
WHERE source_id = 'ID DEL GRUPPO '
AND post_id in 'ID DEI POST '
ORDER BY created_time ASC LIMIT 800
Attraverso la query FQL mostrata nel Listato 5.8 si selezionano le infor-
mazioni riguardo i post i cui id sono stati memorizzati all'interno dell'array
dopo la query del Listato 5.7.
Le informazioni appena selezionate sono memorizzate all'interno della tabella
relativa ai post tramite il comando INSERT.
Listato 5.9: Query SQL per selezionare gli id dei post
SELECT post_id FROM Post
Attraverso la query mostrata nel Listato 5.9 si selezionano gli id di tutti
i post archiviati e si memorizzano all'interno di un array.
72
Listato 5.10: Query FQL per selezionare le informazioni sui commenti
SELECT id , post_id , fromid , time , comment_count ,
likes , text , attachment FROM comment
WHERE post_id = 'ID DEL POST ' ORDER BY time ASC
LIMIT 6000
Attraverso la query del Listato 5.10 si selezionano le informazioni riguardo
ai commenti i cui post_id sono presenti nell'array riempito con la query in
Listato 5.9.
Le informazioni appena selezionate sono memorizzate all'interno della tabella
relativa ai commenti tramite il comando INSERT IGNORE, poiché alcuni
commenti potrebbero già essere presenti.
5.7 Estrazione dati e statistiche
Per poter operare sui dati acquisiti è stato necessario e�ettuare un dump dei
dati archiviati sul server online, per importarli localmente tramite MySQL.
Lo scopo dell'applicativo è quello di interrogare MySQL al �ne di reperire
post e commenti per poi analizzarli e produrre dei �le come output.
Figura 5.5: Applicativo C# per l'estrazione di dati e statistiche
73
Ognuno dei pulsanti presenti in Figura 5.5 avvia una diversa procedura
che, tramite opportune query, ed in certi casi tramite operazioni sui dati
estratti, produce dei �le come output.
Listato 5.11: Query SQL per elencare il numero di post per giorno
SELECT DATE_FORMAT(STR_TO_DATE(created_time ,
'%e-%c-%Y %H:%i:%s'), '%d-%m-%Y')
AS Data , COUNT (*) FROM Post GROUP BY Data ORDER BY Data
La query in Listato 5.11 si occupa di elencare il numero di post rag-
gruppati per giorno attraverso l'operatore GROUP BY. La funzione DA-
TE_FORMAT è usata per convertire un campo di tipo datetime in un
formato personalizzato; in questo caso, si è passati da data ed ora alla sola
data nel formato AAAA-MM-GG.
È stata scritta anche una variante che agisce sulla tabella Comments per
elencare il numero di commenti raggruppati per giorno.
Figura 5.6: Parte del risultato della query 5.11
Listato 5.12: Query SQL per elencare la media dei ritardi dei commenti
SELECT A.post_id , AVG(TIMESTAMPDIFF(MINUTE ,
STR_TO_DATE(created_time , '%d-%m-%Y %H:%i:%s'),
STR_TO_DATE(time , '%d-%m-%Y %H:%i:%s'))) AS AVG
FROM Post A JOIN Comments B ON A.post_id = B.post_id
GROUP BY A.post_id ORDER BY A.post_id;
74
La query in Listato 5.12 permette di calcolare, in media, quanto tempo
intercorre tra la scrittura del post ed i successivi commenti.
Figura 5.7: Parte del risultato della query del Listato 5.12
Listato 5.13: Query SQL per elencare la percentuale di allegati
SELECT attachment_type , (COUNT (*)*100/
NUMERO_TOTALE_POST_CON_ALLEGATI) AS Percent
FROM Post WHERE LENGTH(attachment_type) > 0
GROUP BY attachment_type
La query in Listato 5.13 produce l'elenco dei tipi di allegati dei post e,
per ognuno di essi, ne calcola la percentuale sul numero totale di post con
allegati.
Figura 5.8: Risultato della query del Listato 5.13
Listato 5.14: Query SQL per elencare la percentuale di allegati su tutti i post
SELECT attachment_type , (COUNT (*)*100/
NUMERO_TOTALE_POST) AS Percent FROM Post
GROUP BY attachment_type
75
La query in Listato 5.14 produce l'elenco dei tipi di allegati dei post e,
per ognuno di essi, ne calcola la percentuale sul numero totale di post (con e
senza allegati).
Figura 5.9: Parte del risultato della query del Listato 5.14
Le query nei Listati 5.13 e 5.14 sono state applicate anche alla tabella dei
commenti.
Listato 5.15: Query SQL per elencare il totale di commenti per post
SELECT P.post_id ,COUNT (*)
FROM Post P LEFT JOIN Comments C
ON P.post_id = C.post_id
GROUP BY P.post_id ORDER BY P.post_id
La query in Listato 5.15 produce l'elenco degli id dei post e, per ognuno
di essi, il numero dei relativi commenti.
Figura 5.10: Parte del risultato della query del Listato 5.15
Listato 5.16: Query SQL per elencare la media dei post di ogni utente attivo
SELECT (SELECT COUNT (*) FROM Post) /
76
(SELECT COUNT(DISTINCT Nominativo) FROM
(SELECT Actor_id AS Nominativo FROM Post
UNION ALL SELECT DISTINCT(From_id) AS
Nominativo FROM Comment)X)
La query in Listato 5.16 produce il numero medio di post scritti da ogni
utente attivo all'interno del gruppo. Un utente è attivo se ha scritto almeno
un post o un commento all'interno del gruppo cui è iscritto.
È stata scritta anche una variante della query al �ne di produrre il numero
medio di commenti scritti da ogni utente attivo.
5.7.1 GraphML
La generazione del �le GraphML si è rivelata la parte più di�coltosa da
realizzare. Tale �le è costituito da tre sezioni principali: header, nodi, archi.
Figura 5.11: Header del �le GraphML
Listato 5.17: Query SQL per selezionare i nodi del grafo
SELECT DISTINCT Nominativo FROM
(SELECT Actor_id AS Nominativo FROM Post
UNION ALL SELECT DISTINCT(From_id) AS Nominativo
FROM Comments) X
La query in Listato 5.17 produce l'elenco degli id degli utenti attivi al-
l'interno del gruppo, i quali costituiranno i nodi del grafo. Tale elenco viene
scritto nel �le GraphML nel formato <node id=�ID_UTENTE�/>
77
Figura 5.12: Esempio della sezione dei nodi nel �le GraphML
Listato 5.18: Query per selezionare le relazioni tra gli utenti
SELECT A.actor_id , B.from_id
FROM Post A JOIN Comments B
ON A.post_id = B.post_id
La query in Listato 5.18, per ogni commento ad un post, seleziona gli id
utente del creatore del post e del creatore del commento.
Figura 5.13: Parte del risultato della query 5.18
Gli archi sono memorizzati nel �le utilizzando il tag <edge>, all'interno
del quale si speci�cano la sorgente, la destinazione ed un valore per la chiave
d1, utilizzata in questo caso per memorizzare il peso dell'arco.
Figura 5.14: Esempio della sezione degli archi nel �le GraphML
Ogni relazione deve essere rappresentata soltanto una volta all'interno
del �le, cioè se l'utente x e l'utente y sono presenti più volte nel risultato
della query in Listato 5.18 perché entrati in contatto diverse volte, per essi
78
deve essere presente un solo arco che abbia come sorgente l'id di x e come
destinazione l'id di y.
Dovendo realizzare un grafo pesato, è stato necessario tenere in considera-
zione il numero di volte che due utenti entrano in contatto poiché questo
numero rapprsenta il valore del peso.
Per poter preparare i vari pesi degli archi è stato utilizzato un array bidi-
mensionale all'interno del quale vengono inizialmente memorizzati il primo
valore di source e target prodotti dalla query in Listato 5.18 ed un valore
di peso pari ad 1. Successivamente, viene veri�cato se tra i risultati della
query è nuovamente presente quel determinato valore di source e di target ;
in caso a�ermativo, il valore del peso nell'array viene incrementato. Questa
veri�ca avviene, ovviamente, attraverso un ciclo per iterare tutti gli elementi
prodotti dalla query. Il procedimento appena descritto viene e�ettuato per
tutti gli elementi poiché dopo aver determinato il peso del primo elemento
del risultato, si passa al successivo e così via.
Tale parte del progetto non è stata di immediata realizzazione perché non si è
fatto uso di librerie di terze parti e le procedure per l'analisi delle interazioni
tra i nodi sono state programmate personalmente.
79
Capitolo 6
Analisi
In questo capitolo sono discusse le varie analisi che sono state e�ettuate a
partire dai �le generati con l'applicativo discusso nel capitolo precedente.
In questo lavoro di Tesi sono stati presi in considerazione quattro gruppi
chiusi di utenti di Facebook di dimensioni di�erenti.
Il primo, denominato �Facebook in the Social Sciences� è un gruppo co-
stituito da sociologi interessati allo studio di Online Social Network ed è
composto, al momento in cui quesa Tesi viene scritta, da 520 utenti. Soltan-
to un centinaio di essi partecipa attivamente mediante post o commenti, e
questo è un primo indicatore del fatto che si tratta di un gruppo di grande
successo, nel senso dell'attività oggetto di studio in questa Tesi.
Il secondo gruppo, denominato �Facoltà di Scienze MM.FF.NN. C.d.L.
Informatica�, è costituito da studenti di Informatica (132) e da qualche do-
cente. Le sue �nalità sono la partecipazione tra gli studenti di informazioni
sulla vita del Corso di Laurea, la condivisione di appunti e informazioni sugli
esami. Gli utenti attivi, ai sensi della modellizzazione considerata, sono 113
nel primo archivio, 79 nel secondo.
Il terzo gruppo, denominato �Insegnanti�, è composto da 10221 utenti di
Facebook, aventi in comune il fatto di insegnare nelle scuole di ogni ordi-
80
ne e grado. Le tematiche a�rontate sono orientate su due �loni principali:
normativa e sua applicazione da parte dei Dirigenti Scolastici, problematiche
didattiche e relazionali. Gli utenti attivi sono 1547 nel primo archivio, 1650
nel secondo.
Il quarto gruppo, denominato �Il mercatino messinese�, è formato da
20156 utenti ed è dedicato alla pubblicazione di annunci di compravendi-
ta di oggetti vari e scambio di commenti. L'attività si esplica principalmente
nella pubblicazione di annunci di compravendita e nello scambio di informa-
zioni tra l'utente autore del post e gli utenti eventualmente interessati. Il
numero di utenti attivi è 6609 nel primo archivio, 7358 nel secondo.
L'estrazione dei dati è stata e�ettuata in due di�erenti periodi di tempo:
poichè i dati estratti nelle due situazioni si sono mostrati interessanti, in
questa sede vengono mostrati entrambi. Per questi di sintesi e di facilità di
identi�cazione vengono chiamati Archivio 1 e Archivio 2.
Le relazioni tra gli utenti di Facebook appartenenti ai gruppi presi in esame
sono state modellizzate mediante gra�: ogni volta che un utente pubblica
qualcosa (brevemente, �posta�) si presenta come un nodo del grafo. Se un
altro utente commenta il post, anch'egli viene presentato come un nodo e tra
i due nodi viene stabilito un arco orientato dal secondo nodo verso il primo.
Così facendo si ottiene un grafo orientato e pesato, in modo da tenere conto
che le relazioni tra nodi sono più o meno consolidate in base al numero di
commenti che i due utenti si sono reciprocamente scambiati nel periodo di
osservazione.
A seguire, due tabelle con le statistiche generali dei due archivi per ognuno
dei quattro gruppi presi in esame.
81
Archivio 1
Gruppo Nodi Archi ADa AWDb Diametro Densità Componenti
FSS 92 110 1.196 2.467 5 0.013 18
INF 113 1167 10.327 50.097 5 0.092 3
INS 1547 4691 3.032 7.544 10 0.002 136
MER 6609 29903 4.525 16.111 12 0.001 547
aAverage Degree (Grado medio)bAverage Weighted Degree (Grado medio pesato)
Archivio 2
Gruppo Nodi Archi ADa AWDb Diametro Densità Componenti
FSS 104 127 1.221 2.471 7 0.012 21
INF 79 268 3.392 10.253 6 0.043 6
INS 1650 4452 2.698 5.841 9 0.002 162
MER 7358 31986 4.347 14.147 14 0.001 703
aAverage Degree (Grado medio)bAverage Weighted Degree (Grado medio pesato)
Si può notare che i gruppi presi in considerazione sono stati modellizzati
mediante gra� di piccole dimensioni (da un centinaio ad alcune migliaia di
nodi) con un ridotto numero di relazioni. A questo corrisponde una densità
bassissima, un grado medio ridotto e soprattutto, come sarà evidente nel
paragrafo successivo, un elevato numero di componenti.
Nelle tabelle seguenti sono mostrate alcune informazioni sui gruppi esa-
minati, i periodi di osservazioni e la media di post (e di commenti) per utente.
Questi ultimi, insieme al numero degli utenti, sono dati non assolutamente
certi a causa della di�coltà nel reperire automaticamente il numero di utenti
di un gruppo al momento dell'estrazione dei post e dei commenti del gruppo.
82
Si osservi che il gruppo INF è quello che nel primo periodo mostra un'attività
molto elevata per numero medio di post e numero medio di commenti. Que-
sto andamento non viene confermato nel secondo periodo di osservazione:
una possibile spiegazione potrebbe tenere conto del fatto che gli utenti che
hanno fondato e alimentato l'attività del gruppo hanno via via completato
gli studi e di fatto abbandonato il gruppo. Gli studenti delle ultime coorti
hanno preferito fondare nuovi gruppi e frequentano poco il gruppo �storico�
INF.
Archivio 1
Gruppo Inizio Fine Post Comm. Utenti AVG P.a AVG C.b
FSS 21-05-2012 08-11-2013 104 228 520 1,13 2,47
INF 04-12-2010 31-10-2013 1146 5662 132 10,14 50,10
INS 31-08-2013 10-11-2013 2029 11671 10221 1,31 7,54
MER 01-09-2013 10-11-2013 27878 106593 20156 4,21 16,12
aMedia post per utentebMedia commenti per utente
Archivio 2
Gruppo Inizio Fine Post Comm. Utenti AVG P. AVG C.
FSS 21-05-2012 18-01-2014 118 258 520 1,13 2,48
INF 04-04-2013 22-01-2014 218 811 132 2,75 10,26
INS 13-11-2013 23-01-2014 1935 9642 10221 1,17 5,84
MER 01-11-2013 06-02-2014 29984 104424 20156 4,07 14,19
83
6.1 Gra�
In questo paragrafo vengono mostrati i gra� dei quattro gruppi per ognuno
dei due periodi di estrazione dei dati. Dalle Figure 6.1 � 6.8 si può notare
già a prima vista (e verrà mostrato come uno dei risultati della Social Net-
work Analysis) che i gra� non sono connessi. Questo rappresenta un primo
risultato di interesse: al contrario di quanto si sarebbe indotti a pensare, la
partecipazione ad un gruppo non implica necessariamente la relazione tra
tutti i partecipanti. E' possibile distinguere infatti una componente princi-
pale e alcune componenti (a volte nodi singoli) che non hanno mai stabilito
relazioni strutturate con il resto del grafo. I gra�, nonostante le piccole di-
mensioni mostrano chiaramente una componente principale di nodi connessi
e una serie di componenti (ra�gurate alla periferia) disconnesse.
Nelle Figure 6.9 � 6.16 sono mostrate invece le comunità emerse dal-
l'analisi dei gra�. Si ricorda che le comunità sono sottoinsiemi di un grafo
caratterizzate dall'avere un numero di archi più elevato rispetto al numero
di archi che collegano i nodi che ne fanno parte con gli altri nodi.
Le componenti disconnesse sono di fatto delle comunità, sia pur picco-
le, perché nessun arco le connette al resto del grafo. Dall'analisi dei gra� è
emerso un numero relativamente elevato di comunità, con l'unica eccezione
del gruppo INF, che probabilmente è l'unico gruppo caratterizzato da una
elevata comunanza di interessi. Se si eccettua il caso del gruppo INF, nel
quale si riconoscono poche comunità (3 nel primo Archivio, 6 nel secondo),
gli altri gruppi sono caratterizzati da un elevato numero di comunità, a testi-
monianza del fatto che i gruppi esaminati sono in realtà composti da molti (a
volte moltissimi) sottogruppi abbastanza chiusi e poco interessati a stabilire
relazioni con gli altri utenti del gruppo.
84
Figura 6.1: Grafo del gruppo Facebook in the Social Science (Archivio 1)
Figura 6.2: Grafo del gruppo Facebook in the Social Science (Archivio 2)
85
Figura 6.3: Grafo del gruppo del C.d.L. in Informatica (Archivio 1)
Figura 6.4: Grafo del gruppo del C.d.L. in Informatica (Archivio 2)
86
Figura 6.5: Grafo del gruppo Insegnanti (Archivio 1)
Figura 6.6: Grafo del gruppo Insegnanti (Archivio 2)
87
Figura 6.7: Grafo del gruppo Mercatino (Archivio 1)
Figura 6.8: Grafo del gruppo Mercatino (Archivio 2)
88
Figura 6.9: Comunità nel gruppo Facebook in the Social Science (Archivio1)
Figura 6.10: Comunità nel gruppo Facebook in the Social Science (Archivio2)
89
Figura 6.11: Comunità nel gruppo del C.d.L. in Informatica (Archivio 1)
Figura 6.12: Comunità nel gruppo del C.d.L. in Informatica (Archivio 2)
90
Figura 6.13: Comunità nel gruppo Insegnanti (Archivio 1)
Figura 6.14: Comunità nel gruppo Insegnanti (Archivio 2)
91
Figura 6.15: Comunità nel gruppo Mercatino (Archivio 1)
Figura 6.16: Comunità nel gruppo Mercatino (Archivio 2)
92
6.2 Metriche
In questa sezione vengono mostrate le metriche principali della Social Net-
work Analysis. Nelle Figure 6.17 e 6.18 è mostrata la degree centrality di-
stribution riferiti ai due archivi. La degree centrality indica la distribuzione
del grado dei nodi di un grafo, ovvero il numero di relazioni che i nodi hanno
fra di loro. A causa del fatto che le relazioni tra i nodi sono orientate, nelle
Figure sono distinte le distribuzioni riguardanti gli archi entranti (In), uscen-
ti (Out) e totali. L'andamento della degree distribution mostra chiaramente
che esiste una legge di potenza, a dimostrazione che i gra� studiati sono di
tipo scale-free.
Questa caratteristica è confermata dall'esame dei gra�ci della weighted
degree distribution (si vedano le Figure 6.19 e 6.20), in cui vengono rappre-
sentate le distribuzioni del grado pesato di ogni nodo. Si ricorda infatti che i
gra� sono pesati, nel senso che ogni arco tiene conto del numero di commenti
e�ettuati dall'utente ai post dell'utente con cui esiste la relazione.
Nelle Figure 6.21 e 6.22 è mostrata la distribuzione della betweenness
centrality. Si tratta di una misura che tiene conto della centralità di un
nodo rispetto al numero di percorsi minimi che connettono tutte le coppie
di nodi. Come si può osservare dalle Figure, un ridottissimo numero di nodi
viene attraversato da un elevatissimo numero di percorsi minimi, mentre un
numero via via maggiore di nodi si trova in posizioni periferiche di scarso
interesse ai �ni della veicolazione, per esempio, di informazioni sulla rete.
Nelle Figure 6.23 e 6.23 viene mostrata la closeness centrality. La close-
ness (vicinanza) può essere de�nita come l'inverso della farness (lontananza),
che è la somma delle distanze di un nodo da tutti gli altri. Rispetto a questa
metrica, pertanto, un nodo è tanto più centrale quanto minore è la somma
delle distanze da tutti gli altri nodi. In un caso come questo di gra� non
93
connessi, si osserva che una percentuale non nulla di nodi si trova a vicinan-
za nulla, ovvero a lontananza in�nita. Si tratta di quei nodi non connessi,
ovvero delle componenti disconnesse rispetto alla componente principale del
grafo.
Nelle Figure 6.25 e 6.26 viene mostrato l'andamento del coe�ciente di
clustering. Si tratta di una misura della tendenza dei nodi di un grafo a
formare gruppi chiusi, nei quali cioè il numero di archi sia uguale (o prossimo)
al numero massimo, ovveron(n− 1)
2
se con n si indica il numero di nodi.
Il coe�ciente di clustering globale è il rapporto tra il numero di triplette
chiuse di nodi e il numero totale di triplette (aperte o chiuse).
In un grafo completamente connesso (ovvero tra i cui nodi esistano tutti
gli archi possibili), il coe�ciente di clustering è uguale a 1. Dall'esame dei
gra�ci nelle Figure 6.25 e 6.26 appare come i gra� abbiano soltanto una picco-
lissima percentuale di triple chiuse, ad ulteriore dimostrazione della bassissi-
ma densità del grafo. Una signi�cativa eccezione l'andamento del coe�ciente
di clustering del gruppo FSS, in cui non esiste alcuna tripla chiusa di nodi, a
riprova dell'insu�ciente numero di relazioni esistente tra i nodi del gruppo.
94
Figura 6.17: Degree distribution - Archivio 1
Figura 6.18: Degree distribution - Archivio 2
95
Figura 6.19: Weighted degree distribution - Archivio 1
Figura 6.20: Weighted degree distribution - Archivio 2
96
Figura 6.21: Betweenness centrality distribution - Archivio 1
Figura 6.22: Betweenness centrality distribution - Archivio 2
97
Figura 6.23: Closeness centrality distribution - Archivio 1
Figura 6.24: Closeness centrality distribution - Archivio 2
98
Figura 6.25: Clustering coe�cient distribution - Archivio 1
Figura 6.26: Clustering coe�cient distribution - Archivio 2
99
6.3 Andamento temporale post e commenti
In questo paragrafo viene mostrato l'andamento temporale dei post e dei
relativi commenti tracciati su un intervallo di tempo uguale o inferiore al pe-
riodo di osservazione (ed estrazione) dei dati relativi ai vari gruppi. Per ogni
giorno durante il periodo di osservazione è stato estratto il numero di post
pubblicati e il numero di commenti e�ettuati ai post, non necessariamente
del giorno. I risultati sono mostrati nelle Figure 6.27, 6.28, 6.29 e 6.30. Ad
eccezione del gruppo FSS (in cui l'andamento mostra una scarsissima attività
del gruppo), si ha una certa correlazione, non quanti�cata in questa sede, tra
i post pubblicati in un giorno e il numero dei commenti nello stesso giorno.
L'impressione, non è stato condotto uno studio quantitativo sull'argomento,
che l'a�uenza e l'attività degli utenti di un gruppo produca un aumento
anche dei commenti. Un discorso a parte merita l'andamento temporale del
gruppo MER (si veda la Figura 6.30) rispetto al quale esiste qualche dubbio
circa il trend in salita del numero dei commenti. Potrebbe trattarsi di un
e�etto ampli�cato del trend in salita dei post, ma potrebbe anche trattarsi
di una incompleta estrazione di dati dalla base di dati di Facebook per le
motivazione esposte in precedenza.
100
Figura 6.27: Andamento temporale dei post e dei commenti - Gruppo FSS
Figura 6.28: Andamento temporale dei post e dei commenti - Gruppo INF
101
Figura 6.29: Andamento temporale dei post e dei commenti - Gruppo INS
Figura 6.30: Andamento temporale dei post e dei commenti - Gruppo MER
102
6.4 Tipologia di allegati
In questo paragrafo vengono fornite alcune informazioni sulla tipologia di
allegati. Nelle Figure 6.31 e 6.32 sono presentate, sotto forma di istogrammi,
le percentuali degli allegati dei post e dei commenti, rispettivamente. Ad ec-
cezione del gruppo MER, di cui si parlerà a breve, gli allegati non sono molto
presenti, e contrariamente a quanto si potrebbe pensare i post e i commenti
sono essenzialmente testuali, con una bassissima percentuale di allegati. Si
discostano le abitudini del gruppo INS, in cui c'è una percentuale rilevante di
collegamenti ipertestuali e, come si accennava, quelle del gruppo MER, in cui
la maggioranza dei post (e dei commenti) contiene fotogra�e. Quest'ultima
è una peculiarità abbastanza normale per un gruppo di compravendita, in
cui è abituale e preferibile associare una o più fotogra�e al prodotto che si
intende vendere.
103
Figura 6.31: Percentuale degli allegati sui post - Archivio 1
Figura 6.32: Percentuale degli allegati sui post - Archivio 2
104
Capitolo 7
Conclusioni e Sviluppi Futuri
I computer sono inutili, possono dare solo
risposte.
Pablo Picasso
Il progetto di tesi ha raggiunto lo scopo pre�ssato: l'acquisizione di dati
da gruppi di Facebook chiusi e la realizzazione di �le GraphML per ogni
gruppo, al �ne di produrre un grafo orientato e pesato per poter analizzare
le interazioni tra gli utenti all'interno dei vari gruppi.
Il lavoro si è rivelato molto faticoso e lungo anche se produttivo ed istruttivo
sotto diversi punti di vista: la scoperta dei meccanismi di autenticazione e
di interrogazione dei database che utilizza Facebook, un miglioramento per-
sonale per quanto concerne la programmazione con PHP e la realizzazione
dell'applicativo.
Diverse sono state le di�coltà nella realizzazione del progetto, specie all'i-
nizio. Tra queste si ricordano il codice per l'interfacciamento a Facebook
tramite le API, così come le questioni legate ai token. Il motivo può essere
cercato nella Documentazione u�ciale che all'epoca non era molto ben orga-
nizzata. Come se non bastasse, trattandosi di un'idea abbastanza innovativa,
105
non si trovavano molti aiuti nelle varie community informatiche.
Altre di�coltà importanti si sono avute quando, analizzando i dati estratti,
ci si è accorti di problemi di integrità dei dati: in archivio erano presenti dei
commenti che facevano riferimento a dei post non memorizzati oppure dei
post ai quali mancavano dei commenti. Purtroppo, tali problemi sono da at-
tribuire all'acerba piattaforma FQL con i vari problemi derivanti dall'utilizzo
del LIMIT o da improvvisi blocchi e quindi non esecuzione della query. Da
segnalare il fatto che, se Facebook non imponesse tutti questi limiti nell'e-
secuzione delle query FQL, sarebbe bastato semplicemente eseguire lo script
una sola volta per poter ottenere tutti i post ed i commenti di un gruppo a
partire dalla sua creazione.
Non è stato meno di�coltoso lo sviluppo dell'applicazione in C# specie nella
parte della creazione del �le GraphML poiché si è preferito programmare per-
sonalmente i vari algoritmi senza utilizzare librerie esterne che producono
automaticamene il �le.
Alcune ri�essioni sull'analisi dei dati estratti sono doverose: contrariamente
a quanto si possa pensare, non sempre i gruppi sono dei luoghi di socializza-
zione tra gli utenti. Tra i quattro gruppi presi in esame, soltanto nel gruppo
INF si può parlare di una vera e propria interazione e socializzazione tra la
maggior parte degli utenti. Nei restanti tre gruppi (in particolare in INS e
MER) è evidente un'elevata frammentarietà ed un numero elevato di compo-
nenti, cioè dei �sottogruppi� dentro i quali non sempre vi è un'interazione tra
gli utenti. A titolo d'esempio: nel gruppo MER è possibile notare centinaia
di componenti che fanno desumere una frammentarietà nelle relazioni, anche
perché diverse relazioni del gruppo possono essere ricondotte a un semplice
post �vendo oggetto� , il quale può ricevere un'eventuale risposta �sono inte-
ressato, possiamo concludere� e l'interazione tra due utenti si conclude. Altra
106
eventualità è che i post non ricevano neanche una risposta ed il messaggio
resti isolato.
Tra gli sviluppi futuri del progetto, l'analisi di gruppi più grandi ed attivi
rispetto a quelli presi in esame e l'acquisizione dei dati per periodi più lunghi
al �ne di ottenere dati più accurati per l'analisi. Altre possibilità, sono l'a-
dattamento dei software per poter essere utilizzati anche in ambito di analisi
forense e social media marketing.
107
Capitolo 8
Bibliogra�a e Sitogra�a
8.1 Le Reti Sociali
1. Social Network Analysis Applicata di Giovanni Carturan
http://www.slideshare.net/gio85pd/social-network-analysis-applicata
2. Dipartimento di Scienze Sociali dell'Università di Pisa, L'analisi delle
reti sociali
http://sna.dss.unipi.it/Analisi%20delle%20reti.html
3. Handbook of Social Network technologies and Applications
http://mylifemynotes.�les.wordpress.com/2012/03/handbook-of-social-network-
technologies-and-applns-b-furht-springer-2010-bbs.pdf
4. Analisi delle reti sociali
http://it.wikipedia.org/wiki/Analisi_delle_reti_sociali
5. Rete sociale
http://it.wikipedia.org/wiki/Rete_sociale
108
6. Tu la sapevi la di�erenza tra social media e social network?, di Vero-
nica Gentili
http://www.veronicagentili.com/tu-la-sapevi-la-di�erenza-tra-social-media-
e-social-network/
8.2 Teoria dei gra�
1. Teoria dei gra�
http://it.wikipedia.org/wiki/Teoria_dei_gra�
2. Grafo
http://it.wikipedia.org/wiki/Grafo
3. Alberi e Gra� - Dipartimento di Sistemi e Informatica
www.dsi.uni�.it/∼costa/lucidi_fondII_ing_06_07/25.Alberi.pdf
4. Teoria dei Gra� - Dist
www.dist.unige.it/msanguineti/AttDid/RO1SV/D11.pdf
5. 4. Elementi di Teoria dei Gra� - Dipartimento di Matematica
www.mat.uniroma3.it/users/liverani/doc/disp_oc_04.pdf
8.3 Reti complesse
1. Statistical mechanics of complex networks, Re ka Albert and Albert-La
szlo Baraba si Department of Physics, University of Notre Dame, Notre
Dame, Indiana 46556 (Published 30 January 2002)
2. ScaleFree_Scienti�c American 288, 60-69 (2003), by Albert-Laszlo Ba-
rabasi and Eric Bonabeau
109
3. Introduzione alle reti complesse
http://www.quattromaggio.altervista.org/TesieProgetti/Tesi-Marziale/Capitolo1.pdf
4. RETI COMPLESSE, di Rodolfo Baggio, Gennaio 2004
www.iby.it/itc/baggio_reti.pdf
5. Università di Genova, Reti complesse, reti e misure, Matteo dell'Ami-
co, 7 novembre 2006
http://www.disi.unige.it/person/DellamicoM/teaching/ar2-0607/2-misure.pdf
6. Università degli studi di Torino, Network Complessi e modelli, Rossano
Gaeta
http://www.di.unito.it/∼rossano/DIDATTICA/bioinfo/network-complessi-
e-gra�.pdf
7. Complex Network
http://en.wikipedia.org/wiki/Complex_network
8. Directed graph
http://en.wikipedia.org/wiki/Indegree#Indegree_and_outdegree
9. Centrality
http://en.wikipedia.org/wiki/Betweenness#Betweenness_centrality
10. Degree distribution
http://en.wikipedia.org/wiki/Degree_distribution
11. Clustering coe�cient
http://en.wikipedia.org/wiki/Clustering_coe�cient
12. Betweenness centrality
http://en.wikipedia.org/wiki/Betweenness_centrality
110
13. Closeness Centrality
http://sonivis.org/wiki/index.php?title=Closeness
14. Modularity (networks) http://en.wikipedia.org/wiki/Modularity_(networks)
15. Modularità (reti)
http://it.wikipedia.org/wiki/Modularità_(reti)
16. Distance (graph theory)
http://en.wikipedia.org/wiki/Distance_(graph_theory)
17. Scale-free network
http://en.wikipedia.org/wiki/Scale-free_networks
18. Erd®s�Rényi model
http://en.wikipedia.org/wiki/Erdos-Renyi-model
19. Small-world network
http://en.wikipedia.org/wiki/Small-world_network
20. Clique (graph theory)
http://en.wikipedia.org/wiki/Clique_(graph_theory)
21. Distribuzione di Poisson
http://it.wikipedia.org/wiki/Distribuzione_di_Poisson
22. Sei gradi di separazione
http://it.wikipedia.org/wiki/Sei_gradi_di_separazione
23. Power law
http://en.wikipedia.org/wiki/Power-law
24. Legge di potenza
http://it.wikipedia.org/wiki/Legge_di_potenza
111
25. Random Graph
http://en.wikipedia.org/wiki/Random_graph
26. Small-World Network
http://en.wikipedia.org/wiki/Small-world_network
8.4 Facebook
1. Facebook
http://it.wikipedia.org/wiki/Facebook
2. SDK
http://it.wikipedia.org/wiki/Software_development_kit
3. API
http://it.wikipedia.org/wiki/Application_programming_interface
4. Applicazione Facebook con PHP di Mariano Calandra
http://www.html.it/guide/guida-applicazioni-facebook-con-php/
5. FQL
https://developers.facebook.com/docs/technical-guides/fql/
6. Access Token
https://developers.facebook.com/docs/facebook-login/access-tokens/
8.5 Progetto
1. Draw.io
https://www.draw.io/
112
2. PHP
http://it.wikipedia.org/wiki/PHP
3. C#
http://it.wikipedia.org/wiki/C_sharp http://www.php.net
4. SQL
http://it.wikipedia.org/wiki/SQL
5. FQL: Tabella Stream
https://developers.facebook.com/docs/reference/fql/stream/
6. FQL: Tabella Comment
https://developers.facebook.com/docs/reference/fql/comment/
7. Facebook
https://www.facebook.com/
8. Diagramma ER
http://www.ballini.it/Software/ProgER/
9. Microsoft Visual Studio
http://www.visualstudio.com/
http://it.wikipedia.org/wiki/C_sharp
10. GraphML, Graph Markup Language (GraphML), Ulrik Brandes Uni-
versity of Konstanz, Markus Eiglsperger Zuehlke Engineering AG, Juer-
gen Lerner University of Konstanz, Christian Pich ETH Zurich
http://graphml.graphdrawing.org/
http://it.wikipedia.org/wiki/XML
11. Gnuplot
http://www.gnuplot.info/
113
