许小可1 许爽1 朱郁筱2 张千明2
1.大连民族学院信息与通信工程学院;
2.电子科技大学互联网科学中心
摘要：为从理论上比较各种预测方法的优劣,分析多个网络演化过程中形成链接的两个节点之间的拓扑距离分布,阐明了传统基于共同邻居相似性指标可有效进行链路预测的机理,从理论上分析了9种基于共同邻居相似性算法的预测上限(可预测性)。通过分析一阶邻居预测算法的局限性和影响链路可预测性的因素,提出了两种基于高阶路径信息的链路预测算法并计算了他们的可预测性指标。从理论上提出了链路的可预测性指标,也通过对实际网络的预测证明了所提链路预测算法的有效性。
基金资助：国家自然科学基金(61004104,61104143)； 中央高校基本科研业务费专项基金项目(DC120101132,DC13010215)![]()
Link Predictability
in Complex NetworksXU Xiaoke1, XU Shuang1, ZHU Yuxiao2, ZHANG Qianming21.College
of Information and Communication Engineering, Dalian Nationalities University;2.Web Science Center, University of Electronic Science
and Technology of ChinaAbstract: Link predictability in complex networks refers to the upper limit for link prediction accuracy by using prediction algorithm, and the analysis of link predictability is conductive to compare the pros and cons for various prediction methods in theory. In this paper, we analyzed the topological distance distribution between two nodes forming a link during the process of multiple networks evolution, and then illustrated the mechanism for making effective link prediction based on common neighbor similarity index. At last, we analyzed the prediction upper limit (predictability) for nine algorithms based on common neighbor similarity in theory. By analyzing the limitation of first order neighbor prediction algorithm and the factor affecting link predictability, we propose two types of link prediction algorithms based on high order path information and calculate their predictability index. This study proposed the link predictability index in theory, and proved the validity of the proposed link prediction algorithm by predicting real networks.Keywords: complex networks; link prediction; similarity index; local structure
作者介绍:
第一作者: 许小可(1979- )，辽宁大连人，教授，博士，主要从事非线性时间序列分析和复杂网络方面的研究。许小可,许爽,朱郁筱,张千明.复杂网络中链路的可预测性[J].复杂系统与复杂性科学,2014,11(1) :41-47.
XU Xiaoke,XU Shuang,ZHU Yuxiao,ZHANG Qianming.Link Predictability in Complex Networks[J]. Complex Systems and Complexity Science, 2014,11(1):41-47.↓↓↓全文请点下方阅读原文![]()
