Theory explains how network links can be predicted more accurately
A Theoretical Perspective on Link Prediction Heuristics
Social and Information Networks
Summary
Networks connect things like people or websites, and guessing who might connect next is helpful. This paper explains why links involving very popular nodes, like celebrities, matter less when predicting new connections. The authors use a math model where nodes live in a hidden space and are more likely to connect if they're close there. They find the best way to weight connections based on how many links a node has, matching what people have seen before in experiments.
What this means in practice
- •For social network platform developers: Improve friend suggestion algorithms by using theoretically justified weighting of nodes according to their popularity.
- •For fraud detection teams: Enhance detection of suspicious connections in transaction networks by applying optimal degree-based link prediction heuristics.
Tested on simulated data.
Authors
Jiajie Shi, David A. Meyer
Abstract
In network analysis, nodes with different degrees are usually weighted differently in tasks such as link prediction. For example, two individuals connected to the same high-degree node (e.g., a celebrity) are often considered less likely to know each other than if they share a low-degree connection. In this paper, we theoretically justify the reasoning behind this heuristic using a graph generation model. In this model, nodes are embedded in a latent metric space, and edges are more likely to form between nearby nodes. We analytically derive degree-based weighting schemes for commonly used link prediction and similarity measures. In particular, we identify the optimal weighting scheme for the Common Neighbors index and extend our analysis to other popular heuristics, including the graph distance. Our theoretical findings align with previous empirical observations, and we further validate them through experiments on both synthetic and real-world networks.