一种新的链接预测方法在复杂网络中的应用

李奋华

摘要： 作为复杂网络分析的一项重要任务，链接预测已经被应用到诸多领域，例如：个性化推荐、决策支持系统和犯罪调查等。常用的链接预测方法主要是基于网络拓扑结构的方法，没有考虑网络的聚类信息因素。实际上，网络的聚类结果包含了对链接预测很重要的信息。在此基础上，一种基于聚类信息和网络特征的链接预测模型被提出，并在人造和真实网络数据集上进行了验证，具有较好的预测效果。

关键词： 数据挖掘；链接预测；复杂网络；无标度；聚类信息

中图分类号： TP301.6 文献标识码：A 文章编号：1009-3044（2016）18-0032-03

A Novel Link Prediction in Complex Networks

LI Fen-hua

（Department of Computer Science and Technology， Yuncheng University， Yuncheng 044000， China）

Abstract： Link prediction is an important task of complex network analysis， which has been applied in various domains such as personal recommendation systems， decision support systems， crime investigation and so on. The classical link prediction methods are based on network topology structure and its features， in which the clustering information has not been considered. However， the clustering results of a network contain some vital information for link prediction. In this paper， a novel link prediction based on network clustering information and its features is proposed. Through experiments on the synthetic datasets and real world datasets， our proposed method has the good prediction accuracy.

Key words： data mining； link prediction； complex networks； scale free； clustering information

1 引言

现实世界的很多系统可以用网络来描述，在网络中节点表示对象，链接表示对象间的联系[1]。近年来，复杂网络的研究和分析已经引起了很多学者的高度关注，逐渐成为诸多领域的一个研究热点。然而，真实的复杂网络是动态变化的：随着时间的推移，网络中的节点或边会快速的增长和变化。如何能够准确地预测未来网络中出现或消失的边是一个既有趣又富有挑战性的问题，例如：在朋友网络中，预测未来朋友间可能存在的新关系并进行推荐。上述问题就是所谓的链接预测问题，已经成为很多领域亟待解决的一个问题。

作为链接挖掘的一个分支，链接预测是指根据已知的网络拓扑结构或节点属性来预测复杂网络中未来存在链接的可能性[2，6]。传统的数据挖掘方法无法解决这个问题，其原因在于：传统的数据挖掘方法假定研究的对象实体之间是相互独立的，不考虑对象实体之间的关系。现有的链接预测方法主要是基于网络拓扑结构的方法，没有考虑复杂网络聚类信息在预测中的作用[2]。实际上，复杂网络的聚类结果中包含了很多对链接预测有用的信息，而这些信息对链接预测的效果能够起到很好的辅助作用，这一点已经被很多文献所证明：冯旭等人通过在人造和真实数据集上的实验，初步揭示了网络的聚类信息对链接预测性能的提升有较好的辅助作用[3]；Soundarajan等人也通过实验证明了网络聚类信息在链接预测中的重要性[4]。针对上述问题，结合大多数复杂网络具有的无标度特性，本文提出了一种基于聚类信息和网络特征的链接预测方法，通过后续实验表明，该方法具有较好的链接预测效果。

2常用链接预测方法及其评估标准

2.1 常用链接预测方法

现有的链接预测方法主要分为如下三类[5]：

1）基于网络拓扑结构的方法：该类方法主要是根据网络的结构信息来进行链接预测。基于局部结构信息的方法虽然计算复杂度低，但是它的预测精度低；基于全局结构信息的方法虽然预测精度高，但是它的计算复杂度高[7，8]。

2）基于最大似然估计的方法：该类方法利用预先设定的一些规则和能够使得已知网络结构的似然估计最大化的参数来进行链接预测。虽然预测精度高，但是计算复杂度太高，不适合大规模的复杂网络分析[9]。

3）基于机器学习的方法：该类方法首先提取已知网络结构中有用信息，然后利用机器学习的方法构建学习模型来进行链接预测。同样，该方法虽然预测精度高，但是计算复杂度太高，不适合大规模的复杂网络预测[10]。

2.2 预测精度评估标准

通常情况下，链接预测精度的评估指标主要有下列2个：AUC和Precision[5]。

1） AUC （Area under the receiver operating characteristic curve）：该指标从整体上来衡量一个算法的链接预测精度。如果AUC的值越大，那么说明预测算法的预测精度越高。假设每次从测试集中随机选择一条边，用该边的分值与不存在边的分值做比较，S表示比较的总次数，M表示测试集中边比不存在边分值大的比较次数，L表示测试集中边与不存在边分值相等的比较次数，该评估指标的计算公式如下：

2） Precision：该指标从局部角度衡量一个算法的链接预测精度。假设在按照所有未知边分值逆序排列的前S条边中包含G条测试集中的边，那么，该指标的计算公式如下：

3 基于聚类信息和网络特征的方法

针对传统数据挖掘技术存在的问题，根据复杂网络的无标度特性和网络的聚类信息，本文提出了一种融合网络聚类信息和无标度特性的链接预测方法。该方法的总体思想如下：首先，定义了一种融合网络聚类信息及其无标度特性的节点相似性度量新指标，然后，利用Newman快速算法获取复杂网络的最佳聚类结构[6，11-13]，在此基础上，通过已定义的节点相似性度量新指标进行链接预测。

假设复杂网络可以用图G= （N， L）表示，在这里 N、 L分别表示网络G中节点的集合和边的集合； e=（x， y） ∈L 表示节点x 和y之间存在的关系；N（x）、CN（x， y） 分别表示节点x 的邻居集合和节点对（x， y） 共同邻居的集合。如果与节点对（x， y） 属于同一社团的共同邻居的数量在该节点对共同邻居集合中占的比重越大，那么节点对（x， y）之间存在链接的可能性就越大。基于上述假设，在我们的方法中，网络的聚类信息定义如下：

其中，表示与节点对（x， y） 属于同一社区的共同邻居的集合。仅依靠网络的聚类信息提高预测的精度还不够，在我们的方法中还融入了绝大多数网络具有的无标度特性，其定义如公式（4）所示：

其中，、分别表示节点和节点的度值，表示网络G中的任一节点。根据公式（3）和（4），我们定义节点对（x， y） 的相似性度量新指标如下：

其中，，是可调参数，它调节聚类信息和网络特征信息在相似性度量中所占的比重。

基于聚类信息和网络特征新方法的具体算法描述如算法1所示：

3）[Q， Cluster] = FastNewman（Trainset）； //采用Newman快速算法进行网络聚类。

4）Bestcluster = ChooseBestCluster（Q， Cluster）； //选择当Q最大时最佳的网络聚类结果。

5）根据公式（5）和参数，计算训练集网络中每个未连接节点对的相似性度值；

6）根据测试集Testset和第5）步获得的所有的值，计算网络的预测精度值AUC；

7）Return AUC； ]

上述算法1主要依赖4个基本操作：1、3、5和6，所以该算法的时间复杂度为，适合大规模复杂网络分析。

4 实验分析

本节将针对BCFLP算法进行实验，并对实验结果进行详细分析。

4.1 实验环境和数据集

1） 实验环境

本实验的实验平台采用的是一台联想Thinkpad T450笔记本电脑，该笔记本电脑的处理器为Intel（R） Core i5@ 2.2GHz、操作系统为64位的Windows 8、内存为8.00GB，算法程序采用Matlab 2012a语言实现。

2） 实验数据集

本实验数据集分为两类：人造数据集和真实网络数据集。人造数据集由2个由BA模型生成的人造网络BA（N， m）组成[14]，其中，N、m分别表示网络的节点个数和每加入一个新节点需要连接的边数，具体的网络拓扑特性如表1所示。

在表1中， 表示网络的平均度，C 表示网络的聚类系数，APL表示网络的平均路径长度。

真实网络数据集如表2所示，其中，Karate表示由作者Wayne Zachary收集的一个美国大学karate俱乐部34个成员之间相互联系的复杂网络[15]；UST表示一个美国航空交通网络[16]；PB表示一个美国政治博客复杂网路，原始网络中边的有向性和自连接性被忽略。上述这些真实网络数据集均可以从斯坦福大学官网获得[17]。

4.2 实验结果及其分析

在实验中，我们把初始网络随机地划分为训练集和测试集两部分。其中，训练集包含初始网络90%的边，测试集包含初始网络剩余90%的边。为了验证新方法的预测精度，我们与下列典型的预测算法做了比较：CN、AA、RA、PA和Katz [2]。图1描述了我们的新方法BCFLP与上述方法在人造数据集上的预测精度比较结果，其中，算法的参数θ=0.4，Katz方法的参数β=0.0005。类似，图2描述了BCFLP方法与其他方法在真实网络数据集上的预测精度比较结果，其中，算法的参数θ=0.9，Katz方法的参数β=0.000。

从图1中，我们有如下发现： 1）与其他方法相比，BCFLP方法在人造网络数据集上具有最佳的链接预测精度。2）随着网络的聚类系数增加，上述这些方法的预测精度都得到了明显的提升。3） 除了BCFLP方法之外，CN、AA、RA和PA方法也有不错的链接预测性能。为了进一步验证BCFLP方法的预测性能，我们在真实网络数据集上进行了实验，如图2所示，通过对实验结果分析，我们获得了与图1相同的结论。从上述分析表明，与现有典型的链接预测方法相比，我们的新方法BCFLP在链接预测性能方面具有明显的优势，同时也进一步验证了网络的聚类信息对链接预测的重要作用。从计算复杂度和预测精度两方面考虑，我们的新方法适合对规模较大的复杂网络的分析。

5 结束语

为了获得较高的链接预测精度，本文提出了一种简单而有效的复杂网络链接预测方法，该方法在网络无标度特性的基础上融入了网络的聚类信息。在人造和真实网络数据集上的实验表明：与其他预测方法相比，该方法具有较高的链接预测精度。

在未来的研究中，一方面，我们需要对更多的其他网络数据集进行测试。另一方面，我们把网络节点的语义或内容信息融入到我们的方法中，来进一步提高我们方法的链接预测精度。

参考文献：

[1]L. Getoor， C. P. Diehl. Link mining： a survey [J]. ACM SIGKDD Explorations Newsletter， 2005， 7（2）： 3-12.

[2]Liben-Nowell， J.Kleinberg. The link prediction problem for social networks[J]. Journal of the American society for information science and technology， 2007， 58 （7）： 1019-1031.

[3]Feng X.，Zhao J.，Xu K. Link prediction in complex networks： a clustering perspective[J]. the European Physical Journal B， 2012， 85： 1-9.

[4]Soundarajan S.，Hopcroft J.Using community information to improve the precision of link prediction methods[J]. in Proceedings of the 21st International Conference Companion on World Wide Web， 2012： 607-608.

[5]吕琳媛.复杂网络链路预测 [J]. 电子科技大学学报， 2010， 39（5）： 651-661.

[6]Clauset A.， Newman M. E.，Moore C. Finding community structure in very large networks[J]. Physical Review E， 2004， 70（6）： 066111.

[7]Getoor L. Link mining： a new data mining challenge[J]. ACM SIGKDD Explorations Newsletter，2003（5）： 84-89.

[8]ieter B. T. M.-F. W.，Koller A. D. Link prediction in relational data[J].Learning Statistical Patterns in Relational Data Using Probabilistic Relational Models， 7， 2005.

[9]Liu W.，Lü L. Link prediction based on local random walk [J]. EPL （Europhysics Letters）， 2010， 89.

[10]Zhou T.，Lü L.，Zhang Y.-C. Predicting missing links via local information[J]. the European Physical Journal B， 2009， 71： 623-630.

[11]Clauset A.，Moore C.，Newman M. E. Hierarchical structure and the prediction of missing links in networks[J]. Nature， 2008， 453： 98-101.

[12]Guimerà R.，Sales-Pardo M. Missing and spurious interactions and the reconstruction of complex networks[C]. Proceedings of the National Academy of Sciences， 2009， 106： 22073-22078.

[13]O'Madadhain J.，Hutchins J.，Smyth P. Prediction and ranking algorithms for event-based network data[J]. ACM SIGKDD Explorations Newsletter，2005，7： 23-30.

[14]Barabási A.-L.，Albert R. Emergence of scaling in random networks[J]. Science， 1999， 286： 509-512.

[15]Zachary W. An information flow model for conflict and fission in small groups[J]. Journal of Anthropological Research， 33： 452-473， 1977.

[16]Batagelj V.，Mrvar A. Pajek datasets [DB]. 2007.

[17]Ackland R. Mapping the US political blogosphere [EB]. Presentation to Blog Talk Downunder， 2005.