Link prediction in social networks: combining topological and contextual data in a community detection based method
Pages 297 - 304
Abstract
Link Prediction (LP) is the task of predicting which nodes in a network will interact in the future. A common approach to LP is to compute degrees of compatibility between unconnected node pairs in the network. In such an approach, the predictive model uses some similarity metrics applied in the same way for all pairs of unconnected nodes, independent of the positions those nodes have in the network structure. More recent work has applied a different approach: they first detect communities in the network and then apply LP to each community. Nevertheless, these works have an important limitation: their community detection process only considers topological aspects of the network. They fail to consider, at the time of node grouping, characteristics related to the application context, such as participant's profiles, interests, and preferences, which may be fundamental both for the identification of more cohesive communities and for a greater assertiveness in predicting new connections. This paper proposes a method for LP that uses a community detection phase that combines topological and contextual data. This community detection phase takes into account characteristics of the network's nodes in order to separate them into groups whose internal content is cohesive. Tests with twelve scenarios of four networks popularly used in LP studies provided experimental evidence that the proposed method can overcome the state-of-the-art contextual data agnostic community detection based LP methods.
References
[1]
Y Ahn, J P Bagrow, and S Lehmann. 2010. Link communities reveal multiscale complexity in networks. nature 466, 7307 (2010), 761.
[2]
A. U. Bhat. 2012. Scalable community detection using label propagation & map-reduce. Scalable Community Detection using Label Propagation\& Map-Reduce (2012).
[3]
V D Blondel, J Guillaume, R Lambiotte, and E Lefebvre. 2008. Fast unfolding of communities in large networks. Journal of statistical mechanics: theory and experiment 2008, 10 (2008), P10008.
[4]
C. Cavalcante, A.and Muniz and R. Goldschmidt. 2018. Context-based Time Score: An Effective Similarity Function for Link Prediction in Social Networks. In Proc. of the 24th Brazilian Symposium on Multimedia and the Web. ACM, 339--346.
[5]
A Clauset, M EJ Newman, and C Moore. 2004. Finding community structure in very large networks. Physical review E 70, 6 (2004), 066111.
[6]
M.V. Dias. 2016. Uma abordagem para detecção de comunidades em redes complexas baseada em informações de domínio. Master's thesis. Instituto Militar de Engenharia, Brazil.
[7]
E. S. Florentino, A. A. B. Cavalcante, and R. Goldschmidt. 2019. Um Método Baseado na Evolução dos Dados Topológicos Para a Predição de Links em Redes Sociais. Simpósio Brasileiro de Sistema de Informação 15 (2019).
[8]
S. Fortunato. 2010. Community detection in graphs. Physics reports 486, 3 (2010), 75--174.
[9]
B. J Frey and D. Dueck. 2007. Clustering by passing messages between data points. science 315, 5814 (2007), 972--976.
[10]
M Friedman. 1937. The use of ranks to avoid the assumption of normality implicit in the analysis of variance. Journal of the american statistical association 32, 200 (1937), 675--701.
[11]
M Girvan and M EJ Newman. 2002. Community structure in social and biological networks. Proc. of the national academy of sciences 99, 12 (2002), 7821--7826.
[12]
R Goldschmidt, E Bezerra, and E Passos. 2015. Data Mining: Conceitos, técnicas, algoritmos, orientações e aplicações.
[13]
J. Heidemann, M. Klier, and F. Probst. 2012. Online social networks: A survey of a global phenomenon. Computer Networks 56, 18 (2012), 3866 -- 3878.
[14]
B Krishnamurthy and J Wang. 2000. On network-aware clustering of web clients. ACM SIGCOMM Computer Communication Review 30, 4 (2000), 97--110.
[15]
D Liben-Nowell and J Kleinberg. 2007. The link-prediction problem for social networks. journal of the Association for Information Science and Technology 58, 7 (2007), 1019--1031.
[16]
L Lü and T Zhou. 2011. Link prediction in complex networks: A survey. Physica A: statistical mechanics and its applications 390, 6 (2011), 1150--1170.
[17]
Z Lu, B Savas, W Tang, and I S Dhillon. 2010. Supervised link prediction using multiple sources. In Data Mining (ICDM), 2010. IEEE, Sydney, NSW, Australia, 923--928.
[18]
C Muniz, R Choren, and R Goldschmidt. 2017. Using a time based relationship weighting criterion to improve link prediction in social networks. In Proc. of the 19th International Conference on Enterprise Information Systems (1 ed.), Vol. 1. Porto, Portugal, 73--79.
[19]
C. P. Muniz, R. Goldschmidt, and R. Choren. 2018. Combining contextual, temporal and topological information for unsupervised link prediction in social networks. Knowledge-Based Systems 156 (2018), 129 -- 137.
[20]
A Pecli, M C Cavalcanti, and R Goldschmidt. 2018. Automatic feature selection for supervised learning in link prediction applications: a comparative study. Knowledge and Information Systems 56, 1 (2018), 85--121.
[21]
P Pons and M Latapy. 2005. Computing communities in large networks using random walks. In International symposium on computer and information sciences. Springer, Springer, Berlin, Heidelberg, 284--293.
[22]
F Radicchi, C Castellano, F Cecconi, V Loreto, and D Parisi. 2004. Defining and identifying communities in networks. Proc. of the National Academy of Sciences of USA 101, 9 (2004), 2658--2663.
[23]
U N Raghavan, R Albert, and S Kumara. 2007. Near linear time algorithm to detect community structures in large-scale networks. Physical review E 76, 3 (2007), 036106.
[24]
M Rosvall and CT Bergstrom. 2007. Maps of information flow reveal community structure in complex networks. arXiv preprint physics.soc-ph/0707.0609 (2007).
[25]
S J Russell and P Norvig. 2016. Artificial intelligence: a modern approach. Malaysia; Pearson Education Limited, Malaysia.
[26]
S Soundarajan and J Hopcroft. 2012. Using community information to improve the precision of link prediction methods. In Proc. of the 21st International Conference on World Wide Web. ACM, New York, NY, USA, 607--608.
[27]
V. Ströde, F. Campos, C. K. Pereira, G. Zimbrão, and J. M. Souza. 2016. Information Extraction to improve Link Prediction in scientific social networks. In 2016 IEEE 20th International Conference on Computer Supported Cooperative Work in Design (CSCWD). 515--520.
[28]
L. Tang and H. Liu. 2010. Community Detection and Mining in Social Media. Synthesis Lectures on Data Mining and Knowledge Discovery 2, 1 (2010), 1--137.
[29]
J. Valverde-Rebaza and A. de Andrade Lopes. 2012. Structural link prediction using community information on twitter. In Computational aspects of social networks (CASoN), 2012 Fourth International Conference on (1 ed.). IEEE, IEEE, Sao Carlos, Brazil, 132--137.
[30]
J. C. Valverde-Rebaza and A. de Andrade Lopes. 2012. Link prediction in complex networks based on cluster information. In Advances in Artificial Intelligence-SBIA 2012. Springer, Berlin, Heidelberg, 92--101.
[31]
J. Wang, Y. Ma, M. Liu, H. Yuan, W. Shen, and L. Li. 2017. A vertex similarity index using community information to improve link prediction accuracy. In Systems, Man, and Cybernetics (SMC), 2017 IEEE International Conference on. IEEE, IEEE, Banff, AB, Canada, 158--163.
[32]
P Wang, B Xu, Y Wu, and X Zhou. 2015. Link prediction in social networks: the state-of-the-art. Science China Information Sciences 58, 1 (2015), 1--38.
[33]
Z Wang, J Liang, and R Li. 2018. Exploiting user-to-user topic inclusion degree for link prediction in social-information networks. Expert Systems with Applications 108 (2018), 143 -- 158.
[34]
C. Zhang, H. Zhang, D. Yuan, and M. Zhang. 2016. Deep Learning Based Link Prediction with Social Pattern and External Attribute Knowledge in Bibliographic Networks. In 2016 IEEE International Conference on Internet of Things and IEEE Green Computing and Communications (GreenCom) and IEEE Cyber, Physical and Social Computing (CPSCom) and IEEE Smart Data (SmartData). 815--821.
[35]
B Zhao, P Sen, and L Getoor. 2006. Entity and relationship labeling in affiliation networks. In ICML Workshop on Statistical Network Analysis.
[36]
T. Zhou, L. Lü, and Y. Zhang. 2009. Predicting missing links via local information. The European Physical Journal B 71, 4 (2009), 623--630.
Index Terms
- Link prediction in social networks: combining topological and contextual data in a community detection based method
Recommendations
HM-EIICT: Fairness-aware link prediction in complex networks using community information
AbstractThe evolution of online social networks is highly dependent on the recommended links. Most of the existing works focus on predicting intra-community links efficiently. However, it is equally important to predict inter-community links with high ...
Prediction of link evolution using community detection in social network
AbstractNetwork evolution is one of the emerging research directions in the field of social network analysis, where link prediction plays a crucial role in modeling network dynamics in social networks. Link prediction has attracted a lot of attention of ...
A joint optimization framework for better community detection based on link prediction in social networks
AbstractReal-world network data can be incomplete (e.g., the social connections are partially observed) due to reasons such as graph sampling and privacy concerns. Consequently, communities detected based on such incomplete network information could be ...
Comments
Information & Contributors
Information
Published In
October 2019
537 pages
ISBN:9781450367639
DOI:10.1145/3323503
Copyright © 2019 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 29 October 2019
Check for updates
Author Tags
Qualifiers
- Research-article
Conference
WebMedia '19
WebMedia '19: Brazilian Symposium on Multimedia and the Web
October 29 - November 1, 2019
Rio de Janeiro, Brazil
Acceptance Rates
Overall Acceptance Rate 270 of 873 submissions, 31%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 101Total Downloads
- Downloads (Last 12 months)3
- Downloads (Last 6 weeks)1
Reflects downloads up to 25 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in