Abstract
Link prediction is an important task that estimates the probability of there being a link between two disconnected nodes. The similarity-based algorithm is a very popular method that employs the node similarities to find links. Most of these types of algorithms focus only on the contribution of common neighborhoods between two nodes. In sociological theory, relationships within three degrees are the strong ties that can trigger social behaviors. Thus, strong ties can provide more connection opportunities for unconnected nodes in the networks. As critical topological properties in networks, node degrees and node clustering coefficients are well-suited for describing the tightness of connections between nodes. In this paper, we characterize node similarity by utilizing the strong ties of the ego network (i.e., paths within three degrees) and its close connections (node degrees and node clustering coefficients). We propose a link prediction algorithm that combines topological properties with strong ties, which we call the TPSR algorithm. This algorithm includes TPSR2, TPSR3, and the TPSR4 indices. We evaluate the performance of the proposed algorithm using the metrics of precision and the Area Under the Curve (AUC). Our experimental results show the TPSR algorithm to perform remarkably better than others.
Introduction
Link prediction—the task of estimating the likelihood of a connection forming between two currently disconnected nodes—is a cornerstone of modern data science, powering applications from social network recommendations to biological discovery. Most existing similarity-based algorithms suffer from two main flaws: the "Common Neighbor Trap," where nodes without immediate shared neighbors are assigned zero similarity, and "Topological Blindness," where the quality and density of shared connections are ignored.
The authors address these limitations by bridging the gap between fast local indices and accurate but computationally expensive global indices. By incorporating paths up to three degrees of separation and weighting them by local topological features, the proposed TPSR algorithm achieves high accuracy without the prohibitive cost of global network analysis.
Methodology
The TPSR (Topological Properties and Strong Ties) algorithm defines node similarity through three specific indices:
- TPSR2: Refines the standard common neighbor approach by weighting shared neighbors based on their degree and clustering coefficient, capturing the "tightness" of local connections.
- TPSR3: Incorporates paths of length 3, motivated by sociological theory suggesting that "strong ties" within three degrees are primary drivers of relationship formation.
- TPSR4: Extends the logic to paths of length 4.
By focusing on paths of length 2 and 3, TPSR maintains a time complexity of $O(N^3)$, making it as efficient as the popular Local Path (LP) algorithm while significantly improving accuracy.
Experimental Results
The researchers evaluated TPSR against 14 diverse real-world networks, including social (Facebook), biological (Yeast), and infrastructure (Power grid) datasets. Performance was measured using Area Under the Curve (AUC) and Precision.
Key Insights
- The Power of Three: Moving from length-2 paths to length-3 paths (TPSR3) provided a massive jump in prediction accuracy, especially in sparse networks where common neighbors are rare.
- Clustering as a Weight: TPSR recognizes that a shared neighbor with a high clustering coefficient acts as a stable "bridge," making a future link between its neighbors much more likely.
- Diminishing Returns of Depth: While TPSR3 is a major improvement, TPSR4 often showed stagnant performance, suggesting that after three degrees, the similarity signal becomes too noisy.
Discussion and Conclusion
TPSR3 outperformed all other algorithms in the majority of datasets. For example, on the Yeast network, TPSR3 improved precision by 11.3% over the next best method. In sparse networks like "Router" or "Power," TPSR's ability to look at 3-step paths allowed it to find potential links that local methods missed entirely. While $O(N^3)$ complexity is efficient compared to global methods, future work will focus on scaling these techniques for massive graphs with billions of nodes and extending the framework to directed and weighted networks.
Summary updated