Scalable Link Prediction in Complex Networks Using a Type of Geodesic Distance

Ruwayda Alharbi (King Saud University & Taibah University, Saudi Arabia); Hafida Benhidour and Said Kerrache (King Saud University, Saudi Arabia)

Identifying potential missing links in complex networks has attracted the attention of many researchers in recent years due to the wide range of its applications. Link prediction algorithms need to be efficient from a computational point of view in order to be scalable to networks with a large number of nodes and/or edges. In this paper, we propose, FastLP, a fast and scalable method based on a hidden variables model for solving the link prediction problem in large networks. Recent studies suggest that real networks have an underlying hidden metric space that explains their structural characteristics. The proposed approach computes the geodesic distances between unconnected nodes using the estimated distances between the connected nodes in the hidden metric space and subsequently use these distances to infer the probability of connection. The results show that this method can handle large networks while still keeping high prediction performance.

Journal: International journal of simulation: systems, science & technology V18

Published: Mar 31, 2017

DOI: 10.5013/IJSSST.a.18.01.15