Accurate Link Prediction Metric Based on Node Centrality and LSBC
Accurate Link Prediction Metric Based on Node Centrality and LSBC |
||
 |
 |
|
| © 2023 by IJETT Journal | ||
| Volume-71 Issue-5 |
||
| Year of Publication : 2023 | ||
| Author : Bara Samir, Jibouni Ayoub, Hammouch Ahmed |
||
| DOI : 10.14445/22315381/IJETT-V71I5P207 | ||
How to Cite?
Bara Samir, Jibouni Ayoub, Hammouch Ahmed, "Accurate Link Prediction Metric Based on Node Centrality and LSBC," International Journal of Engineering Trends and Technology, vol. 71, no. 5, pp. 70-83, 2023. Crossref, https://doi.org/10.14445/22315381/IJETT-V71I5P207
Abstract
During the last two decades, there has been a lot of interest in social network analysis. These networks are dynamic, with new links appearing and disappearing all the time. The challenge of suggesting future links from the current state of the network is recognized as link prediction. We calculate user similarity using information from nodes and edges. The more similar two users are, the more likely they will connect. In the domain of link prediction, similarity measures are quite essential. Many authors have suggested and analyzed numerous metrics, such as Jaccard, AA, and Katz, because of their simplicity and flexibility. In this work, we extend a new parameterized approach [21] to enhance the AUC value of link prediction metrics by combining them with eigenvector centrality. This work proposes to enhance local similarity metrics due to their interpretability and low complexity. Experiments reveal that the suggested technique outperforms the state-of-the-art metrics in terms of AUC, and it also outperforms the LSBC metric in terms of time. In addition to that, we have used machine learning algorithms to solve the link prediction problem as a classification task.
Keywords
Social network analysis, Link prediction, Similarity measures, Machine learning, Eigenvector centrality.
References
[1] A.L Barabási et al., “Evolution of the Social Network of Scientific Collaborations,” Physical: Statistical Mechanics and its Applications, vol. 311, no. 3-4, pp. 590-614, 2002.
[CrossRef] [Google Scholar] [Publisher Link]
[2] M. E. J. Newman, “Clustering and Preferential Attachment in Growing Networks,” Physical Review E, vol. 64, no. 2, p. 025102, 2001.
[CrossRef] [Google Scholar] [Publisher Link]
[3] P. Jaccard, “Comparative study of the Floral Distribution in a Portion of the Alps and the Jura,” Bulletins – Vaud Society of Natural Sciences, vol. 37, pp. 547-579, 1901.
[Google Scholar]
[4] Lada A Adamic, and Eytan Adar, “Friends and Neighbors on the Web,” Social Networks, vol. 25, no. 3, pp. 211-230, 2003.
[CrossRef] [Google Scholar] [Publisher Link]
[5] E. Ravasz et al., “Hierarchical Organization of Modularity in Metabolic Networks,” Science, vol. 297, no. 5586, pp. 1551-1555, 2002.
[CrossRef] [Google Scholar] [Publisher Link]
[6] E. A. Leicht, Petter Holme, and M. E. J. Newman, “Vertex Similarity in Networks,” Physical Review E, vol. 73, no. 2, p. 026120, 2006.
[CrossRef] [Google Scholar] [Publisher Link]
[7] G. Salton, and M. J. McGill, Introduction to Modern Information Retrieval, 1986.
[8] T. A. Sorensen, “A Method of Establishing Groups of Equal Amplitude in Plant Sociology Based on Similarity of Species Content and its Application to Analyses of the Vegetation on Danish Commons,” Biol. Skar., vol. 5, pp. 1-34, 1948.
[Google Scholar]
[9] Tao Zhou, Linyuan Lü, and Yi-Cheng Zhang, “Predicting Missing Links via Local Information,” The European Physical Journal B, vol. 71, no. 4, pp. 623-630, 2009.
[CrossRef] [Google Scholar] [Publisher Link]
[10] Ryan A. Rossi, and Nesreen K. Ahmed, “The Network Data Repository with Interactive Graph Analytics and Visualization,” Twenty-Ninth AAAI Conference on Artificial Intelligence, vol. 29, no. 1, 2015.
[CrossRef] [Google Scholar] [Publisher Link]
[11] Jerome Kunegis, “KONECT – The Koblenz Network Collection,” Proceedings of the 22nd International Conference on World Wide Web, pp. 1343–1350, 2013.
[CrossRef] [Google Scholar] [Publisher Link]
[12] M. Girvan and M. E. J. Newman, “Network of American Football Games Between Division IA Colleges during Regular Season Fall 2000,” Proceedings of National Acadamic Science, USA 99, pp. 7821-7826, 2002.
[Publisher Link]
[13] Vladimir Batagelj, and Andrej Mrvar, Spider Datasets, 2006. [Online]. Available: http://vlado.fmf.uni−lj.si/pub/networks/data/
[14] Duncan J. Watts, and Steven H. Strogatz, “Collective Dynamics of ‘Small-World’ Networks,” Nature, vol. 393, no. 1, pp. 440–442, 1998.
[CrossRef] [Google Scholar] [Publisher Link]
[15] Robert E. Ulanowicz, Cristina Bondavalli, and Michael S. Egnotovich, Network Analysis of Trophic Dynamics in South Florida Ecosystems–The Florida Bay Ecosystem, Annual Report to the U.S. Geological Survey, Biological Resources Division, 1997.
[16] Shiwei Sun et al., “Topological Structure Analysis of the Protein-Protein Interaction Network in Budding Yeast,” Nucleic Acids Research, vol. 31, no. 9, pp. 2443-2450, 2003.
[CrossRef] [Google Scholar] [Publisher Link]
[17] Software Package Protein Interaction Network
[18] Vito Latora, and Massimo Marchiori, “Efficient Behavior of Smallworld Networks,” Physical Review Letters, vol. 87, no. 19, p. 198701, 2001.
[CrossRef] [Google Scholar] [Publisher Link]
[19] Jari Saramäki et al., “Generalizations of the Clustering Coefficient to Weighted Complex Networks,” Physical Review E, vol. 75, no. 2, p. 027105, 2007.
[CrossRef] [Google Scholar] [Publisher Link]
[20] Marcus Kaiser, “Mean Clustering Coefficients: The Role of Isolated Nodes and Leafs on Clustering Measures for Small-World Networks,” New Journal of Physics, vol. 10, 2008.
[CrossRef] [Google Scholar] [Publisher Link]
[21] Jibouni Ayoub, Dounia Lotfi, and Ahmed Hammouch, “Link Prediction Using Betweenness Centrality and Graph Neural Networks,” Social Network Analysis and Mining, vol. 13, no. 1, 2023.
[CrossRef] [Google Scholar] [Publisher Link]
[22] Manuel Guerrero et al., “Adaptive Community Detection in Complex Networks Using Genetic Algorithms,” Neurocomputing, vol. 266, pp. 101-113, 2017.
[CrossRef] [Google Scholar] [Publisher Link]
[23] Duanbing Chen et al., “Identifying Influential Nodes in Complex Networks,” Physica A: Statistical Mechanics and its Applications, vol. 391, no. 4, pp. 1777-1787, 2012.
[CrossRef] [Google Scholar] [Publisher Link]
[24] Fragkiskos D. Malliaros, Maria-Evgenia G. Rossi, and Michalis Vazirgiannis, “Locating Influential Nodes in Complex Networks,” Scientific Reports, vol. 6, no. 1, pp. 1-10, 2016.
[CrossRef] [Google Scholar] [Publisher Link]
[25] Sang-Uk Jung et al., "Predicting Neologisms for Marketing:A Text Mining Approach," SSRG International Journal of Economics and Management Studies, vol. 7, no. 7, pp. 5-9, 2020.
[CrossRef] [Publisher Link]
[26] Fataneh Dabaghi Zarandi, and Marjan Kuchaki Rafsanjani, “Community Detection in Complex Networks Using Structural Similarities,” Physica A: Statistical Mechanics and its Applications, vol. 503, pp. 882-891, 2018.
[CrossRef] [Google Scholar] [Publisher Link]
[27] Ilham Esslimani, Armelle Brun, and Anne Boyer, “Densifying a Behavioral Recommender System by Social Networks Link Prediction Methods,” Social Network Analysis and Mining, vol. 1, no. 3, pp. 159–172, 2011.
[CrossRef] [Google Scholar] [Publisher Link]
[28] Zan Huang, Xin Li, and Hsinchun Chen, “Link Prediction Approach to Collaborative Filtering,” Proceedings of ACM/IEEE Joint Conference on Digital Libraries, pp. 141-142, 2005.
[CrossRef] [Google Scholar] [Publisher Link]
[29] Francesco Folino, and Clara Pizzuti, “Link Prediction Approaches for Disease Networks,” International Conference on Information Technology in Bio-and Medical Informatics, Springer, Berlin, Heidelberg, pp. 99-108, 2012.
[CrossRef] [Google Scholar] [Publisher Link]
[30] Víctor Martínez, Fernando Berzal, and Juan-Carlos Cubero, “A Survey of Link Prediction in Complex Networks,” Acm Computing Surveys, vol. 49, no. 4, pp. 1-33, 2016.
[CrossRef] [Google Scholar] [Publisher Link]
[31] Linyuan Lü, and Tao Zhou, “Link Prediction in Complex Networks: A Survey,” Physica A: Statistical Mechanics and its Applications, vol. 390, no. 6, pp. 1150-1170, 2011.
[CrossRef] [Google Scholar] [Publisher Link]
[32] Mohammad Al Hasan, and Mohammed J. Zaki, “A Survey of Link Prediction in Social Networks,” Social Network Data Analytics, Springer, Boston, MA, pp. 243-275, 2011.
[CrossRef] [Google Scholar] [Publisher Link]
[33] Mohammad Al Hasan et al., “Link Prediction Using Supervised Learning,” SDM06: Workshop On Link Analysis, Counterterrorism, and Security, vol. 30, pp. 798-805, 2006.
[Google Scholar] [Publisher Link]
[34] Tadej Matek, and Svit Timej Zebec, “Github Open-Source Project Recommendation System,” arXiv preprint arXiv:1602.02594, 2016.
[CrossRef] [Google Scholar] [Publisher Link]
[35] Iftikhar Ahmad et al., “Missing Link Prediction Using Common Neighbor asnd Centrality Based Parameterized Algorithm,” Scientific Reports, vol. 10, no. 1, pp. 1-9, 2020.
[CrossRef] [Google Scholar] [Publisher Link]
[36] Charles R. Harris et al., “Array Programming with NumPy,” Nature, vol. 585, pp. 357–362, 2020.
[CrossRef] [Google Scholar] [Publisher Link]