Analizziamo i protocolli di Social Score proposti nel Capitolo 3.8. Procediamo estraendo dal dataset 5 reti casuali composte da un numero di nodi prefissato. Le reti vengono classificate in base al loro numero di nodi, rispettivamente pari a 1000, 2500, 5000 e 8000 nodi. Sulle reti estratte `e stato eseguito l’algoritmo SSSC e RSC. La costante di decremento ST EP SIZE RAT IO definita dall’algoritmo SSSC ha un valore pari a 0.1 . Per le reti estratte sono stati calcolati il numero medio di archi (#Archi), il diametro medio delle reti (Diametro), il coefficiente di clustering medio (CC), i gradi medi dei nodi (Grado Medio) e la lunghezza media dei path minimi (AvaragePL). In Tabella 5.7 sono elencate tali misure medie per i vari campioni considerati. Le reti estratte presentano delle caratteristiche molto comuni alle OSN (descritte nel Capitolo 2).
Reti #Archi Diametro CC Grado Medio AvaragePL
1000 9230 4 0.41 10 3.2
2500 81911 5.5 0.35 10 3.91
5000 29212 5.5 0.33 10 4
8000 68621 6 0.26 10 3.98
Tabella 5.7: Caratteristiche medie delle reti estratte dal dataset.
Per l’algoritmo SSSC prendiamo in considerazione la misura di Social Score definita dall’Equazione 5.4.
SS = DynamicW EBC + N odeAvailability (5.4)
In Tabella 5.8 vengono mostrate, per ogni classe di rete considerata, il SS minimo medio (SS min), il SS massimo medio (SS max) e SS medio delle reti contenute in ogni classe.
Nel grafico in Figura 5.19 viene mostrata la percentuale di nodi selezionati come Social Cache nella prima fase dell’algoritmo SSSC e nella prima iterazione dell’algoritmo Random Social Score (RSC). Per le varie classi di reti considerate nell’esperimento la percentuale di nodi che vengono selezionati come social cache dall’algoritmo SSSC risulta essere molto bassa. In particolare, solo l’8% dei nodi vengono selezionati come social cache per reti composte da 1000 nodi; mentre per le reti composte da 8000 nodi, solo il 16 % di questi viene selezionato come social
Reti SS medio SS max SS min SS social cache (SSSC)
1000 1.3 2.61 0.24 2.42
2500 1.38 2.66 0.08 2.03
5000 1.82 6.32 0.26 3.57
8000 2 7 0.23 3.3
Tabella 5.8: Social Score delle classi di rete estratte dal dataset.
cache. Per l’algoritmo RSC la percentuale di nodi eletti social cache nella prima iterazione risulta essere molto pi`u alta rispetto a SSSC. Infatti, durante la prima fase dell’algoritmo SSSC, ogni nodo seleziona come social cache il nodo della pro- pria ego network che possiede il punteggio di Social Score pi`u alto. Di conseguenza, i nodi che hanno un punteggio di social score alto hanno pi`u probabilit`a di essere selezionati come social cache dai loro nodi vicini.
Figura 5.19: Percentuale di nodi selezionati come social cache per le classi di reti esaminate.
In Tabella 5.8 vengono mostrati il punteggio medio di social score dei nodi social cache selezionati nella prima fase dell’algoritmo SSSC (SS social cache SSSC). Il social score medio dei nodi selezionati come social cache risulta superiore alla media.
Per valutare al meglio le caratteristiche degli algoritmi `e necessario capire come i social cache selezionati nella prima fase degli algoritmi si comportano dal punto di vista del problema della copertura della rete, eseguita nelle successive fasi degli algoritmi SSSC e RSC. Il grafico in Figura 5.20 mostra la percentuale di archi coperti dai social cache, dopo la prima fase dell’algoritmo SSSC e dopo la prima iterazione dell’algoritmo RSC. Dal grafico `e possibile notare come i social cache selezionati nella prima fase dell’algoritmo SSSC coprono almeno l’80% degli archi delle reti esaminate.
Figura 5.20: Percentuale di archi coperti dai social cache per le classi di reti esaminate.
La seconda fase dell’algoritmo SSSC si occupa di coprire, in modo iterativo, i rimanenti archi della rete. La fase termina in un numero finito di passi determinato dal valore della costante di decremento ST EP SIZE RAT IO (pari a 0.1).
In [39] viene proposto un algoritmo, simile a SSSC, per affrontare il problema della diffusione delle informazioni sociali in (descritto in Paragrafo 2.3.1). La misura di social score calcolata da ogni nodo prende in considerazione la sua EBC, il grado e il coefficiente di clustering. Nella prima fase dell’algoritmo ogni nodo calcola il proprio punteggio di social score e diventa social cache se il suo punteggio supera una certa soglia. Il numero di social cache da selezionare nella prima fase pu`o essere fissato attraverso la variabile soglia.
La seconda fase dell’algoritmo SocialCDN `e uguale a quella dell’algoritmo SSSC. Il numero di social cache selezionati dai due algoritmi `e uguale, tuttavia la misura
di social score utilizzata in SocialCDN non prende in considerazioni propriet`a temporali dei nodi. Tuttavia, come hanno dimostrato gli esperimenti nei Paragrafi 5.4 e 5.5, non considerare la dinamicit`a dei nodi pu`o causare la degradazione delle prestazioni del sistema.
Capitolo 6
Conclusioni e lavori futuri
Nel lavoro di tesi sono state analizzate le problematiche relative alla gestione di informazioni sociali; problematiche che emergono dalla distribuzione e decentraliz- zazione del servizio di OSN attraverso un approccio P2P. A supporto del problema `e stata definita una overlay network innovativa, social overlay Dunbar-based, ba- sata sul concetto di ego network. Una ego network `e una rete composta da un utente e da tutti gli altri individui che hanno una relazione stabile con esso. Gli studi condotti sulle ego network sia in campo antropologico da Dunbar [31, 49] sia in ambienti virtuali [18, 43], hanno permesso la definizione di una social overlay dove ogni peer `e collegato ad un insieme di nodi limitato dal numero di Dunbar (150) ed i collegamenti che instaura un peer sono solo verso peer con i quali esso mantiene una relazione stabile. La social overlay definita gode di un certo livello di fiducia, in quanto, ogni individuo `e collegato solo agli utenti con cui ha una relazione stabile e quindi di cui si fida maggiormente.
La disponibilit`a dei dati viene garantita attraverso l’utilizzo della tecnica del Di- stributed Social Caching, dove ogni peer ha a disposizione nodi vicini da utilizzare come server locali (social cache) per la memorizzazione delle proprie informazioni sociali. I nodi che agiscono da social cache rendono disponibili i dati di un utente anche quando esso abbandona il sistema.
`
E stato proposto un algoritmo distribuito di selezione dei social cache, che considera il comportamento temporale del nodo e le sue caratteristiche strutturali locali (Social Score) per decidere quali vicini sono pi`u adatti a ricoprire il ruolo di social cache. L’algoritmo ha dimostrato avere buone capacit`a di selezione dei social cache e buone caratteristiche di copertura della social overlay. Inoltre il modello di Social Score utilizzato per la selezione dei social cache pu`o essere esteso
in modo da considerare altre propriet`a interessanti dei nodi (come ad esempio la Degree Centrality [42]).
La Ego Betweenness Centrality (ego-bc) `e stata studiata e utilizzata come misura dell’importanza topologica di un nodo. Il metodo proposto per il calcolo della ego-bc presenta una complessit`a computazionale molto bassa e una correlazione positiva molto forte rispetto ai metodi comunemente adottati per il calcolo della centralit`a di un nodo. Inoltre il metodo per il calcolo della ego-bc pu`o essere utilizzato a supporto di altri problemi che si presentano nell’ambito delle DOSN come: update diffusion, top-k, searching, etc.
Il metodo di selezione proposto considera i social cache persistenti e sempre disponibili nel tempo. Tuttavia, sia il dinamismo infrastruttura sia il dinami- smo relazionale dei nodi provoca un cambiamento della sottostante social overlay Dunbar-based e, di conseguenza, una rielezione dei social cache. Si potrebbero introdurre dei meccanismi che cercano di mantenere l’insieme dei social cache una copertura minima della social overlay. Ad esempio, nel caso in cui un nodo instau- ra delle connessioni con altri nodi possiamo distinguere i seguenti casi: (i) un nodo cache (social cache) si collega ad un nodo non cache (non social cache), (ii) un nodo cache si collega ad un nodo cache oppure (iii) un nodo non cache si collega ad un nodo non cache. I casi (i) e (ii) non necessitano di una rielezione dei social cache, anche se la nuova copertura della rete potrebbe non essere pi`u minima. Nel caso (iii), i due nodi non cache devono verificare la copertura dell’arco nella propria ego network e, se necessario, eseguire una rielezione dei social cache.
In modo simile, nel caso in cui un nodo rimuove una connessioni con un altro nodo possiamo distinguere i seguenti casi: (i) un nodo cache si disconnette da un nodo non cache, (ii) un nodo cache si disconnette da un nodo cache oppure (iii) un nodo non cache si disconnette ad un nodo non cache. I casi (ii) e (iii) non necessitano di una rielezione dei social cache. Nel caso (i) bisogna eseguire una verifica della copertura e se necessario una rielezione di social cache.
La rapida diffusione delle tecnologie Mobile come smartphone ha accentuato ancora di pi`u le caratteristiche di dinamicit`a del sistema. Il formalismo, recente- mente introdotto, dei time-varing graph pu`o essere utilizzato per avere una visione temporale di quello che sono le caratteristiche della rete e di come essa evolve nel tempo. Questo ci pu`o dare molte informazioni su come potrebbero evolvere i pro- cessi che operano su tali sistemi.
dotte nel sistema per garantire una maggiore disponibilit`a dei dati e una maggiore robustezza del sistema.
Appendice A
User Churn Model
Una delle caratteristiche principali delle DOSN `e la loro dinamicit`a. L’assenza o la presenza di determinati link all’interno della DOSN dipende principalmente dallo stato in cui un utente si trova (online o offline). Gli utenti di una OSN sono caratterizzati da una disponibilit`a di tipo eterogenea, in quanto ogni utente ha una propria probabilit`a di essere online o offline in un determinato istante di tempo, che `e diversa da quella di un altro utente. Tale fenomeno pu`o essere modellato come un processo stocastico. Con il termine di user churn viene indicato il processo di arrivo/abbandono dei nodi all’interno di un sistema. Il churn `e caratterizzato da: lifetimes distribution Che determina la quantit`a di tempo in cui l’utente `e
presente nel sistema
offline distribution Che determinala la quantit`a di tempo in cui l’utente non `e presente nel sistema
Questi due elementi definiscono ci`o che viene chiamata disponibilit`a di un nodo. Utilizziamo il modello definito in [58] per caratterizzare la disponibilit`a dei nodi. Il modello `e ottenuto considerando caratteristiche comportamento degli utenti in sistemi P2P reali.
Consideriamo un sistema P2P con n utenti, dove ogni utente i in un determina- to istante di tempo t pu`o essere online o offline. Questo comportamento pu`o essere modellato attraverso un processo di renewal Zi(t) definito in Equazione (A.1).
Zi(t) =
1 i `e online al tempo t
Il tale processo, i periodi in cui il nodo i si trova online e offline sono ricavati da variabili casuali Xi
one Xof fi ognuna delle quali ha associato una distribuzione Foni e
Fi
of f. Le distribuzioni esponenziali (definite dall’Equazione (A.2)) e le distribuzioni
di Pareto (definite dall’Equazione (A.3)) sono quelle pi`u utilizzare per descrivere la durata dei periodi di online (Fi
on) e di offline (Fof fi ) per ogni utente i. Le variabili
λ, α e β rappresentano i parametri delle distribuzioni.
Fi(x) = 1− e−λix (A.2)
pareto[α, β] = Fi(x) = 1− (1 + x/βi)−αi, x > 0, αi > 1 (A.3)
Indichiamo con li = E(Xoni ) e con di = E(Xof fi ) la durata media dei periodi
di online e offline del nodo i. L’eterogeneit`a tra le disponibilit`a degli utenti viene introdotta generando casualmente i valori li e di per ogni utente i, attraverso
l’utilizzo di due distribuzioni di Pareto con α = 3 e β = 1 per li, e α = 3 e
β = 2 per di. Queste distribuzioni ci permettono di avere un tempo medio di
online e offline pari rispettivamente a E(li) = 0.5 ore e E(di) = 1 ora. Tali valori
coincidono con quelli riscontrati in molti studi sperimentali [58].
Dopo aver selezionato una coppia (li, di) per ogni utente i, i tempi di online e
offline attuali vengono ottenuti dalle distribuzioni Fi
on e Fof fi , definite in modo che
la propria media sia uguale ai corrispondenti valori li e di. Le distribuzioni che `e
possibile utilizzare in questa fase sono elencate di seguito: • Fi on ∼ pareto[3, 2li], Fof fi ∼ pareto[3, 2di] • Fi on ∼ pareto[1.5, li/2], Fof fi ∼ pareto[1.5, di/2] • Fi on ∼ exp[1/li], Fof fi ∼ pareto[3, 2di]
Bibliografia
[1] Diaspora. https://joindiaspora.com/.
[2] A. Datta, S. Buchegger, L. Vu, T. Strufe and K. Rzadca. Decentralized online social networks. In Handbook of Social Network Technologies, pages 349–378, 2009.
[3] Albert, R., Jeong, H., and Barabasi, A.-L. Attack and error tolerance of complex networks. Nature 406, 378-382, 2000.
[4] Alberto Montresor and M´ark Jelasity. PeerSim: A Scalable P2P Simulator. In Proc. of the 9th Int. Conference on Peer-to-Peer (P2P’09), pages 99–100, 2009.
[5] Amre Shakimov and Harold Lim and Ram´on C´aceres and On P. Cox and Kevin Li and Dongtao Liu and Er Varshavsky. Vis-`a-vis: Privacy-preserving online social networking via virtual individual servers. In In COMSNETS, 2011.
[6] Arnaboldi, Valerio and Guazzini, Andrea and Passarella, Andrea. Egocen- tric Online Social Networks: Analysis of Key Features and Prediction of Tie Strength in Facebook. Computer Communications, 2013.
[7] Baden, Randy and Bender, Adam and Spring, Neil and Bhattacharjee, Bob- by and Starin, Daniel. Persona: an online social network with user-defined privacy. In Proceedings of the ACM SIGCOMM 2009 conference on Data communication, SIGCOMM ’09, pages 135–146, New York, NY, USA, 2009. ACM.
[8] Barabasi A.-L. and Albert R. The Emergence of Scaling in Random Networks. Science, 286:797-817, 1999.
[9] Bonchi, Francesco and Castillo, Carlos and Gionis, Aristides and Jaimes, Alejandro. Social Network Analysis and Mining for Business Applications. ACM Trans. Intell. Syst. Technol., 2(3):22:1–22:37, May 2011.
[10] boyd, d. m., & Ellison, N. B. Social network sites: Definition, history, and scholarship. Journal of Computer-Mediated Communication, 2007.
[11] Broder, A., Kumar, R., Maghoul, F., Raghavan, P., Rajagopalan, S., Stata, R., Tomkins, A., and Wiener, J. Graph structure in the web. Computer Networks 33, 309–320, 2000.
[12] Buchegger, Sonja; Schioberg, Doris; Vu, Le-Hung; Datta, Anwitaman. Imple- menting a P2P Social Network - Early Experiences and Insights from PeerSoN. In Second ACM Workshop on Social Network Systems, 2009.
[13] Chan, Shu Yan and Leung, Ian X.Y. and Li`o, Pietro. Fast centrality ap- proximation in modular networks. In Proceedings of the 1st ACM interna- tional workshop on Complex networks meet information & knowledge management, 2009.
[14] Ching-man Au Yeung and Ilaria Liccardi and Kanghao Lu and Oshani Se- neviratne and Tim Berners-lee. Decentralization: The future of online social networking. In W3C Workshop on the Future of Social Networking Position Papers, 2009.
[15] Cutillo, Leucio Antonio and Molva, Refik and Strufe, Thorsten. Safebook : a privacy preserving online social network leveraging on real-life trust. IEEE Communications Magazine, 47, 12 2009.
[16] Daly, Elizabeth M. and Haahr, Mads. Social network analysis for routing in disconnected delay-tolerant MANETs. In Proceedings of the 8th ACM international symposium on Mobile ad hoc networking and computing, 2007. [17] Daniel Whitney. Basic Network Metrics.
[18] Duncan J. Watts & Steven H. Strogatz. Collective dynamics of ’small-world’ networks. Nature, 393:440–442, 1998.
[19] Erd¨os, P. and R´enyi, A. On random graphs, I. Publicationes Mathematicae (Debrecen), 1959.
[20] Everett, M.G., and Borgatti, S.P. Ego-Network Betweenness. In Social Networks, 2005.
[21] Foster, Jacob G. and Foster, David V. and Grassberger, Peter and Paczuski, Maya. Edge Direction and the Structure of Networks. Proceedings of the National Academy of Sciences of the United States of America, 2009.
[22] Freeman, Linton C. A Set of Measures of Centrality Based on Betweenness. Sociometry, 1977.
[23] Garriss, Scott and Kaminsky, Michael and Freedman, Michael J. and Karp, Brad and Mazieres, David and Yu, Haifeng. RE: reliable email. In Pro- ceedings of the 3rd conference on Networked Systems Design & Implementa- tion - Volume 3, NSDI’06, pages 22–22, Berkeley, CA, USA, 2006. USENIX Association.
[24] Gert Sabidussi. The centrality index of a graph. Psychometrika, 31(4):581– 603, 1966.
[25] Giuliano Mega and Alberto Montresor and Gian Pietro Picco. On churn and communication delays in social overlays. In P2P’12, 2012.
[26] Gkorou, Dimitra and Pouwelse, Johan and Epema, Dick. Betweenness Cen- trality Approximations for an Internet Deployed P2P Reputation System. In Proceedings of the 2011 IEEE International Symposium on Parallel and Distributed Processing Workshops and PhD Forum, pages 1627–1634, 2011. [27] Graffi, K. ; Gross, C. ; Stingl, D. ; Hartung, D. ; Kovacevic, A. ; Steinmetz, R.
LifeSocial.KOM: A secure and P2P-based solution for online social networks. In Consumer Communications and Networking Conference (CCNC), pages 554 – 558 , 2012.
[28] Gummadi, Krishna P. and Mislove, Alan and Druschel, Peter. Exploiting Social Networks for Internet Search . In Proc. 5th Workshop on Hot Topics in Networks, pages 79–84, 2006.
[29] Harary, Frank ; Hage, Per. Eccentricity and centrality in networks. Social Networks, 1995.
[30] Hari Balakrishnan and M. Frans Kaashoek and David Karger and Robert Morris and Ion Stoica. Looking up Data in P2P Systems.
[31] Hill, R. A. and Dunbar, R. I. M. Social network size in humans. Human Nature, 14(1):53–72.
[32] Jac. M. Anthonisse. The rush in a directed graph. SMC, 1971.
[33] Jacob G. Foster, Favid V. Foster, Peter Grassberger and Maya Paczuski. Edge direction and the structure of network. Proceedings of the National Academy of Sciences of the United States of America, 2010.
[34] K. Wehmuth and A. Ziviani. Distributed Assessment of Network Centralities in Complex Social Networks. 2012 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, pages 1046–1049, 2012.
[35] Katharina A. Lehmann and Michael Kaufmann. Decentralized algori-
thms for evaluating centrality in complex networks. Technical report, Universit¨atsbibliothek T¨ubingen, 2003.
[36] Kossinets, Gueorgi and Kleinberg, Jon and Watts, Duncan. The structure of information pathways in a social communication network. In Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 435–443, 2008.
[37] Liu, Dongtao and Shakimov, Amre and Caceres, Ramon and Varshavsky, Alexander and Cox, Landon P. Confidant: protecting OSN data without locking it up. In Proceedings of the 12th ACM/IFIP/USENIX international conference on Middleware, Middleware’11, pages 61–80, Berlin, Heidelberg, 2011. Springer-Verlag.
[38] Lu Han ; Nath, B. ; Iftode, L. ; Muthukrishnan, S. Social Butterfly: Social Caches for Distributed Social Networks. In Privacy, security, risk and tru- st (passat), 2011 ieee third international conference on and 2011 ieee third international conference on social computing (socialcom), pages 81–86, 2011. [39] Lu Han ; Punceva, M. ; Nath, B. ; Muthukrishnan, S. ; Iftode, L. So- cialCDN: Caching techniques for distributed social networks. In IEEE 12th International Conference on Peer-to-Peer Computing (P2P), pages 191–202, 2012.
[40] M. E. J. Newman. The Structure and Function of Complex Networks. SIAM Review 45, 167-256, 2003.
[41] M´ark Jelasity. Natural Computing Series, pages 139—162. Springer, 2011. [42] Marsden, P. Egocentric and sociocentric measures of network centrality. Social
Networks, 24(4):407–422, 2002.
[43] Massimiliano La Gala, Valerio Arnaboldi, Andrea Passarella, Marco Con- ti. Ego-net Digger: a New Way to Study Ego Networks in Online Social Networks. Technical report, IIT-CNR, 2012.
[44] Mega, Giuliano and Montresor, Alberto and Picco, Gian Pietro. Efficient dissemination in decentralized social networks. In Peer-to-Peer Computing, pages 338–347, 2011.
[45] Newman M. Assortative Mixing in Networks. Physical Review Letters, 2002. [46] Newman MEJ. Mixing patterns in networks. Phys Rev E 67:026126, 2003. [47] Nicolas Kourtellis and Adriana Iamnitchi. Inferring peer centrality in socially-
informed peer-to-peer systems. In Peer-to-Peer Computing’11, pages 318–327, 2011.
[48] Nilizadeh, Shirin and Jahid, Sonia and Mittal, Prateek and Borisov, Nikita and Kapadia, Apu. Cachet: a decentralized architecture for privacy preser- ving social networking with caching. In Proceedings of the 8th international conference on Emerging networking experiments and technologies, CoNEXT ’12, pages 337–348, New York, NY, USA, 2012. ACM.
[49] R. I. M. Dunbar. The Social Brain Hypothesis. Evolutionary Anthropology, 1998.
[50] Robert Geisberger and Peter Sanders and Dominik Schultes. Better
Approximation of Betweenness Centrality .
[51] Seong, Seok-Won and Seo, Jiwon and Nasielski, Matthew and Sengupta, De- bangsu and Hangal, Sudheendra and Teh, Seng Keat and Chu, Ruven and Dodson, Ben and Lam, Monica S. PrPl: a decentralized social networking infrastructure. In Proceedings of the 1st ACM Workshop on Mobile Cloud
Computing & Services: Social Networks and Beyond, MCS ’10, pages 8:1–8:8, New York, NY, USA, 2010. ACM.
[52] Shimbel, Alfonso . Structural parameters of communication networks. Bulletin of Mathematical Biology, 15:501–507, 1953.
[53] Travers, Jeffrey & Stanley Milgram. An Experimental Study of the Small World Problem. Sociometry, 1969.
[54] Valerio Arnaboldi, Marco Conti, Andrea Passarella and Fabio Pezzoni. Ana- lysis of Ego Network Structure in Online Social Networks. Technical report, IIT-CNR, 2012.
[55] Maarten van Steen. Graph Theory and Complex Networks: An Introduction. Maarten van Steen, 2010.
[56] Watts D. and Strongatz S. Collective Dynamics of Small World Networks. Nature, 393: 440-442, 1998.
[57] Xiao Fan Wang and Guanrong Chen. Complex Networks: Small-World, Scale- Free and Beyond. IEEE CIRCUITS AND SYSTEMS MAGAZINE, 2003. [58] Yao, Zhongmei and Leonard, Derek and Wang, Xiaoming and Loguinov, Dmi-
tri. Modeling Heterogeneous User Churn and Local Resilience of Unstruc- tured P2P Networks. In Proceedings of the Proceedings of the 2006 IEEE International Conference on Network Protocols, pages 32–41, 2006.