NANDINI, YV, TANGIRALA, Jaya Lakshmi and ENDURI, Murali Krishna (2023). Link Prediction in Complex Networks: An Empirical Review. In: BHAJETA, Vikrant, CARROLL, Fiona, TAVARES, João Manuel R. S., SENGHAR, Sandeep Singh and PEER, Peter, (eds.) Intelligent Data Engineering and Analytics. Proceedings of the 11th International Conference on Frontiers of Intelligent Computing: Theory and Applications (FICTA 2023). Smart Innovation, Systems and Technologies (371). Singapore, Springer Nature Singapore, 57-67.
Documents
33358:638911
PDF
LP_FICTA_AAD.pdf - Accepted Version
Restricted to Repository staff only until 26 November 2024.
Available under License All rights reserved.
LP_FICTA_AAD.pdf - Accepted Version
Restricted to Repository staff only until 26 November 2024.
Available under License All rights reserved.
Download (403kB)
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.
More Information
Metrics
Altmetric Badge
Dimensions Badge
Share
Actions (login required)
![]() |
View Item |