Abstract
Any real-world entity with entities and interactions between them can be modeled as a complex network. Complex networks are mathematically modeled as graphs with nodes denoting entities and edges(links) depicting the interaction between entities. Many analytical tasks can be performed on such networks. Link prediction (LP) is one of such tasks, that predicts missing/future links in a complex network modeled as graph. Link prediction has potential applications in the domains of biology, ecology, physics, computer science, and many more. Link prediction algorithms can be used to predict future scientific collaborations in a collaborative network, recommend friends/connections in a social network, future interactions in a molecular interaction network. The task of link prediction utilizes information pertaining to the graph such as node-neighborhoods, paths. The main focus of this work is to empirically evaluate the efficacy of a few neighborhood-based measures for link prediction. Complex networks are very huge in size and sparse in nature. Choosing the candidate node pairs for future link prediction is one of the hardest tasks. Majority of the existing methods consider all node pairs absent of an edge to be candidates; compute prediction score and then the node pairs with the highest prediction scores are output as future links. Due to the massive size and sparse nature of complex networks, examining all node pairs results in a large number of false positives. A few existing works select only a subset of node pairs to be candidates for prediction. In this study, a sample of candidates for LP based are chosen based on the hop distance between the nodes. Five similarity-based LP measures are chosen for experimentation. The experimentation on six benchmark datasets from four domains shows that a hop distance of maximum three is optimum for the prediction task.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Albert, R., Barabási, A.: Statistical mechanics of complex networks. Rev. Mod. Phys. 74(1), 47 (2002)
Yao, L., Wang, L., Pan, L., Yao, K.: Link prediction based on common-neighbors for dynamic social network. Procedia Comput. Sci. 83, 82–89 (2016)
Stumpf, M.P.H., Thorne, T., Silva, E.D., Stewart, R., An, H.J., Lappe, M., Wiuf, C.: Estimating the size of the human interactome. Proc. Nat. Acad. Sci. 105(19), 6959–6964 (2008)
Ben Schafer, J., Frankowski, D., Herlocker, J., Sen, S.: Collaborative filtering recommender systems. In: The Adaptive Web, pp. 291–324. Springer (2007)
Kumar, A., Singh, S.S., Singh, K., Biswas, B.: Link prediction techniques, applications, and performance: a survey. Physica A Stat. Mech. Appl. 553, 124289 (2020)
Jaya Lakshmi, T., Durga Bhavani, S.: Link prediction measures in various types of information networks: a review. In: 2018 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM), pp. 1160–1167. IEEE (2018)
Tong, H., Faloutsos, C., Pan, J.-Y.: Fast random walk with restart and its applications. In: Sixth International Conference on Data Mining (ICDM’06), pp. 613–622. IEEE (2006)
Wang, C., Satuluri, V., Parthasarathy, S.: Local probabilistic models for link prediction. In: Seventh IEEE International Conference on Data Mining (ICDM 2007), pp. 322–331. IEEE (2007)
Neville, J.: Statistical Models and Analysis Techniques for Learning in Relational Data. University of Massachusetts Amherst (2006)
Lü, L., Zhou, T.: Link prediction in complex networks: a survey. Physica A Stat. Mech. Appl. 390(6), 1150–1170 (2011)
Barabâsi, A.-L., Jeong, H., Néda, Z., Ravasz, E., Schubert, A., Vicsek, T.: Evolution of the social network of scientific collaborations. Physica A Stat. Mech. Appl. 311(3–4), 590–614 (2002)
Adamic, L., Adar, E.: Friends and neighbors on the web. Soc. Netw. 25(3) (2003)
Zhou, T., Lü, L., Zhang, Y.-C.: Predicting missing links via local information. Euro. Phys. J. B 71(4), 623–630 (2009)
Salton, G., McGill, M.J.: Introduction to Modern Information Retrieval. McGraw-Hill (1983)
McCune, B., Grace, J.B., Urban, D.L.: Analysis of Ecological Communities, vol. 28. MjM Software Design Gleneden Beach, OR (2002)
Cannistraci, C.V., Alanis-Lobato, G., Ravasi, T.: From link-prediction in brain connectomes and protein interactomes to the local-community-paradigm in complex networks. Sci. Rep. 3(1), 1–14 (2013)
Liu, Z., Zhang, Q.M., Lü, L., Zhou, T.: Link prediction in complex networks: a local Naïve Bayes model. EPL (Europhy. Lett.) 96(4), 48007 (2011)
Morales, A.J., Losada, J.C., Benito, R.M.: Users structure and behavior on an online social network during a political protest. Physica A Stat. Mech. Appl. 391(21), 5244–5253 (2012)
Lichtnwalter, R., Chawla, N.V.: Link prediction: fair and effective evaluation. In: 2012 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, pp. 376–383. IEEE (2012)
Leskovec, J., Kleinberg, J., Faloutsos, C.: Graph evolution: densification and shrinking diameters. ACM Trans. Knowl. Disc. Data (TKDD) 1(1), 2-es (2007)
Adamic, L.A., Glance, N.: The political blogosphere and the 2004 us election: divided they blog. In: Proceedings of the 3rd International Workshop on Link Discovery, pp. 36–43 (2005)
Duch, J., Arenas, A.: Community identification using extremal optimization. Phys. Rev. E 72, 027104 (2005)
Rossi, R., Ahmed, N.: The network data repository with interactive graph analytics and visualization. In: Twenty-Ninth AAAI Conference on Artificial Intelligence (2015)
Yang, Y., Lichtenwalter, R.N., Chawla, N.V.: Evaluating link prediction methods. Knowl. Inf. Syst. 45, 751–782 (2015)
Fawcett, T.: An introduction to roc analysis. Pattern Recogn. Lett. 27(8), 861–874 (2006)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd.
About this paper
Cite this paper
Nandini, Y.V., Lakshmi, T.J., Enduri, M.K. (2023). Link Prediction in Complex Networks: An Empirical Review. In: Bhateja, V., Carroll, F., Tavares, J.M.R.S., Sengar, S.S., Peer, P. (eds) Intelligent Data Engineering and Analytics. FICTA 2023. Smart Innovation, Systems and Technologies, vol 371. Springer, Singapore. https://doi.org/10.1007/978-981-99-6706-3_5
Download citation
DOI: https://doi.org/10.1007/978-981-99-6706-3_5
Published:
Publisher Name: Springer, Singapore
Print ISBN: 978-981-99-6705-6
Online ISBN: 978-981-99-6706-3
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)