资源描述：
《一种新的链接预测方法在复杂网络中的应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、一种新的链接预测方法在复杂网络中的应用现实世界的很多系统可以用网络来描述，在网络中节点表示对象，链接表示对象间的联系⑴。近年来，复杂网络的研究和分析已经弓I起了很多学者的高度关注，逐渐成为诸多领域的一个硏究热点。然而，真实的复杂网络是动态变化的:随舂时间的推移，网络中的节点或边会快速的增长和变化。如何能够准确地预测未来网络中出现或消失的边是一个既有趣又富有挑战性的问题，例如：在朋友网络中，预测未来朋友间可能存在的新关系并进行推荐。上述问题就是所谓的链接预测问题,已经成为很多领域亟待解决的一个问题。作为链接挖掘的一个分支,链接预测是指根据已
2、知的网络拓扑结构或节点属性来预测复杂网络中未来存在链接的可能性［2,6］。传统的数据挖掘方法无法解决这个问题，其原因在于:传统的数据挖掘方法假定研究的对象实体之间是相互独立的，不考虑对象实体之间的关系。现有的链接预测方法主要是基于网络拓扑结构的方法，没有考虑复杂网络聚类信息在预测中的作用［2］。实际上，复杂网络的聚类结果中包含了很多对链接预测有用的信息,而这些信息对链接预测的效果能够起到很好的辅助作用，这一点已经被很多文献所证明:冯旭等人通过在人造和真实数据集上的实验，初步揭示了网络的聚类信息对链接预测性能的提升有较好的辅助作用［3］;S
3、oundarajan等人也通过实验证明了网络聚类信息在链接预测中的重要性［4］。针对上述问题,结合大多数复杂网络具有的无标度特性,本文提岀了一种基于聚类信息和网络特征的链接预测方法，通过后续实验表明,该方法具有较好的链接预测效果。2常用链接预测方法及其评估标准2.1常用链接预测方法现有的链接预测方法主要分为如下三类［5］:1）基于网络拓扑结构的方法：该类方法主要是根据网络的结构信息来进行链接预测。基于局部结构信息的方法虽然计算复杂度低，但是它的预测精度低；基于全局结构信息的方法虽然预测精度高，但是它的计算复杂度高［7,8］o2）基于最大似
4、然估计的方法：该类方法利用预先设定的一些规则和能够使得已知网络结构的似然估计最大化的参数来进行链接预测。虽然预测精度高，但是计算复杂度太高,不适合大规模的复杂网络分析［9］。3）基于机器学习的方法：该类方法首先提取已知网络结构中有用信息，然后利用机器学习的方法构建学习模型来进行链接预测。同样，该方法虽然预测精度高，但是计算复杂度太高，不适合大规模的复杂网络预测［10］。2.2预测精度评估标准通常情况下，链接预测精度的评估指标主要有下列2个：AUC和Precision⑸。1)AUC(Areaunderthereceiveroperating
5、characteristiccurve):该指标从整体上来衡量一个算法的链接预测精度。如果AUC的值越大z那么说明预测算法的预测精度越高。假设每次从测试集中随机选择一条边，用该边的分值与不存在边的分值做比较,S表示比较的总次数zM表示测试集中边比不存在边分值大的比较次数，L表示测试集中边与不存在边分值相等的比较次数，该评估指标的计算公式如下：2）Precision:该指标从局部角度衡量一个算法的链接预测精度。假设在按照所有未知边分值逆序排列的前S条边中包含G条测试集中的边,那么,该指标的计算公式如下：3基于聚类信息和网络特征的方法针对传统
6、数据挖掘技术存在的问题，根据复杂网络的无标度特性和网络的聚类信息，本文提出了一种融合网络聚类信息和无标度特性的链接预测方法。该方法的总体思想如下：首先，定义了一种融合网络聚类信息及其无标度特性的节点相似性度量新指标,然后，利用Newman快速算法获取复杂网络的最佳聚类结构［6,11-13］，在此基础上，通过已定义的节点相似性度量新指标进行链接预测。假设复杂网络可以用图G二（N,L）表示，在这里N、L分别表示网络G中节点的集合和边的集合；e二（x,y）GL表示节点x和y之间存在的关系；N（x）、CN（x,y）分别表示节点x的邻居集合和节点对
7、（x,y）共同邻居的集合。如果与节点对（x,y）属于同一社团的共同邻居的数量在该节点对共同邻居集合中占的比重越大，那么节点对（x,y）之间存在链接的可能性就越大。基于上述假设，在我们的方法中，网络的聚类信息定义如下:其中,表示与节点对（x,y）属于同一社区的共同邻居的集合。仅依靠网络的聚类信息提高预测的精度还不够,在我们的方法中还融入了绝大多数网络具有的无标度特性，其定义如公式（4）所示:其中，、分别表示节点和节点的度值,表示网络G中的任一节点。根据公式（3）和（4），我们定义节点对（x,y）的相似性度量新指标如下:其中，，是可调参数，它
8、调节聚类信息和网络特征信息在相似性度量中所占的比重。基于聚类信息和网络特征新方法的具体算法描述如算法1所示3)[Q,Cluster]=FastNewman(Trainset);〃采用Newma
