Link prediction in complex networks: A survey

被引:1945
作者
Lue, Linyuan [1 ,2 ,3 ]
Zhou, Tao [1 ,4 ]
机构
[1] Univ Elect Sci & Technol China, Web Sci Ctr, Chengdu 610054, Peoples R China
[2] Shanghai Univ Sci & Technol, Res Ctr Complex Syst Sci, Shanghai 200093, Peoples R China
[3] Univ Fribourg, Dept Phys, CH-1700 Fribourg, Switzerland
[4] Univ Sci & Technol China, Dept Modern Phys, Hefei 230026, Peoples R China
基金
中国国家自然科学基金; 瑞士国家科学基金会;
关键词
Link prediction; Complex networks; Node similarity; Maximum likelihood methods; Probabilistic models; SCALE-FREE NETWORKS; COMMUNITY STRUCTURE; HIERARCHICAL ORGANIZATION; RECOMMENDER SYSTEMS; MISSING DATA; RANDOM-WALK; SIMILARITY; GRAPH; INTERNET; MODEL;
D O I
10.1016/j.physa.2010.11.027
中图分类号
O4 [物理学];
学科分类号
0702 ;
摘要
Link prediction in complex networks has attracted increasing attention from both physical and computer science communities. The algorithms can be used to extract missing information, identify spurious interactions, evaluate network evolving mechanisms, and so on. This article summaries recent progress about link prediction algorithms, emphasizing on the contributions from physical perspectives and approaches, such as the random-walk-based methods and the maximum likelihood methods. We also introduce three typical applications: reconstruction of networks, evaluation of network evolving mechanism and classification of partially labeled networks. Finally, we introduce some applications and outline future challenges of link prediction algorithms. (C) 2010 Elsevier B.V. All rights reserved.
引用
收藏
页码:1150 / 1170
页数:21
相关论文
共 174 条
[91]   The link-prediction problem for social networks [J].
Liben-Nowell, David ;
Kleinberg, Jon .
JOURNAL OF THE AMERICAN SOCIETY FOR INFORMATION SCIENCE AND TECHNOLOGY, 2007, 58 (07) :1019-1031
[92]   Empirical study of Chinese city airline network [J].
Liu, Hong-Kun ;
Tao, Zhou .
ACTA PHYSICA SINICA, 2007, 56 (01) :106-112
[93]   Structure and External Factors of Chinese City Airline Network [J].
Liu, Hong-Kun ;
Zhang, Xiao-Li ;
Zhou, Tao .
INTERNATIONAL CONFERENCE ON COMPLEXITY AND INTERDISCIPLINARY SCIENCES: 3RD CHINA-EUROPE SUMMER SCHOOL ON COMPLEXITY SCIENCES, 2010, 3 (05) :1781-1789
[94]  
[刘宏鲲 LIU HongKun], 2009, [中国科学. G辑, 物理学,力学,天文学, Science in China. Series G, Physics, Mechanics & Astronomy], V39, P935
[95]   Link prediction based on local random walk [J].
Liu, Weiping ;
Lue, Linyuan .
EPL, 2010, 89 (05)
[96]   Link prediction in weighted networks: The role of weak ties [J].
Lue, Linyuan ;
Zhou, Tao .
EPL, 2010, 89 (01)
[97]   Similarity index based on local paths for link prediction of complex networks [J].
Lue, Linyuan ;
Jin, Ci-Hang ;
Zhou, Tao .
PHYSICAL REVIEW E, 2009, 80 (04)
[98]   The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations - Can geographic isolation explain this unique trait? [J].
Lusseau, D ;
Schneider, K ;
Boisseau, OJ ;
Haase, P ;
Slooten, E ;
Dawson, SM .
BEHAVIORAL ECOLOGY AND SOCIOBIOLOGY, 2003, 54 (04) :396-405
[99]   ON A TEST OF WHETHER ONE OF 2 RANDOM VARIABLES IS STOCHASTICALLY LARGER THAN THE OTHER [J].
MANN, HB ;
WHITNEY, DR .
ANNALS OF MATHEMATICAL STATISTICS, 1947, 18 (01) :50-60
[100]   The Sum-over-Paths Covariance Kernel: A Novel Covariance Measure between Nodes of a Directed Graph [J].
Mantrach, Amin ;
Yen, Luh ;
Callut, Jerome ;
Francoisse, Kevin ;
Shimbo, Masashi ;
Saerens, Marco .
IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, 2010, 32 (06) :1112-1126