Link prediction improved by combining node importance and local network patterns
Link prediction in complex networks via fusing node centrality and local similarity indices
Social and Information Networks
Summary
Predicting missing or future links in networks often uses local clues like shared neighbors, but this can fail when nodes have no neighbors in common. The authors show that combining measures of node importance, called centrality, with these local clues improves predictions. They introduce a new way to fuse these metrics using PageRank and a new centrality called DomiRank, proving this approach works better across many real-world networks. Their best combined method outperforms some established global methods, and their framework can be extended to other centrality and similarity measures.
What this means in practice
- •For network engineers: Improve link prediction in communication or social networks by combining node importance scores with local connectivity patterns for more accurate topology inference.
- •For recommendation system developers: Enhance recommendation algorithms by better predicting likely user-item links through fusion of global importance and local similarity in large sparse data.
Authors
Yingying Zhang, Chengye Zhao
Abstract
Local similarity indices are widely used in link prediction on complex networks owing to their low computational cost; however, in sparse networks they assign a zero score to every node pair lacking common neighbors, which severely limits their predictive power. A natural remedy is to fuse node centrality indices with local similarity indices: the former provide global importance for the node pair, while the latter capture fine-grained local topology, and the two can be combined into complementary scores within a unified framework. This paper uses PageRank and DomiRank as two representative centrality measures and constructs a centrality--local-similarity fusion framework. The PageRank-based fusion proposed by Charikhi is first generalized to seven classical local similarity indices, and the universality of its improvement is systematically verified on nine real-world network datasets. Furthermore, the DomiRank centrality is introduced to build the DR-MD series of fused indices under a unified weighting coefficient, which overcomes the drawback that the PageRank-based fusion requires index-by-index weight tuning. Results of five-fold cross-validation together with Wilcoxon signed-rank tests show that, under the unified experimental protocol, all DR-MD indices consistently outperform the corresponding local baselines and their PR-MD counterparts on all nine datasets ($p=0.002$), and that the improvements remain robust against perturbations of $σ$ and the weighting coefficients within the near-critical parameter plateau; in particular, DR-RA achieves an average AUC of 0.7084, surpassing global methods such as Katz and RWR as well as several advanced similarity indices. The framework is inherently extensible, and its fusion paradigm can be straightforwardly generalized to couple other node centrality indices with local similarity indices.