Dispersion centrality: applicazionedella dispersione in casi di studio reali

Amedeo Leo | Alessio Petrozziello | Simone Romanoamedeo.leo92@gmail.com | alessio92p@gmail.com | s.romano1992@gmail.com

Università degli Studi di Salerno

Abstract

In questo lavoro si vogliono mostrare alcuni casi di studio reali in cui la dispersione[1](unanuova misura per Social Network Analysis) è utilizzata per evidenziare nodi all’interno diuna rete con particolari caratteristiche. In particolare verrà mostrato come la Dispersioncentrality(nuova misura che introdurremo) insieme alla Betweenness centrality rappresentanoun metodo efficace per isolare nodi che si differenziano dal resto della rete.

1. Introduzione

L’articolo [1] mostra la dispersione, un’unità dimisura applicabile agli archi di un grafo. Lo stu-dio proposto parte da un’analisi di tale misuraper confrontarla con alcune delle misure già pre-senti e diffuse in letteratura(degree centrality,closeness centrality, betweenness centrality) epunta a cercare una relazione con queste. Inparticolare scopo dello studio è utilizzare la dis-persione in unione ad una delle altre misureper ricavare informazioni aggiuntive inerenti lastruttura della rete analizzata. Ciò che seman-ticamente rappresenta la dispersione è quantoamici in comune di due nodi non sono bencollegati. Innanzitutto quello che è stato fattoè portare una misura applicata ad archi(quale ladispersione) ad un singolo nodo, introducendola dispersion centrality definita, a partire daun nodo, come la somma delle dispersioni datutti i suoi vicini. Per ricavare dei risultati val-utabili è stata implementata una libreria scrittain python utilizzando la libreria [2]. Tale libre-ria consente, dato un grafo in input in formatoedge, di calcolare per tutti i nodi del grafo alcunedelle misure principali utilizzate in social net-work analysis aggiungendo dunque la dispersioncentrality e di stampare i risultati in formato.cvs analizzabile poi con altri tool descritti inseguito. I paragrafi successivi formalizzerannoin maniera più precisa il concetto di dispersionecosì come proprosto in [1]; a questo punto ver-ranno dettagliate le metodologie utilizzate, i casi

di studio e i risultati. Verranno dunque propostedelle conclusioni.

2. Dispersione

Nella sociologia matematica, i legami interper-sonali sono definiti come connessioni che “in-globano” delle informazioni tra le persone. Laforza di un legame costituisce una dimensioneimportante in cui si possono caratterizzare i col-legamenti di una persona ai suoi “vicini di rete”.Informalmente, si riferisce alla vicinanza di uncollegamento: definisce un insieme che varia dalegami forti a deboli; i primi sono spesso incor-porati nella rete, circondati da un vasto numerodi vicini, mentre gli ultimi coinvolgono spessopochi vicini e sono utilizzati come “ponti” perdiverse zone della rete, fornendo accesso a im-portanti informazioni. Il punto critico è dunqueidentificare gli individui più importanti in unarete sociale. La caratteristica fondamentale inqueste analisi è l’embeddedness (“annidamento”o “radicamento”): è una quantità che tipica-mente aumenta con la forza dei legami, poichérappresenta il numero di persone che due nodivicini hanno in comune. Tuttavia, è un mezzodebole per poter identificare le relazioni di unarete. In questo lavoro proponiamo una mis-urazione alternativa, chiamata dispersione, cheè significativamente più efficace. Tale misuranon prende in considerazione solo il numero diindividui comuni a due persone, ma anche allastruttura della rete determinata da questo nu-

1

mero; approssimativamente, una connessione tradue persone ha un’alta dispersione quando i lorovicini non sono connessi tra loro. La dispersioneriflette la teoria del “social foci”: molte per-sone hanno grandi gruppi (o “cluster”) di amicio conoscenti corrispondenti a interazioni bendefinite nella loro vita, come, nel nostro casodi studio, individui che frequentano un dojoe relativi istruttori oppure una rete criminalecon i corrispondenti boss. Poiché molte personeall’interno di tali cluster si conoscono, questi ul-timi contengono dei link con alta embeddedness,anche se non corrispondono necessariamente alegami particolarmente forti. Al contrario, i col-legamenti agli amici di una persona possonoavere radicamento minore, ma coinvolgono ivicini comuni di investimento da numerosi ediversi foci. Quindi, invece dell’embeddedness,ipotizziamo che i collegamenti tra un nodo u e unsuo vicino v riflettano una struttura “dispersa”:in tal modo, i vicini comuni di u e v non sonoben connessi l’un l’altro, e quindi u e v agisconocongiuntamente come gli unici intermediari traqueste diverse parti della rete.

Per poter definire la dispersione in terminimatematici, formuliamo una serie di definizioni:per iniziare, consideriamo Gu come il sottografoindotto su u e sui suoi vicini, e per ogni nodo vdefiniamo Cuv come l’insieme dei vicini comunidi u e v. Per esprimere l’idea che le coppie dinodi in Cuv devono essere distanti in Gu quandonon consideriamo i path in due step attraverso ue v stessi, definiamo la dispersione assoluta dellacollegamento u-v, disp(u,v), come la somma ditutte le distanze a coppie tra i nodi in Cuv, mis-urata in Gu - u, v; ovvero,

disp(u, v) =∑

s,t∈Cuv

dv(s, t)

dove dv è la distanza tra due nodi in Cuv;tale distanza dv (s,t) equivale a 1 se s e t nonsono direttamente connessi e non hanno nodi incomuni in Gu, oltre a u e v stessi, e equivale a 0altrimenti. Nei nostri casi di studio intervengonoanche altre misurazioni: la dispersione normal-izzata, norm(u,v), definita come il rapporto trala dispersione e l’embeddness; da questa sonostate create altre due metriche per aumentare le

prestazioni: la prima è la dispersione parametriz-zata, definita da:

(disp(u, v) + b)α

emb(u, v) + c

La seconda è l’applicazione della dispersione inmaniera ricorsiva: individuare i nodi v il cuicollegamento u-v raggiunge una elevata disper-sione normalizzata sulla base di una serie divicini comuni Cuv, che, a loro volta, hanno altadispersione normalizzata nei loro legami con u.Per realizzare questa idea, assegniamo valori ainodi che riflettono la dispersione nei loro legamicon u, e quindi aggiorniamo questi valori conquelli di dispersione associati ad altri nodi. Inparticolare, definiamo xv= 1 per tutti i vicini vdi u, e aggiorniamo iterativamente ogni xv:

xv =

∑w∈Cuv

x2w + 2

∑s,t∈Cuv

dv(s, t)xsxtemb(u, v) + c

Tuttavia, tali misurazioni, data una coppiadi nodi definita da un arco, determinano uninsieme di valori: per poter confrontare i risul-tati ottenuti, occorrerebbero nuove funzioni cherestituiscono una sola misura. Per questo obiet-tivo, abbiamo definito diverse nuove metriche:centralità di dispersione, dispersione massima,dispersione minima, dispersione media. Tali fun-zioni non si basano su una coppia di nodi, masu un singolo nodo: determinano quanto questonodo venga coinvolto nel calcolo delle disper-sioni dei suoi vicini. Sommando le dispersionidi tali vicini, ne abbiamo determinato l’effettivamisurazione, la dispersione massima, la minimae la media. Inoltre, abbiamo effettuato i testsui grafi anche su altre funzioni ben note: labetweenness centrality, la degree centrality e lacloseness centrality. La prima, per un nodo v, èdeterminata dall’espressione

g(v) =∑s 6=v 6=t

σs,t(v)

σs,t

Dove σst è il numero totale di cammini min-imi da s a t e σst è il numero di tali camminiche attraversano v. La degree centrality è statauna delle prime metriche sviluppate: è definitacome il numero di archi incidenti su un nodo,

2

ovvero la quantità di legami che ha un nodo.Nei nostri casi di studio, gli archi non sono di-rezionati, quindi useremo solo una misurazione(e non indegree o outdegree). Il significato datoda tale metrica è rappresentato dal fatto chegli individui più importanti sono coloro con piùlegami nella rete. La closeness centrality, invece,misura quanti passaggi devono essere fatti, par-tendo da un nodo v, per raggiungere il maggiornumero possibile di nodi. In tal caso, la personapiù importante può raggiungere facilmente lealtre nella rete.

3. Metodologie

Durante lo sviluppo di questo progetto ci siamoavvalsi del supporto di diverse tecnologie per lamanipolazione e visualizzazione dei grafi tra cui:

• Python• Xml• Csv• Snap• Gephi• Cran-R• Weka

3.1. PythonPython è un linguaggio di programmazione di-namico orientato agli oggetti utilizzabile permolti tipi di sviluppo software. Offre un fortesupporto all’integrazione con altri linguaggi eprogrammi, è fornito di una estesa libreria stan-dard e può essere imparato in pochi giorni. Moltiprogrammatori Python possono confermare unsostanziale aumento di produttività e ritengonoche il linguaggio incoraggi allo sviluppo di codicedi qualità e manutenibilità superiori. Pythongira su Windows, Linux/Unix, Mac OS X, OS/2,Amiga, palmari Palm e cellulari Nokia; è statoanche portato sulle macchine virtuali Java e.NET.

3.2. SnapStanford Network Analysis Platform (SNAP) èuna libreria per network analysis e graph mining.E’ scritta in C++ e scala facilmente con grafi

massivi con centinaia di milioni di nodi e miliardidi archi. E’ capace di manipolare grafi moltograndi, calcolare proprietà strutturali, gener-are graphi random e regolari e supporta gli at-tributi su nodi e archi. Snap.py è una interfacciaPython per SNAP. Essa provvede le performancedi SNAP, uniti alla flessibilità di Python. Moltedelle funzioni di SNAP in C++ sono disponibilinella libreria Snap.py

3.3. GephiGephi è un tool di visualizzazione ed esplo-razione interattiva di qualsiasi tipo di rete,sistemi complessi, grafi dinimaci e gerarchici.Gephi gira su Windwos, Linux e OS X. E’ open-sorce e free

3.4. ImplementazioneVarie funzioni necessarie e di supporto sono statesviluppate tra cui:

• fromGexfToEdge: permette la trasfor-mazione da un file di gephi ad un file ditipo EDGE, importabile in SNAP

• commonNeighbors: permette di trovare ilvicinato comune tra due nodi

• dispersion: calcola la dispersione tra duenodi, così come da formula

• embeddedness: corrisponde al vicinato co-mune tra due nodi

• norm: calcola la dispersione normalizzata

dispersione

embeddedness

• performance: calcola la norma aggiun-gendo dei parametri costanti di ottimiz-zazione

• recDisp: calcola la dispersione ricorsiva daun nodo a tutti gli altri come da formula

• printNodeInformations_XML: crea un fileXML con tutti le informazioni su ogninodo del grafo (degree centrality, between-ness centrality, closeness centrality, disper-sion centrality)

• dispersionCentrality: calcola la disper-sione su ogni nodo vicino e ne effettuala somma

3

• printNodesInformations_CSV: crea un fileCSV con tutte le informazioni sui nodi,standard facilmente importabile in CRAN-R o Weka, tool di data analisys

4. Casi di studio

Al fine di valutare quanto ipotizzato in fase dianalisi del problema sono stati studiati alcunicasi reali. In particolare il primo caso studi-ato è stato quello rappresentatne un club dikarate(presentato in [3]). Lo studio [3] risaleal 1977. Gli autori hanno osservato il compor-tamento del club di karate dal 1970 al 1972,registrando ciò che accadeva all’interno del club.In particolare il club era formato da due istrut-tori i quali, a seguito di litigi dovuti a disaccordisul prezzo delle lezioni, litigarono. La rete si di-vise in due parti, ciascuna con a capo uno degliistruttori e i relativi allievi. Infine, ulitmo casodi studio è il grafo di una rete criminale. Ciò chesi vuole mostrare è che la dispersion centralityconsente di evidenziare nodi che rappresentanonodi particolari(dal punto di vista semantico)all’interno del grafo.

5. Risultati

Di seguito sono mostrati e commentati i risul-tati dei test effettuati sui vari casi di studio.Le metriche utilizzate per analizzare i risultatidella dispersion centrality sono degree centrality,closeness centrality e betweenness centrality.

5.1. Karate

Nella figura seguente si evince che, nella rete delKarate analizzata, esiste una netta correlazionetra betweenness centrality e dispersion central-ity, come si può notare nel relativo quadrante.In particolare gli outlier rappresentano i nodi1, 34, 33 relativi ai 3 nodi più importanti dellarete ovvero il capo istruttore e i 2 maestri.

id

0.1 0.2 0.3 0.4 0.5

●

● ●●●● ●●

● ●●● ● ●

●●

●

●●

●

●●

●

●●●

●●●

●●

●

●●

●

● ●●●●●

● ● ●●●●

●

●●

●

●●

●

●●

●

●●●

●●●

●●

●

●●

0 50 100 150 200

●

● ●●●● ●●

● ●●●● ●

●●

●

●●

●

●●

●

●●●

●●●

●●

●

●●

010

2030

●

● ●● ●●●●

●●●●●●

●●●

●●

●

●●

●

●●●

●●●

●●

●

●●

0.1

0.3

0.5 ●

●

●

●

●

●●●●

●

●

●●

●

●●

●

●

●

●

●●

●

●●● ● ● ●●

●●

●●

degree_centrality

●

●

●

●

●

●●● ●

●

●

●●

●

●●

●

●

●

●

●●

●

● ●●●●●●

●●

●●

●

●

●

●

●

●●●●

●

●

●●

●

●●

●

●

●

●

●●

●

●●●●●●●

●●●●

●

●

●

●

●

●●●●

●

●

●●

●

●●●

●

●

●

●●

●

●●●●●●●

●●

●●

●

●

●●

●

●●●

●

●

●●●

●

●

●

●

●

●

●

●●

●

●

●● ● ● ● ●● ●●

●

●

●

●●

●

● ●●

●

●

●● ●

●

●

●

●

●

●

●

●●

●

●

●●●●● ●●●●

●

closeness_centrality

●

●

●●

●

● ●●

●

●

●●●

●

●

●

●

●

●

●

●●

●

●

●●●●●●●●●

●

0.30

0.40

0.50

●

●

●●

●

●●●

●

●

●●●

●

●

●

●

●

●

●

●●

●

●

●●●●●●●●●

●

050

150 ●

●

●

●

●●●●

●

●

●●●

●

●●

●

●

●●●

●

●

●●● ● ● ● ●● ●● ●

●

●

●

●

●●●●●

●

●● ●

●

●●

●

●

●●●

●

●

●●●●●● ● ●●●●

●

●

●

●

●●●●

●

●

●●●

●

●●

●

●

●●●

●

●

● ●●●●●●●●●●

betweenness_centrality

●

●

●

●

●●●●

●

●

●●●

●

●●●

●

●●●●

●

●●●●●●●●●●●

0 5 10 15 20 25 30 35

●

●

●

●●

●●●●● ●●●● ● ● ● ●●● ●●

●

●●● ● ● ● ●● ●● ●

●

●

●

●●

● ●●● ●●● ● ●● ●● ●●● ●●

●

●●●●●● ● ●●●●

0.30 0.40 0.50

●

●

●

●●

●●● ● ●●●● ●● ●● ●●● ●●

●

● ●●●●●● ●●●●

●

●

●

●●

● ●●● ●●●● ●● ●● ●●● ●●

●

●●●●●●●●●●●

0 10 20 30 40

010

2030

40

dispersion_centrality

5.2. Rete criminaleLa figura seguente mostra i risultati ottenutiapplicando le stesse metriche ad una rete crimi-nale. Ciò che si evince è, ancora una volta, chegli outlier evidenziati dalla betweenness central-ity sono gli stessi evidenziati dalla dispersioncentrality.

id

0.00 0.05 0.10 0.15 0.20

●

●●

● ●

●●●

●

●●

●

●●

●

●

●●●

●●

●

●

●

●

●

●●●

●●

●●

●●

●

●● ●●●●●●

●

●

●

● ●●

●

●●●●

●

●●

●

●●

●

●●●

●

●

●

●

●●●●●●●

●

●

●●●

●●●●

●●●●●●

●●

●●

●

●

●

●

●

●

●●

●●● ●

●●●●

● ●● ●●●●●●●●●●●●●

●

●●●

●●●

●

●

●●●●

●●

●●●●●●●●●●●

●

●

●●

● ●

●●●

●

●●

●

●●

●

●

●●●

●●

●

●

●

●

●

●●●

●●

●●

●●

●

●●●●●●●●

●

●

●

●●●

●

●●●●

●

●●

●

●●

●

●●●

●

●

●

●

●●●●●●●

●

●

●●●

●●●●

●●●●●●

●●

●●

●

●

●

●

●

●

●●●●● ●

●●●●

● ●● ●●●●●●●●●●●●●

●

●●●

●●●

●

●

●●●●

●●

● ● ● ●●● ●●●●

●

●

0 1000 2000 3000 4000

●

●●

● ●

●●●

●

●●

●

●●

●

●

●●●

●●

●

●

●

●

●

●●●

●●

●●

●●

●

●●●●●●●●

●

●

●

● ●●

●

●●●●

●

●●

●

●●

●

●●●

●

●

●

●

●●●●●●●

●

●

●●●

●●●●

●●● ●●●

●●

●●

●

●

●

●

●

●

●●●●●●

●●●●

●●●●●●●●●●●●●●●●

●

●●●

●●●

●

●

●●●●

●●

●●●●●●●

●●●●

●

050

100

●

●●

● ●

●●●

●

● ●

●

●●

●

●

●●●

●●

●

●

●

●

●

●●●

●●

●●

●●

●

●●●●●●●●

●

●

●

● ●●

●

●●●●

●

●●

●

●●

●

●●●

●

●

●

●

●●●●●●●

●

●

●●●

●●●●

●●●●●●

●●

●●

●

●

●

●

●

●

●●●●●●

●●●●

●●●●●●●●●●●●●●●●

●

●●●

●●●

●

●

●●●●

●●

●●●●●●●●●●●

●

0.00

0.10

0.20

●

●●

●

●

●●●

●

●

●

●●

●

●

●●●●●●

●●●

●

●

●●

● ●●●●

●

●

●

●●●●●●●●

●

● ●●

●

●

●

●●●

● ● ●●● ●

●●●●● ●

●●●

●●●●●●●

●●●

●●●●●●

●

●●●●● ●●

●●

●● ●

●

● ●

●●

●●●●

●●●●

●

●●●●●●●●●●●●●

●● ●●●●

●●

●●

●●●● ● ●●●●●●●●●● ●●● ●

degree_centrality●

●●

●

●

●●●●

●

●

●●

●

●

●●●●●●

●●●

●

●

●●

●●●●●

●

●

●

●●●

●●●●●

●

● ●●

●

●

●

●●●

●●●●● ●●

● ●●●●●

●●

●●●●●●●●●●●●●●●●

●

●●●

●●●●

●●

●●●

●

●●

●●●●●

●●

●●●●

●●●

●●●●●●●●●●

●●●●●●

●●●●

●●●●●●●● ● ●●●

● ●● ●●● ●

●

●●

●

●

●●●

●

●

●

● ●

●

●

●●●●●●

●●●

●

●

●●

●●●●●

●

●

●

●●●●●●●●

●

● ●●

●

●

●

●●●●●●●

● ●●●●●●●●●●

●●●●●●●●●●●●●●●●

●

●● ●●●●●

●●

●●●

●

●●

●●●●●●●

●●●●

●●●●●●●●●●●●●

●●●●●●

●●

●●●●●●●●●●●●●●●●●●●●●

●

●●

●

●

●●●

●

●

●

●●

●

●

●●●●●●

●●●

●

●

●●

●●●●●

●

●

●

●●●●●●●●

●

●●●

●

●

●

●●●●●●●●●●●●●●●

●●●

●●●●●●●●●●●●●●●●

●

●●●●●●●

●●

●●●

●

●●

●●●●●●

●●●●●

●●●●●●●●●●●●●

●●●●●●●●●●●●●●●●●●●●●●●●●●●●●

●

●●●●

●●●●●● ●●

● ● ●●●●●●

●●●

●●●●● ●●● ●

●● ●

●●●●●●●●●

●

●●●●

●●●

●● ● ●●

●●● ●

●●● ●● ●● ● ●●●●●● ●●●●● ●●●●

●●●●●● ●●

●●

●● ●●

● ●● ●●●●

●●●●

●●

●●

●

●●●●●●●●●●

●●

●●●●

●●●● ●●●

●●

●●●●

●

●

●●

●●

●●●

●

●

●●●

●

●●● ●●●●●

● ●●●●●●●

●●●

●● ●●●●●●●

●● ●

●● ●●●●●●●

●

●● ●●

●●●

●●●●●

●●

●●

●●●● ●●● ●●●●●●●●●●●●●●●●

●●●●●●●●

●●

● ●●●

●●●●●●

●

●●

●●●●

●●

●

●●●●●●●●●●

●●

●●●●

●● ●●●●●

●●●●●●

●

●

●●

●●●●●

●

closeness_centrality●

●●●

●

●●● ●●●● ●

● ●●●●●●●●●●

●● ●●●●●●●

●● ●●●●●●●●●

●●

●● ●●

●●●●●●●●

●●

●●

●●●●●●● ●●●●●●●●●●●●●●●●

●●● ●●●●●

●●

●●●●●●

●●●●●

●●

●●●●

●●

●

●●●●●●●●●●

●●

●●●●

●● ●●●●●●●●●●●

●

●

●●

●●●●●

●

0.2

0.6

1.0

●

●●●

●

●●● ●● ●●●

● ●●●●●●●●●●

●●●●●●●●●

●● ●

●●●●●●●●●●

●● ●●●●●●●●●●●●●●

●●●●●●●●●●●●●●●●●●●●●●●

●●●●●●●●

●●●●●

●●●

●●●●●

●●

●●●●

●●

●

●●●●●●●●●●

●●

●●●●●●●●●●●●●●●●●

●

●

●●

●●●●●

●

020

0040

00

●

●●

●

●

●●●

●

●

●

●

●

●● ●

●●●●● ● ●●

●

●●●

● ●●● ●

●

●

●

●●●●●●●●●

●●

●

●

●

●

●● ●● ● ●●●●

● ●●●● ●● ●●

●

●●●●●● ●●●●● ●●●●

●

●●

●

●● ●●

●●

●● ●● ● ●●

●●●●● ●●●●●●●●●●●●●●●●●●●● ●●●●●●

●

● ●●●● ● ●●●●●●●●●● ●●● ●

●

●●

●

●

●●●

●

●

●

●

●

●●●

●●● ●●● ●●

●

●●●

●●●●●

●

●

●

●● ●●●●●●●

●●

●

●

●

●

●●●●●●● ●●

●●●●●● ●●●

●

●●●●●●●●●●●●●●●

●

●●

●

●●●●

●●

● ●● ●●●●

●●●● ● ●●●●● ●● ●●●●●●●●●●●●●●●●●●

●

●

●●●●●●●●●●●●●●●●●●●●

●

●●

●

●

●●●

●

●

●

●

●

●●●●●● ●●● ●●

●

●●●●●●●●

●

●

●

●●●●●●●●●

●●

●

●

●

●

●● ●●●●●●●

●● ●●●●●●●

●

●●●●●●●●●●●●●●●

●

●●

●

●●●●

●●

●●●●●●●●●●● ●●●●●● ●● ●●●●●●●●●●●●●●●●●●

●

●

●●●●●●●●● ● ● ●●● ●● ●●● ●

betweenness_centrality

●

●●

●

●

●●●

●

●

●

●

●

●●●

●●●●●●●●

●

●●

●●●●●●

●

●

●

●●●●●●●●●●●●

●

●

●

●●●●●●●●●

●●●●●●●●●

●

●●●●●●●●●●●●●●●

●

●●

●

●●●●

●●

●●● ●●●●

●●●●● ●●●●●●●●●●●●●●●●●●●●●●●●●●

●

●●●●●●●●●●●●●●●●●●●●

0 50 100 150

●

●●

●

●

●●●

●●

●

●●●

●

●●●●●● ● ●●

●

●●●● ●●● ●

●●

●

●●●●●●●●● ● ●●

●

●● ●● ●● ● ●●● ●● ●●●● ●● ●● ● ●●●●●● ●●●●● ●●●●●●●●●● ●●●● ●● ●

●

● ●● ●●●●●

●

●●●●●●●●●●●●●●●●●●● ●●●● ●●●● ●●●● ● ●●●●●●●●●● ●●● ●

●

●●

●

●

●●●

●●

●

●●●

●

●●●● ●●● ●●

●

● ●●●●●●●

●●

●

●● ●●●●●● ●●● ●

●

● ●●●●●●●● ●●●●●●●● ●●● ●●●●●●●●●●●●●●●● ●●●●●●●● ● ●● ●●

●

●● ●●●●● ●

●

●●●● ●● ●●●●●●●●●●●●●●●●● ●● ●●●●●●●●●●●●●●●●●●●●●

0.2 0.4 0.6 0.8 1.0

●

●●

●

●

●●●

●●

●

●●●

●

●●●● ●●● ●●

●

●●●●●●●●

●●

●

●●●●●●●●●● ●●

●

● ●●● ●●●●●● ●●● ●●●●●●●●●●●●●●●●●●●●●●● ●●●●●●●● ●●●●●

●

●● ●●●●● ●

●

●●●● ●● ●●●●●●●●●●●●●●●●● ●●●●●●●●●●●● ● ● ●●● ●● ●●● ●

●

●●

●

●

●●●

●●

●

● ●●

●

●●●●●●●●●

●

● ●●●●●●●

●●

●

●●●●●●●● ●● ●●

●

● ●●●●●●●●● ●●●●●●●●●● ●●●●●●●●●●●●●●●● ●●● ●●●●● ●●●●●

●

●●●●●●●●

●

●●●●●●●●●●●●●●●●●●●●●●● ●● ●●●●●●●●●●●●●●●●●●●●●

0 10 20 30

010

2030

dispersion_centrality

6. Conclusioni

Partendo dall’analisi della dispersione[1](unitàapplicabile ad un arco di una rete) abbiamo con-siderato, dato un nodo, la somma delle disper-sioni tra questo nodo ed i suoi vicini(dispersioncentrality) in modo da ottenere una misuraconfrontabile con degree centrality, closenesscentrality e betweenness centrality. Ciò cheè emerso dai risultati sui dataset utilizzati è

4

quanto segue: la dispersion centrality fornisce lestesse informazioni della betweenness centrality.La differenza sostanziale è che il calcolo delladispersion centrality è parallelizzabile.

References

[1] Romantic Partnerships and the Disper-sion of Social Ties: A Network Analy-

sis of Relationship Status on Facebook -http://arxiv.org/pdf/1310.6753.pdf

[2] Snap http://snap.stanford.edu/

[3] Journal of Anthropological Research,Vol. 33, No. 4 (Winter, 1977), pp.452-473 http://www1.ind.ku.dk/complexLearning/zachary1977.pdf

5