基于聚类系数链路预测算法改进.doc

基于聚类系数链路预测算法改进 　　摘要： 链路预测是指通过已知的网络信息来预测网络中的丢失边信息或者是错误连边信息，链路预测是对于网络分析和数据挖掘的一项支撑学科。经过数十年的学科发展，链路预测得到了长足的发展，大量新的预测算法得以提出。本文提出了一种基于网络节点中聚类系数的算法优化思路，并将该优化思路运用到9种经典的算法上，在5种真实数据集上的实验表明了该优化思路的可行性。链路预测的准确性研究多基于丢失边的预测，对于错误连边的准确性预测少有涉及，本文的实验部分同时涉及了丢失边的预测以及错误连边的预测。传统的链路预测比较实验，对于测试集多选取10%这一固定值，本文为了说明算法的健壮性，针对不同大小的测试集进行了广泛的实验 关键词：复杂网络；链路预测；聚类系数；错边识别；局部相似性 中图分类号：TP391 文献标识码：A 文章编号：1009-3044（2017）01-0239-05 Abstract： Link prediction is a subject which uses the current network information to predict the missing and spurious links， so it is a supporting discipline for network analysis and data mining. After decades of academic development， link prediction has achieve a lot of progress， a large number of algorithms have been proposed. In this paper， we have proposed an optimization thought which was inspired by clustering coefficient. We have applied this optimization methods to nine kinds of classical algorithms， results on five real data sets prove the feasibility of the optimization method. Former study on link prediction mainly focus on the prediction of missing links， while in this paper we have also concern the spurious links. Compared with the traditional research， we have doing experiments on varies ratio of training set， previous training set were fixed at 10% for the most conditions. Key words： complex networks； link prediction； clustering coefficient； spurious links； local similarity 1 概述 关于网络结构的研究已有数百年的历史，网络学科的理论发展经过了规则网络，随机网络和复杂网络三个阶段。网络上的首项研究可以追溯到1736年欧拉关于哥尼斯堡七桥问题的提出与解决，这属于规则网络时代的研究。之后的很长一段时间，网络学科都没有很大的发展。1959年，匈牙利的著名数学家Erd?s和Rényi建立了著名的随机图（ER）理论，这才将网络研究带入到了第二个阶段[1]。随机网络的提出将网络的理论研究拓展到了更为广泛的科研领域，比如社会学家也可以利用随机理论对于人类关系网络进行建模。复杂网络的开启主要归功于Watts和Strogatz在1998提出的小世界模型以及Barabási 在1999提出的无标度网络[2，3]。小世界网络指网络中大多数的节点不直接相连，但彼此之间只需通过少量节点即可以到达，即“六度分离”理论的诠释。无标度网络指网络中节点度的分布符合幂指数，即少数的节点具有很高的度分布而大多数节点的度相对较低 近年来，随着复杂网络学科的快速发展，作为其分支之一的链路预测研究也得到了越来越广泛的关注。网络中的链路预测是指根据网络现有的节点属性以及网络拓扑等信息来预测网络中尚未产生连边的两个节点之间产生链接的可能性[4]。链路预测包含了对于未知边的发掘以及网络演化中即?⒉?生的边的预测。链路预测很好地将网络与信息科学进行了连接，可以很好地