第30卷第2期安徽工程大学学报 2015年4月Journal of Anhui Polytechnic University Apr. .2015 文章编号:1672-2477(2015)02-0060-04基于社区信息的链接分析与预测研究杨磊，李臣龙，汪精(安徽工程大学计算机与信息学院，安徽芜湖241000) 摘要:社区结构是社交网络最重要的拓扑特性之一，有助于理解用户分布和用户行为，提高链接预测的精确度.通过分析社区结构，结合贝叶斯理论，提出了一种新的基于社区信息的链接预测方法，并应用于真实的社交网络数据中对未来链接进行分析与预测.实验演示了该方法的优点和有效性，取得了很好的预测效果.关键词:链接预测;社会网络分析;社区结构;链接分析中图分类号:TP391文献标识码:A链接关系在数据挖掘中已经成为了新的研究热点，链接预测利用网络历史结构信息来预测未来节点之间产生链接的可能性.社交网络作为一种图结构，对链接更加关注.通过链接预测方法可以预测未结交的用户中哪些"应该是朋友"[IJ此外，链接预测方法还可以应用于预测一篇学术论文的类型或合著者关系，发现网络中恐怖分子的恐怖活动信息以及预测手机用户是否会切换运营商等领域.链接预测问题有两种不同的解决策略，即:监督的和无监督的.无监督链接预测方法有CN(Common neighbors)、AA(Adamic-Adar)等多种算法[幻，而基于监督的链接预测方法通常是作为一个分类问题.大多数无监督的和监督的解决方案关注于开发本地或全局结构化网络信息，其他的信息如社区信息等并没有得到充分利用.为了改善链接预测精度.Hoseini町等提出了混合的方法，利用结构化信息和社区信息进行链接预测;Liaghat[4J等利用回归分析模型预测社交网站用户之间的链接关系，取得了较好的效果;5JFené等发现当网络社区结构增长时，基于结构化信息的链接预测方法的精确度将会有很大提高.本文基于社区信息对社交网络进行链接分析与预测，通过社区发现算法对社交网络进行了社区划分，分析了网络顶点在同一社区和不同社区对预测结果的影响，把新的方法应用在社交网络数据中，进行了实验验证并与其他经典链接预测算法做了对比，更好地实现了对网络节点之间链接关系的预测.1 问题描述与评价方法对于杜交网络定义网络图G().其中V为网络图的顶点集合.E为网络图中边的集合，即链接集合.假设1VI表示V集合中的顶点数量，则V集合中顶点之间所有可能的链接数量为1V 1 (1 V 1一1)/2条，记为全集U.则网络中属于U但不属于E的链接即为不存在的链接，记为U-E.链接预测方法的基本任务是在集合ιE中找出可能存在的链接，为每个可能的链接指派一个分数并降序排列.假定可能链接的顶点对()εCU-E) ，则该分数记为SX'Y'分数乱.y值越高，则顶点对归，y)间链接存在的可能性越大.TPT为了衡量链接预测算法精确性，集合E被划均为两部分.叩.训练集E和测试集E显然E=EU PTP E且En E=φ.将训练集信息作为算法的输入，然后将预测结果和测试集信息比较并根据评价指标衡量预测算法性能.本文使用AUC[6JCArea Under the Receiver Operating Characteristic Curve)指标来衡量算法的精确性.AUC表示测试集中的边的分数值比随机选择的一个不存在的边的分数值高的概率，即每次随机从测试集中选取一条边与随机选择的不存在的边进行比较，如果测试集中边的分数值大于不存在的边的分数值，就加1分;如果两个分数值相等，就加分.假定n是独立比较的次数，如果有n次测试集中的边的分数值大于不存在的边的分数，有n次两分数值相等，则AUC的值为:收稿日期:2014-C7-28 基金项目:安徽省高校省级优秀青年人才重点基金资助项目(2013SQRL034Z凹，安徽工程大学校青年基金资助项目(2009YQ040) 作者简介:杨磊0982-)，男，安徽l恪泉人，讲师，硕士.
第2期杨磊，等:基于社区信息的链接分析与预测研究61 AUC =(n十η)/71(1) 显然，当所有分数是独立同分布时，AUC的值等于，链接预测算法的测试精度可以用AUC大于的程度来描述，AUC越大，算法精度越高.2 基于社区信息的链接预测方法假定网络G中，存在M>l个社区，分别用C，C，…，C等标签表示.当一个顶点xEV属于标签12MCC，的社区，则该顶点用X•表示，其中=1，2.….M.每个顶点看作属于一个单独的社区.社区图样例如图l所示.由图1可知，图1中有12个顶点和19条链接，为了标识方便，每个顶点用数字和颜色做了标识，同样颜色的顶点属于同一社区.顶点从1~5属于社区Cj，用灰色表示;顶点6~8属于社区C，用白色表示;顶点9~ 12属2于社区C，用黑色表示. 社区发现篝法本文使用标签传播算法(Lab el Propagation 图1社区图Algorithm, LPA)[1]作为社交网络中的社区发现算法.LPA是一个简单快速且具有近于线性时间复杂度的社区发现方法，基本思路是用己标记顶点的标签信息去预测未标记节点的标签信息.LPA为网络图中每个顶点分配一个标签，一对顶点所形成的链接表示顶点相似度，顶点标签按相似度传播给其他顶点，并且该顶点标签为其大多数邻近顶点的标签，相似顶点的标签越趋于一致，其标签越容易传播.在标签传播过程中，保持已标注数据的标签不变，连步传向来标注数据.当迭代过程结束时，那些具有相同标签的顶点便组合构成了同一个社区，从而完成标签传播过程. 链接预测方法假设r(.x)表示顶点Z的邻居顶点集合，r(y)表示顶点y的邻居顶点集合，则A•=r(川nrcy) Iy表示未链接的顶点对(x，y)的共同邻居集合.根据贝叶斯理论，为顶点对(x，y)分配相同社区标签C，的条件概率为:ccP( 1 x. .yc. )P(x, ,yc.) Cp (X, .yC, 1 A ) = ~ (2) yI三~P(XCi,yc. )P(XCi ，y巳|人'，") i=l 同理.如顶点对(工，y)分配不同社区标签c;和C的条件概率为:jCi CCP(X,yC, 1 ) =P( 1 x’ ,yC, )P(X, .yC, )/P() (3) 根据式(2)和式(3)很难独立确定顶点对()是在相同社区标签下还是在不同社区标签下更有可能存在链接.假设A:.y={ZC E AJ,y 1 X’ ，yC}是具有相同社区标签的共同邻居的集合，A~，y=A川-AL是具有不同社区标签的共同邻居集合，则=A:.y U A~.y，显然A;.y门A~.y=φ. 具有同一社区标签的共同邻居数量越多，顶点工和y越有可能属于该社区.则顶点(工，y)具有相同社区标签C，的共同邻居的概率可以定义为具有同一社区标签的共同邻居的数量除以共同邻居总数量，方程如下:P ( 1 :Ø’ ,yCi) =1 A:.y 1 / 1 Ar,y 1 (4) J同理，顶点(工，y)具有不同社区标签C和C的共同邻居的概率可以定义为属于不同社区标签共同ij邻居的数量除以共同邻居的总数量，方程如下:Ci 1 X,yC,) =1 A~.y 1 / 1 A.,y 1 (5) x为了预测节点对(x，y)之间链接存在的可能性，定义分数作为式(2)和式(3)的比率，分别代入式(4)和式(5)，可以得到方程如下2Ci Ci =1 A了.yIXP(x,yC’)/CI A~，y IXP(x,yCi)) (6) 当C.=C时，P(x~，y~)/(P(x~，y~)值为1.此时可得到丘.y=1 A~.y 1/ 1A ~.y 1; 当C，弓丘C时，A了.yjj
62 安徽工程大学学报第30卷=φ，则乱.y=0.当A~.y=时，则A~.y=0，为了避免分母A;.y为0，把A~.y替换为.根据= A~.y U A~.y，总体上该替换不改变链接预测的结果，可得方程如下z(7) s;.y =1 A~.y 1 / 1 1 3 实验方案 实验数据采用3种具有代表性的社交网络，即:Sina微博、Twitter和微博数据来源于数据堂[剖，后两种社交网络数据均来源于Stanford[9]，它们的网络拓扑性质如表I所示.其中，IVI表示网络顶点数，1E 1表示网络边数，C为平均网络聚集系数.表1实验数据网络拓扑性质Ivl C I E I Sina微博79,120 515,581 Twitter 81,306 1, 768,149 Facebook 4039 88,234 实验结果与分析实验中编程语言:Java，CPU:Intel Xeon E5504，内存:8G.随机选取实验数据集中90%的链接作为训练集，其余10%的链接为测试集，对训练集使用本文所提方法进行链接预测.通过与经典算法CN、AA对比，根据AUC评估方法，实验执行10次且进行5次随机选取训练集和测试集并且汁算AUC平均值，结果如图2所示.从图2可以看出，本文方法在Sína微博和Facebook取得了最好的预测准确率，在Twitter网络预测准确率仅次于CN算法.通过分析10次AUC值的标准差，结果如图3所示.从图3可以看出，本文方法在Twitter数据集上标准差最小，意味着每次执行结果值与平均值较近，预测算法稳定性最好;其中，在Sina微博数据集中的标准差最大，表明本算法在该数据集虽然取得了较高的预测准确率，但预测结果准确性并不稳定.各个算法在不同数据集上的运行时间对比如图4所示. 唰..本 文方法--CN-....AA "唱-本文方法-喝一CN.......AA ~丛斗 , , , , , , , , M• Sina微博Twitter Facehook Sin微博Twitter Facehook 图2链接预测结果对比图图3AUC标准差在算法效率方面，CN和AA算法的时间复杂20 r -+-Sina徽博-. -Twitter -.-Facehook 2度均为O(N).本文杜区发现算法的时间复杂度[6 A 一且--------.…------一，为O(N)，计算AUC的时间复杂度为OCK祷l\lI), 计算s;巾的时间复杂度是O((M+N)祷N)，所以38 2总体上本文方法的时间复杂度为O(N)(N是初4 ι 由四.....，晶4 -始网络G的节点数;M是链接数;K表示网络中不。本文方法CN AA 存在的链接数).因此，在保证算法复杂度的情况圈4算法运行时间下，取得了较好的预测效果.4 结论在链接分析与预测理论基础上，提出了基于社区信息的链接分析与预测方法.考虑了同一社区和不同社区间网络顶点的硝互关系，对3个不同社交网络数据集进行了实验.实验结果表明，新算法的预测准确性有所提高.当然，随着复杂社交网络的快速发展，链接预测在大规模网络数据的分析应用还有待更进一步深入研究.
第2期杨磊，等g基于社区信息的链接分析与预测研究 63 参考文献:[lJ D Sharma, U Sharma,S K experimental comparison of link prediction techniques in social networks[ J Model Optim,2014,4(1) :21-24. [2J 吕琳援.复杂网络链路预测口J.电子科技大学学报，2010，39(曰:651-661. [3J E Hoseini, S Hashemi, A Hamzeh. SPCF: a stepwise partitioning for collaborative filtering to alleviate sparsity prob›lems[ of Information Science，2012，38(的:578-592. [4J Z Liaghat,A H Rasekh,A of data mining methods for link prediction in social networks[ Network Analysis and Mining, 2013,3(2) : 143-150. [5J X Feng,] C Zhao,K prediction in complex networks: a clustering perspective[J].The European Physical Jour›nal B,2012,85(l):1-9. [6J J A Hanley, B J McNeil. The meaning and use of the area under a receiver operating characteristic (ROC) curve[›diology, 1982,143(1) : 29-36. [7J U N Raghavan,R Albert,S linear time algorithm to detect community structures in large-scale networks [J].Physical Review E,2007, 76 (3) : 1-11. [8J 数据堂.科学数据共享平台[EB/OL]..[2014-05-l1J.[9 J J Leskovec. Stanford large network dataset collection[EB/OL]. http:/ / snap. stanford. edu/ data/index. html. [2012-11 08]. Research on Iink analysis and prediction based on community information Y ANG Lei, LI Chen-long, W ANG Jing (College of Computer and Information,Anhui Polytechnic University, Wuhu 241000, China) Abstract: Community structure is one of the most important social network topological characteristics, which can help to understand the distributions and behaviors of users, and improve the accuracy of the link analyzing the community structure,according to Bayesian theory,a new method of link prediction based on community information is proposed, applied to several real social network datasets for predicting and analyzing the future link. The experiment demonstrates the advantages and eHective›ness of this method, which achieves a good prediction performance. Key words: link prediction; social network analysis; community structure; link analysis
