A supervised approach for intra-/inter-community interaction prediction in dynamic social networks
Rossetti G., Guidotti R., Miliou I., Pedreschi D., Giannotti F.
Link prediction Link Prediction Computer Science Applications H.2.8 DATABASE MANAGEMENT. Database Applications. Data Mining Community Detection Media Technology Information Systems Community discovery detection Human-Computer Interaction Communication
Due to the growing availability of Internet services in the last decade, the interactions between people became more and more easy to establish. For example, we can have an intercontinental job interview, or we can send real-time multimedia content to any friend of us just owning a smartphone. All this kind of human activities generates digital footprints, that describe a complex, rapidly evolving, network structures. In such dynamic scenario, one of the most challenging tasks involves the prediction of future interactions between couples of actors (i.e., users in online social networks, researchers in collaboration networks). In this paper, we approach such problem by leveraging networks dynamics: to this extent, we propose a supervised learning approach which exploits features computed by time-aware forecasts of topological measures calculated between node pairs. Moreover, since real social networks are generally composed by weakly connected modules, we instantiate the interaction prediction problem in two disjoint applicative scenarios: intracommunity and inter-community link prediction. Experimental results on real time-stamped networks show how our approach is able to reach high accuracy. Furthermore, we analyze the performances of our methodology when varying the typologies of features, community discovery algorithms and forecast methods.
Source: Social Network Analysis and Mining 6 (2016). doi:10.1007/s13278-016-0397-y
Publisher: Springer, Vienna
Bao Z, Zeng Y, Tay YC (2013) sonLP: social network link prediction by principal component regression. In: IEEE/ACM international conference advances in social networks analysis and mining (ASONAM). IEEE, pp 364-371
Baraba´si A-L, Albert R (1999) Emergence of scaling in random networks. Science 286(5439):509-512
Bliss CA, Frank MR, Danforth CM, Dodds PS (2013) An evolutionary algorithm approach to link prediction in dynamic social networks. arXiv:1304.6257
Blondel VD, Guillaume J-L, Lambiotte R, Lefebvre E (2008) Fast unfolding of communities in large networks. J Stat Mech Theory Exp 2008(10):P10008
Bringmann B, Berlingerio M, Bonchi F, Gionis A (2010) Learning and predicting the evolution of social networks. IEEE Intell Syst 25(4):26-35
Coscia M, Rossetti G, Giannotti F, Pedreschi D (2012) Demon: a local-first discovery method for overlapping communities. In: Proceedings of the 18th ACM SIGKDD international conference on knowledge discovery and data mining. ACM, pp 615-623
Csermely P (2004) Strong links are important, but weak links stabilize them. Trends Biochem Sci 29(7):331-334
da Silva Soares PR, Prudencio RBC (2012) Time series based link prediction. In: IEEE international joint conference on neural networks (IJCNN). doi:10.1109/IJCNN.2012.6252471
Dong Y, Tang J, Wu S, Tian J, Chawla NV, Rao J, Cao H (2012) Link prediction and recommendation across heterogeneous social networks. In: 2012 IEEE 12th international conference on data mining (ICDM). IEEE, pp 181-190
Feng X, Zhao J, Xu K (2012) Link prediction in complex networks: a clustering perspective. Eur Phys J B 85(1):1-9
Fire M, Puzis R, Elovici Y (2013) Link prediction in highly fractional data sets. In: Subrahmanian VS (ed) Handbook of computational approaches to counterterrorism. Springer, New York, pp 283-300
Gilbert E, Karahalios K (2009) Predicting tie strength with social media. In: Proceedings of the SIGCHI conference on human factors in computing systems. ACM, pp 211-220
Girvan M, Newman ME (2002) Community structure in social and biological networks. Proc Natl Acad Sci 99(12):7821-7826
Granovetter M (1973) The strength of weak ties. Am J Sociol 78(6):1
Hartmann T, Kappes A, Wagner D (2014) Clustering evolving networks. arXiv:1401.3516
Huang S, Chen M, Luo B, Lee D (2012) Predicting aggregate social activities using continuous-time stochastic process. In: Proceedings of the 21st ACM international conference on information and knowledge management. ACM, pp 982-991
Jahanbakhsh K, King V, Shoja GC (2012) Predicting human contacts in mobile social networks using supervised learning. In: SIMPLEX workshop, ACM
Liben-Nowell D, Kleinberg J (2007) The link prediction problem for social networks. J Am Soc Inform Sci Technol 58(7):1019-1031
Lichtenwalter RN, Lussier JT, Chawla NV (2010) New perspectives and methods in link prediction. In: Proceedings of the 16th ACM SIGKDD international conference on knowledge discovery and data mining. ACM, New York, pp 243-252. doi:10.1145/ 1835804.1835837
Lichtnwalter R, Chawla NV (2012) Link prediction: fair and effective evaluation. In: 2012 IEEE/ACM international conference on advances in social networks analysis and mining (ASONAM). IEEE, pp 376-383
Lu¨ L, Zhou T (2009) Role of weak ties in link prediction of complex networks. In: Proceedings of the 1st ACM international workshop on complex networks meet information & knowledge management. ACM, pp 55-58
Lu¨ L, Zhou T (2011) Link prediction in complex networks: a survey. Phys A Stat Mech Appl 390(6):1150-1170
Newman MEJ (2001) Clustering and preferential attachment in growing networks. Phys Rev E 64(2):025102
Onnela J-P, Sarama¨ki J, Hyvo¨nen J, Szabo´ G, Lazer D, Kaski K, Kerte´sz J, Baraba´si A-L (2007) Structure and tie strengths in mobile communication networks. Proc Natl Acad Sci 104(18):7332-7336
Page L, Brin S, Motwani R, Winograd T (1999) The pagerank citation ranking: bringing order to the web. Technical Report 1999-66, Stanford InfoLab, November 1999
Pujari M, Kanawati R (2012) Supervised rank aggregation approach for link prediction in complex networks. In: Proceedings of the 21st ACM international conference on World Wide Web, pp 1189-1196
Rapoport A (1963) Mathematical models of social interaction. In: Luce et al (eds) Handbook of mathematical psychology, vol 2. Wiley, New York
Rosvall M, Bergstrom CT (2011) Multilevel compression of random walks on networks reveals hierarchical organization in large integrated systems. PloS one 6(4):e18209
Salton G, McGill MJ (1983) Introduction to modern information retrieval. McGraw-Hill, New York
Sarkar P, Chakrabarti D, Jordan M (2012) Nonparametric link prediction in dynamic networks. arXiv:1206.6394
Shibata N, Yuya K, Ichiro S (2012) Link prediction in citation networks. J Am Soc Inform Sci Technol 63(1):78-85
Soundarajan S, Hopcroft J (2012) Using community information to improve the precision of link prediction methods. In: Proceedings of the 21st ACM international conference on World Wide Web, pp 607-608
Spiegel S, Clausen J, Albayrak S, Kunegis J (2011) Link prediction on evolving data using tensor factorization. In: Pacific-Asia conference on knowledge discovery and data mining. Springer, Berlin, Heidelberg, pp 100-110
Wang D, Pedreschi D, Song C, Giannotti F, Barabasi AL (2011) Human mobility, social ties, and link prediction. In: Proceedings of the 17th ACM SIGKDD international conference on knowledge discovery and data mining, pp 1100-1108
Watts DJ, Strogatz SH (1998) Collective dynamics of 'smallworld'networks. Nature 393(6684):440-442
Xiang R, Neville J, Rogati M (2010) Modeling relationship strength in online social networks. In: Proceedings of the 19th international conference on world wide web. ACM, pp 981-990
Xu Y, Rockmore D (2012) Feature selection for link prediction. In: CIKM workshop. ACM
Zhu J (2012) Max-margin nonparametric latent feature models for link prediction. arXiv:1206.4659
Metrics
Back to previous page
@article{oai:it.cnr:prodotti:366877,
title = {A supervised approach for intra-/inter-community interaction prediction in dynamic social networks},
author = {Rossetti G. and Guidotti R. and Miliou I. and Pedreschi D. and Giannotti F.},
publisher = {Springer, Vienna},
doi = {10.1007/s13278-016-0397-y},
journal = {Social Network Analysis and Mining},
volume = {6},
year = {2016}
}
0000-0003-3099-3835ISTI Repository
DOIAlso available from
