Journal
PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA
Volume 112, Issue 8, Pages 2325-2330Publisher
NATL ACAD SCIENCES
DOI: 10.1073/pnas.1424644112
Keywords
link prediction; complex networks; structural perturbation; predictability
Categories
Funding
- National Natural Science Foundation of China [11222543, 11075031, 11205042, 61433014]
- NESS Project
- CCF-Tencent Open Research Fund
- research start-up fund of Hangzhou Normal University [PE13002004039]
- EU FP7 Grant [611272]
- Program for New Century Excellent Talents in University [NCET-11-0070]
- US National Science Foundation [1125290, 0855453]
- Direct For Mathematical & Physical Scien
- Division Of Physics [0855453] Funding Source: National Science Foundation
- Div Of Civil, Mechanical, & Manufact Inn
- Directorate For Engineering [1125290] Funding Source: National Science Foundation
Ask authors/readers for more resources
The organization of real networks usually embodies both regularities and irregularities, and, in principle, the former can be modeled. The extent to which the formation of a network can be explained coincides with our ability to predict missing links. To understand network organization, we should be able to estimate link predictability. We assume that the regularity of a network is reflected in the consistency of structural features before and after a random removal of a small set of links. Based on the perturbation of the adjacency matrix, we propose a universal structural consistency index that is free of prior knowledge of network organization. Extensive experiments on disparate real-world networks demonstrate that (i) structural consistency is a good estimation of link predictability and (ii) a derivative algorithm outperforms state-of-the-art link prediction methods in both accuracy and robustness. This analysis has further applications in evaluating link prediction algorithms and monitoring sudden changes in evolving network mechanisms. It will provide unique fundamental insights into the above-mentioned academic research fields, and will foster the development of advanced information filtering technologies of interest to information technology practitioners.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available