A survey of structural node-similarity methods for link prediction in complex networks

Abstract

This paper surveys several commonly used techniques for link prediction in networked/relational systems. This survey considers the body of literature from networks science, social networks analysis, and related research, and surveys several well-known analytical methods based on structural similarity of participating nodes. These methods that have been or could be used for solving the problem of link prediction in networked systems. The paper starts with a formalization of the link prediction problem previously given in the context of social networks. We discuss the notion of structural similarity among nodes in a network, and why and how these structure-derived node similarity measures also quantify the likelihood of the presence of future links in the network. The surveyed methods include proximity indices based on graph-theoretic distances between nodes, as well as, on local and global neighbourhoods. The authors identify and discuss a number of challenges which complicate link prediction due to certain conditions, or due to the necessity of consideration of exogenous factors to the network rather than just its endogenous structural properties.