A Centrality Maximization Approach for Link Recommendation
DOI:
https://doi.org/10.24203/3712t522Keywords:
link recommendation, node centrality, submodular function maximization, social networksAbstract
In social networks, the goal of link recommendation is to recommend links for nodes and add them to the network, thereby satisfying the potential link interests of the nodes. The centrality of nodes in social networks typically quantifies the importance of nodes in the network. Some nodes may desire to increase their centrality by adding links. First, a multi-community centrality measurement method is proposed, and based on harmonic centrality, a hybrid centrality measurement method is introduced. Next, the link recommendation problem is regarded as a problem of maximizing node hybrid centrality, which can be formally modeled as a submodular function maximization problem. A greedy algorithm with performance guarantees can be directly applied to select the best links. Compared to existing link prediction and link recommendation algorithms, our algorithm recommends links that better improve the hybrid centrality of users.
References
[1] Mishra S, Singh S S, Kumar A, et al. HOPLP− MUL: link prediction in multiplex networks based on higher order paths and layer fusion[J]. Applied Intelligence, 2023, 53(3): 3415-3443.
[2] Zhou M, Jin H, Wu Q, et al. Betweenness centrality-based community adaptive network representation for link prediction[J]. Applied Intelligence, 2022, 52(4): 3545-3558.
[3] Le T, Le N, Le B. Knowledge graph embedding by relational rotation and complex convolution for link prediction[J]. Expert Systems with Applications, 2023, 214: 119122.
[4] Zhang J, Huang J, Gao J, et al. Knowledge graph embedding by logical-default attention graph convolution neural network for link prediction[J]. Information Sciences, 2022, 593: 201-215.
[5] Zhao A, Yu Y. Context aware sentiment link prediction in heterogeneous social network[J]. Cognitive Computation, 2022, 14(1): 300-309.
[6] Liu Q, Chen Y, Zhang G, et al. A novel functional network based on three-way decision for link prediction in signed social networks[J]. Cognitive Computation, 2022, 14(6): 1942-1954.
[7] Boldi P, Vigna S. Axioms for centrality[J]. Internet Mathematics, 2014, 10(3-4): 222-262.
[8] Papagelis M, Bonchi F, Gionis A. Suggesting ghost edges for a smaller world[C]//Proceedings of the 20th ACM international conference on Information and knowledge management. 2011: 2305-2308.
[9] Parotsidis N, Pitoura E, Tsaparas P. Selecting shortcuts for a smaller world[C]//Proceedings of the 2015 SIAM International Conference on Data Mining. Society for Industrial and Applied Mathematics, 2015: 28-36.
[10] Crescenzi P, d’Angelo G, Severini L, et al. Greedily improving our own centrality in a network[C]//International symposium on experimental algorithms. Cham: Springer International Publishing, 2015: 43-55.
[11] Ishakian V, Erdös D, Terzi E, et al. A framework for the evaluation and management of network centrality[C]//Proceedings of the 2012 SIAM International Conference on Data Mining. Society for Industrial and Applied Mathematics, 2012: 427-438.
[12] Chen W, Zhong H, Wu L, et al. A general greedy approximation algorithm for finding minimum positive influence dominating sets in social networks[J]. Journal of Combinatorial Optimization, 2022, 44(1): 1-20.
[13] Lin H, Bilmes J. A class of submodular functions for document summarization[C]//Proceedings of the 49th annual meeting of the association for computational linguistics: human language technologies. 2011: 510-520.
[14] Yang W, Zhang Y, Du D Z. Influence maximization problem: properties and algorithms[J]. Journal of Combinatorial Optimization, 2020, 40(4): 907-928.
[15] Chakrabarty D, Goel G. On the approximability of budgeted allocations and improved lower bounds for submodular welfare maximization and GAP[J]. SIAM Journal on Computing, 2010, 39(6): 2189-2211.
[16] Parotsidis N, Pitoura E, Tsaparas P. Centrality-aware link recommendations[C]//Proceedings of the ninth ACM international conference on web search and data mining. 2016: 503-512.
[17] Wolsey L A. An analysis of the greedy algorithm for the submodular set covering problem[J]. Combinatorica, 1982, 2(4): 385-393.
[18] Mirzasoleiman B, Badanidiyuru A, Karbasi A, et al. Lazier than lazy greedy[C]//Proceedings of the AAAI Conference on Artificial Intelligence. 2015: 1812–1818.
[19] Palla G, Derényi I, Farkas I, et al. Uncovering the overlapping community structure of complex networks in nature and society[J]. nature, 2005, 435(7043): 814-818.
[20] Reichardt J, Bornholdt S. Statistical mechanics of community detection[J]. Physical Review E—Statistical, Nonlinear, and Soft Matter Physics, 2006, 74(1): 016110.
[21] Cordasco G, Gargano L. Community detection via semi-synchronous label propagation algorithms[C]//2010 IEEE international workshop on: business applications of social network analysis (BASNA). IEEE, 2010: 1-8.
[22] Traag V A, Waltman L, Van Eck N J. From Louvain to Leiden: guaranteeing well-connected communities[J]. Scientific reports, 2019, 9(1): 1-12.
[23] Newman M E J. Finding community structure in networks using the eigenvectors of matrices[J]. Physical Review E—Statistical, Nonlinear, and Soft Matter Physics, 2006, 74(3): 036104.
[24] Lusseau D, Schneider K, Boisseau O J, et al. The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations: can geographic isolation explain this unique trait?[J]. Behavioral Ecology and Sociobiology, 2003, 54: 396-405.
[25] Girvan M, Newman M E J. Community structure in social and biological networks[J]. Proceedings of the national academy of sciences, 2002, 99(12): 7821-7826.
[26] Zachary W W. An information flow model for conflict and fission in small groups[J]. Journal of anthropological research, 1977, 33(4): 452-473.
[27] Liu B, Xu S, Li T, et al. Quantifying the effects of topology and weight for link prediction in weighted complex networks[J]. Entropy, 2018, 20(5): 363.
[28] Ye Q, Zhu C, Li G, et al. Using node identifiers and community prior for graph-based classification[J]. Data Science and Engineering, 2018, 3(1): 68-83.
[29] Watts D J, Strogatz S H. Collective dynamics of ‘small-world’networks[J]. nature, 1998, 393(6684): 440-442.
[30] Xu Q, Qiu L, Lin R, et al. An improved community detection algorithm via fusing topology and attribute information[C]//2021 IEEE 24th International Conference on Computer Supported Cooperative Work in Design (CSCWD). IEEE, 2021: 1069-1074.
[31] Zhou T, Lü L, Zhang Y C. Predicting missing links via local information[J]. The European Physical Journal B, 2009, 71: 623-630.
[32] Liben-Nowell D, Kleinberg J. The link prediction problem for social networks[C]//Proceedings of the twelfth international conference on Information and knowledge management. 2003: 556-559.
[33] Soundarajan S, Hopcroft J. Using community information to improve the precision of link prediction methods[C]//Proceedings of the 21st international conference on world wide web. 2012: 607-608.
[34] Valverde-Rebaza J C, de Andrade Lopes A. Link prediction in complex networks based on cluster information[C]//Advances in Artificial Intelligence-SBIA 2012: 21th Brazilian Symposium on Artificial Intelligence, Curitiba, Brazil, October 20-25, 2012. Proceedings. Springer Berlin Heidelberg, 2012: 92-101.
[35] Ahmad I, Akhtar M U, Noor S, et al. Missing link prediction using common neighbor and centrality based parameterized algorithm[J]. Scientific reports, 2020, 10(1): 364.
Downloads
Published
Issue
Section
License
Copyright (c) 2025 Qi Zhang, Hao Zhong
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
The articles published in International Journal of Computer and Information Technology (IJCIT) is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
