Role of Weak Ties in Link Prediction of Complex Networks

2009/07/10 by Linyuan Lu, Linyuan Lü, Tao Zhou +2
Computer Science · Mathematics · Physics and Astronomy · #Advanced Graph Neural Networks #Complex Network Analysis Techniques #FOS: Computer and information sciences #Graph theory and applications #Information Retrieval (cs.IR) #cs.IR

paper · pdf · doi:10.48550/arxiv.0907.1728

4 pages, 1 figure and 2 tables. Accepted by CIKM workshop, see http://www.dcs.bbk.ac.uk/~dell/cnikm09/#programme

openalex publication_date 2009/07/10 · arxiv created 2009/08/14 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Plenty of algorithms for link prediction have been proposed and were applied to various real networks. Among these works, the weights of links are rarely taken into account. In this paper, we use local similarity indices to estimate the likelihood of the existence of links in weighted networks, including Common Neighbor, Adamic-Adar Index, Resource Allocation Index, and their weighted versions. In both the unweighted and weighted cases, the resource allocation index performs the best. To our surprise, the weighted indices perform worse, which reminds us of the well-known Weak Tie Theory. Further extensive experimental study shows that the weak ties play a significant role in the link prediction problem, and to emphasize the contribution of weak ties can remarkably enhance the predicting accuracy.

Citations

• The Strength of Weak Ties
• Friends and neighbors on the Web
• The meaning and use of the area under a receiver operating characteristic (ROC) curve.

Related

• Robustness of Link-prediction Algorithm Based on Similarity and Application to Biological Networks
• NEW: A Generic Learning Model for Tie Strength Prediction in Networks
• Predicting missing links via correlation between nodes
• Link Prediction in Complex Networks by Multi Degree Preferential-Attachment Indices
• A Survey of Link Prediction Algorithms