基于优化标签传播算法的社区发现研究-龚宇.pdf

《基于优化标签传播算法的社区发现研究-龚宇.pdf》由会员分享，可在线阅读，更多相关《基于优化标签传播算法的社区发现研究-龚宇.pdf（54页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1必渊必黄。-jl：3Q!：S1二代鹧!：学号上Q琏131Q3Q3密级猷蓠妥毋拨走哮硕士学位论文基于优化标签传播算法的社区发现研究学位申请、： 龚字学科分韭指导教师答辩日期梦算机科长复挞张智副教授三塑年酆14日_ 一万方数据A Dissertation Submitted in Partial Fulfillment of the Requirementsfor the Degree of Master in EngineeringResearch of Community Detection Based onOptimized Label：Propagation AlgorithmMaste

2、r Candidate：Major：Supervisor：GongYuComputer Science and TechnologyAssoProfZhang ZhiWuhan University of Science and TechnologyWuhan，Hubei 430081，PRChinaMay 14恤，2017万方数据武汉科技大学研究生学位论文创新性声明本人郑重声明：所呈交的学位论文是本人在导师指导下，独立进行研究所取得的成果。除了文中已经注明引用的内容或属合作研究共同完成的工作外，本论文不包含任何其他个人或集体己经发表或撰写过的作品成果。对本文的研究做出重要贡献的个人和集体，均

3、己在文中以明确方式标明。申请学位论文与资料若有不实之处，本人承担一切相关责任。论文作者签名： 垄要 日期：丝!【=!：!研究生学位论文版权使用授权声明本论文的研究成果归武汉科技大学所有，其研究内容不得以其它单位的名义发表。本人完全了解武汉科技大学有关保留、使用学位论文的规定，同意学校保留并向有关部门(按照武汉科技大学关于研究生学位论文收录工作的规定执行)送交论文的复印件和电子版本，允许论文被查阅和借阅，同意学校将本论文的全部或部分内容编入学校认可的国家相关数据库进行检索和对外服务。论文作者签名： 鬃窘指导教师签名： 互丝坌万方数据摘要在过去几十年中，随着互联网技术的高速发展，在线网络数据规模呈

4、现爆发式的增长，在大规模网络数据的驱动下，复杂网络研究越来越得到广泛重视。其中社区发现能帮助挖掘复杂网络中的社区结构，对于深入理解复杂网络的特性和功能具有重要的理论意义和广泛的应用前景，逐步成为了复杂网络分析中的重点研究方向。社区发现方法分为非重叠社区发现和重叠社区发现，而现实复杂网络所呈现出来的社区结构通常是可重叠的，因此重叠社区发现更符合现实要求。目前，基于标签传播的社区发现算法因其操作简单和执行高效的优点而在社区发现领域里被深入研究和广泛应用。其中COPRA(Community OverlapPRopagation Algorithm)算法扩展了传统的标签传播算法(Label Propa

5、gationAlgorithmLPA)，能从网络中有效挖掘重叠社区结构，但该算法同时保留了L王，A算法随机性强、鲁棒性差、容易把所有顶点分配给一个社区等缺点。为了提高算法准确度和鲁棒性，本文提出一种基于LeaderRank的多标签传播重叠社区发现算法。该算法通过LeaderRank算法来量化网络中节点的重要性，然后根据量化值大小对这些节点进行团扩展，得到可重叠的最具重要性的粗糙团，作为标签传播的初始社区核心，并将节点重要性融入标签初始化和标签更新过程中，最终提高了社区划分结果的准确性。通过在人工网络图以及真实网络数据集上进行实验分析，结果表明所提算法不仅有效地增强了社区发现结果的稳定性，同时提

6、高了准确率。关键词：复杂网络；重叠社区发现；标签传播；LeaderRank万方数据AbstractOver the past few decades，with the rapid development of Internet technology,thescale of online network data is explodingUnder the drive of largescale network data，more and more attention has been paid to the research of complex networkIn theseresearch

7、es，community detection，which can discover the structure of communities inthe complex network，and Can help researchers understand the characteristics andfunctions of complex network more deeply,and has important theoretical significanceand wide application prospect，has gradually become the focus of r

8、esearch in complexnetwork analysisCommunity detection is divided into nonoverlapping communitydetection and overlapping community detectionCommunity structure presented byrealistic complex network is usually overlapping，SO overlapping community detectionis more realistieAt present，owing to the advan

9、tages of simple and rapid in community detection，the community detection algorithm based on label propagation is widely used andstudiedAmong them，COPRA(Community Overlap PRopagation Algorithm)，as anextension of LPA(Label Propagation Algorithm)，can effectively detect overlappingcommunities from the c

10、omplex network，but it also retains the shortcomings of LPA，such as strong randomness，poor robustness，and easily assigning all vertices to acommunityIn order to improve accuracy and robustness of COPRA，a multilabelpropagation algorithm for overlapping community detection was proposedIt usedLeaderRank

11、 algorithm to quantify the influence and importance of nodes in socialnetwork,then extended these nodes to maximal cliques as initial community cores forlabel propagation according to LeaderRank score，and introduced the importance ofnodes into the label initialization and label updating process，whic

12、h ultimatelyimproved the accuracy of the results of community divisionExperiments on LFR benchmark networks and real public datasets show that theproposed algorithm not only improves the stability effectively,but also increases theII万方数据accuracy for detecting overlapping communitiesKeywords：complex

13、network；overlapping community detection；label propagation；LeaderRankIlI万方数据目 录摘 要IAbstractII第1章绪论l11课题研究的背景和意义112研究现状213本文的主要工作414论文的结构安排5第2章相关理论综述621复杂网络概述622节点的重要性测度823社区结构评价指标11231模块度l l232标准化互信息1424非重叠社区发现算法14241基于划分的社区发现方法14242基于模块度优化的社区发现方法15243基于标签传播的社区发现方法1625重叠社区发现算法18251基于团渗透的重叠社区发现方法18252

14、基于节点分裂的重叠社区发现方法19253基于标签传播的重叠社区发现方法2026本章小结一21第3章基于LeaderRank的多标签传播重叠社区发现算法2231算法思路与框架2232节点重要性计算。2333粗糙团生成24TV万方数据34标签初始化2635标签传播阶段27351标签传播顺序27352标签更新策略27353标签传播终止条件2836 LRMLPA算法描述与分析2937本章小结3l第4章实验及结果分析3241实验数据32411人工网络图324。12真实数据集3342实验结果与分析33421人工网络图实验33422真实数据集实验36413本章小结37第5章总结和展望一3851总结。3852

15、展望。38致射40参考文献4l附录l攻读硕士学位期间发表的论文45附录2攻读硕士学位期间参加的科研项目46V万方数据武汉科技大学硕士学位论文第1章绪论11课题研究的背景和意义几乎所有的复杂系统都能抽象成复杂网络，通过网络建模进行研究【1，例如，万维网可以抽象成由网页和链接组成的网络；交通网络可以抽象成由站点和站点之间的交通路线构成的网络；生物网络可以抽象成由细胞或者蛋白质组成的网络等。随着复杂网络数据规模的增长及应用领域的扩展，复杂网络研究受到越来越多的学者的广泛关注。作为复杂网络的一个基本特征，社区结构(Community Structure)也受到研究者们的广泛关注和深入研究。在复杂网络中

16、普遍存在一些节点集合，这些集合内部的节点紧密连接，而与集合之外的节点连接较稀松，这种节点集合就是社区【21。例如，在社会网络中社区可以代表具有相同爱好的群体或朋友圈；在万维网中社区可以代表描述相同技术的网页集合；在学术网络中社区可以代表研究相同领域的学者等。社区发现就是找到网络中的这些社区结构的方法。社区发现具有重大的现实意义，例如在社交网站中，可以根据用户的关注和评论等信息对用户进行社区划分，为社区中的用户做定向信息推荐，提升网站对用户的吸引力；在视频网站中，可以根据用户观看记录对用户进行社区划分，以社区为单位进行视频推荐或者广告投放，以此营造更高的利润；在电子商务网站中，可以根据用户浏览记

17、录和购买记录等信息对用户进行社区划分，为社区中的用户进行准确的商品推荐，提高用户体验等等。在初期的社区发现研究中，大多数的社区发现方法都认为社区之间是不重叠的，但是深入研究后发现现实世界网络中社区之间相互重叠的现象非常常见，例如，在学术网络中，一个研究员按研究方向可以横跨多个的研究领域；在问答网站中，一个用户可以根据兴趣和能力参与不同话题的讨论；在社交网络中，一个用户按兴趣爱好可以有多个社交圈子等等。另一方面，现实中的社会网络，如Facebook、微博等，它们数据规模庞大，节点关系复杂，得到的网络结构混合多样并且未知。因此，面对规模日益庞大、复杂性日益提高的网络数据，如何准确有效地挖掘出网络中

18、存在的重叠社区结构是一个极具挑战性的课题，并在许多方面仍然具有较大的发展和提升空间。万方数据武汉科技大学硕士学位论文12研究现状复杂网络中的社区发现具有重大的理论和现实意义，吸引了越来越多的学者的关注。近年来，随着社区发现方法的不断演进，研究者们提出了各种方法来发现网络中的社区结构，这些方法主要分为两大类，一类是非重叠社区发现方法，发现的社区之间相互独立，另一类是重叠社区发现方法，发现的社区之间相互可交叉。图分割和聚类思想是大多数社区发现方法的基础。早期的谱方法(spectralmethod)【3】和KernighanLin算法41就是图分割方法中的两类典型算法，这些算法在面对当今的大规模网络

19、已经不合时宜了，但是它们为后来者奠定了良好的研究基础。2002年，Girvan和Newman)发现网络_中普遍存在的社区结构，由此提出了社区发现的概念，并提出了著名的社区发现算法一一GN算法5】。不过GN算法具有计算量太高的缺陷，无法应用于大规模网络上，但它吸引了学者对这个问题的进一步研究，从而激发了复杂网络社区发现的研究热潮。2003年，Tyler等人将蒙特卡罗方法(Monte Carlo Method)弓入到GN算法中，提出了一种效率更高的算法【们，但牺牲了社区发现的准确度，因为算法不再计算出所有边的精确边介数，而是估算出的近似边介数。2004年，Radicchi等人以局部指标边聚集系数来

20、取代GN算法中的全局指标边介数，提出了一种新的算法【7】，有效降低了算法复杂度，但也缩小了算法的适用范围。2004年，Newman将GN算法扩展到了加权复杂网络中【81。2004年，Newman和Girvan提出了一种评价社区优劣的量化指标一一模块度函数Q91。Q函数清晰地表示出了网络中的社区结构特征，并成功地应用到实际场景中，极大地推动了社区发现的发展。2004年，Newman提出了第一个基于模块度优化的社区发现方法一Newman快速算法(Fast Newman，VN)t10】。该算法通过贪婪法不断凝聚合并社区使得模块度不断增大，然后选择对应模块度最大的社区划分作为最终结果，算法的复杂度是D

21、(沏切)，2)，在稀疏网络图上复杂度可以进一步降低，接近O(n2)，相比GN算法有较大的提升。之后基于FN算法，Clauset、Newman与Moore提出了CNM算法【】，算法使用大顶堆优化了模块度函数Q的计算，使得算法拥有接近线性的复杂度O(nl092玎)，。此后不断有新的基于模块度优化的算法被提出来，但近年来研究者发现，这类算法存在分辨率极限(Resolution Limit)12】的问题，这说明p函数本身是有缺陷的。另一方面，在实际分析中很难确定一种合理的优化目标，使万方数据武汉科技大学硕士学位论文得划分出来的社区结构难以反应真实的社区结构，因此这类算法的理论基础有待于进一步研究。20

22、07年，Raghavan等人提出了标签传播算法LPA(Label PropagationAlgofithm)13】，算法不需要输入参数，且具有线性时间复杂度，可应用于较大规模的复杂网络，但是该算法更新节点标签时使用了随机选择方式，降低了算法稳定性。2009年，Leung等人针对LPA算法容易形成怪兽社区的问题，提出了随着传播而衰减的标签传播算法【14，有效的提高了LPA算法的稳定性，并降低了计算开销。Barber等人为了防止u，A算法将所有节点划分为一个社区，提出了一种新的标签传播算法LPAmt”】，将社区发现问题等价于目标函数最优解的问题。2010年，Liu等人发现LPAm算法在求解过程中容

23、易陷入局部极大值，使划分出的社区结果不准确，提出将多步贪婪凝聚算法MSG引入LPAm算法中，设计了新的标签传播算法LPAm+116】，比较有效地避免了陷入局部极大值的问题。此外最近几年还有很多学者通过不同的方式对LPA算法进行了改进。2014年，Xing等人结合k-shell17提出NIBLPA算法【18】，通过节点的k-shell值和度计算节点的影响力，以此消除标签选择过程的随机性，增强了算法的稳定性。而He等人通过PageRank算法【19】量化节点的重要性，提出LPAp算法【201。2015年，石梦雨等人鉴于PageRank本身具有节点排序不唯一的缺点，提出结合LeaderRank2l】

24、的LRLPA算法221，进一步提升了算法的稳定性和准确度。2016年，宋琛等人引入随机游走思想提出RWLPA算法(23，通过随机游走计算出节点问相似度的矩阵，在标签选择过程中选择相似度高的节点标签，消除了标签选择的随机性，增强了算法的稳定性。以上介绍的几种社区发现方法都只能发现非重叠社区，在这些算法中每个节点有且只有一个社区，而现实世界的复杂网络中的社区之间不可能完全分离，经常存在重叠部分。因此，重叠社区发现更符合现实世界的社区规律，成为了近几年社区发现领域的研究热点。2005年，Palla等人提出了团渗透算法CPM(Clique Percolation Method)241，发现了网络中存在

25、的重叠社区，从此激发了重叠社区发现的研究热潮。基于此，Adamcsek和Gergely Palla等人编写了重叠社区发现软件CFinder251。CPM算法需要以k-clique(节点数为k的完全子图)为基本单位来发现重叠节点，这严格限制了算法的适用范围，并且算法难以选择合适的参数k来适用于不同的网络，但算法的思路激发了学者们的创新灵感。2009年，沈华伟等人以极大团为最小单位，设计了EAGLE算法261，并提出了一种重叠模块度函数EQ用于评价重叠社区结构的质量。2010年，Lee等人提出了GCE算法【271，通过对极大k-clique根据一万方数据武汉科技大学硕士学位论文定指标进行贪婪扩展，

26、以此生成重叠程度很高的社区结构，但在面对大规模稠密网络时性能不佳。2007年，Steve提出了重叠社区发现算法CONGAz8】，通过将网络中满足条件的节点分裂成多个副本节点，以此构造出新的网络，然后以GN算法划分出新网络中的社区，最后将划分的社区中的副本节点还原成原始节点。CONGA算法的复杂度为O(m3)。2008年，Steve为了提高CONGA算法的效率，将中介度简化为局部中介度，提出了一种改进算法CONGOt29】，降低了算法在稀疏网络上的复杂度O(nlog，z)，但在大规模真实网络中局限较大。2010年，Steve等人把标签传播思想应用到重叠社区发现上，提出了一种基于多标签传播的重叠社

27、区发现算法COPRA301。该算法保留了标签传播算法的高效性，同时也遗传了标签传播算法的随机性，导致社区发现结果极不稳定，并且算法难以选择合适的初始参数适用于结构复杂的网络，从而无法保证划分的社区结果质量。2011年，Xie等人基于标签传播算法提出了SLPA算法【3l】，算法有较好的时间复杂度，而且适用于非重叠社区发现，但难以选择合适的阈值参数且需要人为干预迭代次数。2012年，Wu等人在COPRA算法的基础上，提出了基于均衡多标签传播的重叠社区发现算法BMLPA32】，提升了算法的稳定性和收敛速度。虽然近些年来越来越多的学者投身到社区发现领域，并提出了各种各样的算法，但仍未形成统一的评价标准

28、来评估社区发现算法的优劣，并且对于大规模网络的高效准确的社区发现仍然需要深入研究，尤其是重叠社区发现，尚存许多问题丞待解决。13本文的主要工作本文在详细分析了多标签传播重叠社区发现算法COPRA，针对算法的差鲁棒性的问题，提出一种基于LeaderRank的多标签传播重叠社区发现算法(LeaderRank MultiLabel Propagation Algorithm，LRMLPA)。该算法通过LeaderRank算法来量化网络中节点的重要性，然后根据量化值大小提取出网络中可重叠的最具重要性的粗糙团，以此作为标签传播的初始社区核心，在标签初始化过程中将节点重要性融入到标签从属系数的计算里，使节

29、点的初始化标签集合更加准确，并设定合理的标签传播顺序更新标签，在更新节点标签时考虑邻居节点的重要性和本身的重要性的差异，使标签更新更为合理，最终提高了社区划分结果的准确性。在人工网络图和真实数据集上进行实验分析，验证了本文算法有效地提升了社区划分结果的稳定性和准确度。4万方数据武汉科技大学硕士学位论文14论文的结构安排本文由五个部分组成，各个部分的组织结构和相关内容如下：第一章为绪论，主要介绍了社区发现的相关研究背景、应用领域及研究意义，同时介绍了当前国内外相关领域的研究现状以及本论文的主要工作。第二章为相关理论的综述，主要介绍了复杂网络的基本理论以及网络中节点的重量性衡量方法，同时介绍了社区

30、发现的评价指标，详细介绍了非重叠社区发现和重叠社区发现方法中的几个经典算法。第三章为本文提出的基于LeaderRank的多标签传播重叠社区发现算法，主要介绍了算法的整体框架和流程，详细描述了部分关键步骤及其伪代码，并对算法做了简要分析。第四章为实验与分析，通过在人工网络图和真实数据集上进行实验，验证算法的稳定性和准确度。第五章为总结与展望，主要对本文内容和相关工作做简要的总结，并对以后可以深入研究和改进的工作进行展望。万方数据武汉科技大学硕士学位论文第2章相关理论综述在本章节中，我们将介绍复杂网络的基本理论以及网络中节点的重量性衡量方法，同时介绍社区发现的评价指标，然后详细介绍一些经典的社区发

31、现算法。21复杂网络概述现实世界中存在很多的复杂系统，它们可以通过网络建模抽象成复杂网络进行研究。复杂网络通常表示为G(E日，其中，矿是网络中的所有节点的集合，层是网络中所有边的集合H。复杂网络的规模一般都是非常巨大的，通常包含数百万的的节点和边。研究发现，这些大规模网络拥有一些相同的特性，而且随着网络规模的减小，这些特性越来越不明显。这些共同的特性具体如下：(1)小世界现象(Small World Efiect)网络中的大部分节点之间并不相连，但绝大部分节点经过少数几条边就可相互访问，即网络具有较短的平均最短路径长度和高的聚集系数，这就是网络的小世界现象331。(2)无尺度特生(scalef

32、ree)网络的无尺度特性34】主要体现为网络中的大部分节点拥有较小的度，而同时少数一些节点拥有极大的度，并且整体上节点的度数满足幂率分布。图21是包含1138499个节点的YouTube网络的节点分布图，可以看出大部分节点拥有很低的度，而少数节点拥有非常高的度。万方数据武汉科技大学硕士学位论文漆弘节点度图21 YouTube网络的节点分布(对数坐标)(3)网络社区结构特性科学家发现，复杂网络中存在一些结构和功能相似的节点集合，这些集合内部的节点之问连接相对来说十分紧密，而与集合外的节点之间的连接相对稀疏，这些节点集合被称为社区(community)，中文有时也译作社团或者社群，而发现网络中社区

33、结构的过程被称为社区发现51。现实世界中存在各种各样的社区结构，例如微信朋友圈、个人微博、论坛话题等等。而这些现实复杂网络中的社区之间通常是交叉的，存在着相互重叠的部分，这样的社区就是重叠社区。图22给出了一个重叠社区结构的示意图，一种颜色对应一个社区，拥有不同颜色的节点同时属于多个社区，这些节点就是重叠节点。万方数据武汉科技大学硕士学位论文22节点的重要性测度图22重叠社区结构示意图节点重要性可以衡量复杂网络中的节点，以此发现网络中处于中心地位的重要节点。节点重要性具有重大的理论研究意义和广泛的实际应用价值，越来越受到学者的广泛关注。中心性(centrality)分析就是一种评价节点重要性指

34、标的分析方法，中心性分析常用的几种经典方法有度中心性(degree centrality)、紧密度中心性(closeness centrality)、介数中心性(betweermess centrality)和特征向量中心性(eigenvector centrality)t35】-【381。(1)度中心性：一般来说，如果网络中一个节点与其他很多节点都直接相连，那么这个节点就是网络中的核心之一，也就是说如果一个节点的关系越广，相邻节点越多，那么这个节点也就越重要，因此，节点的度数中心性为该节点的度。当需要比较不同网络中的节点的重要性时，可对度中心性的值进行标准化，表示为式(2一1)：万方数据武汉

35、科技大学硕士学位论文G(z)=碧 (21)其中，吠f)表示节点f的度，n表示网络中节点的数量。(2)紧密度中心性：网络中的中心节点应该与其他节点联系的更紧密，能更快地访问到其他节点。紧密度中心性就是用来衡量这种紧密程度的评价方法。如果一个节点到网络中各节点的距离都很短，那么这个节点的信息传播就不会受限于其他节点。紧密度中心性的定义如下：晰刍秘叫-1=赫 弘2，Cc(o 1击驴)j 2翥荔 Q-2)其中，烈t力表示节点f*Nj的最短路径长度。(3)介数中心性：在一个网络中，介数大的节点相当于一个枢纽，和它相连的节点想要到其他节点都得经过它。节点的介数中心性可用式(23)表示：G(z)_；善igj

36、k(i)J0表示更新标签时倾向于选择邻接节点中度较大的节点持有的标签，m3)；9：if J=null：1 0： continue；11：clique卜i,j；12：commNeigho)(31)(32)(33)当it=乐l时，迭代仍要继续，除非只剩下一个标签，因为在接下来的迭代过程中标签集合可能会继续减少，而且社区结构也有可能发生变化，从而达到更好的社区划分效果。同样，当每个社区包含的节点数不变时也不能停止迭代，因为节点数经常会随着迭代继续而变化。第t次迭代后的社区标签与其包含的节点数的集合表示如下：cf=(c，f)：c矿f=，。y，岛(。一，。1) (34)因此，最终的迭代终止条件设置为当C

37、t-I和Ct的最小映射与c，和Ct+l的最小映射相等时，迭代终止。第t次迭代后的最小标签映射表示如下：蜴：j(c，f)：3p39(c，p)cf一(c，g)g Ai=min(p，g)，ift=t一-(35)e，otherwise万方数据武汉科技大学硕士学位论文当mr=mf-l时，迭代终止。举个简单的例子，假设itq=珥6，c,d)，Ct-I=“1)】(6，2)，(c，3)，(厦4)，it=儡6，c,d，cr=，1)，(6，2)，(cj2)，(Z5)，it+1=口，b,c,d)，Ct+l=(口，1)，(色3l(cj2)，(Z4)，贝0 mt=1)，(扛2)J2)，(厦4)，mr+1=以1)，(6，

38、2)，(c，2)，(Z4)，mr=mt+l，故迭代终止，以第t次或第什1次迭代结果为社区划分结果。36 LRMLPA算法描述与分析LRMLPA算法的伪代码描述如表313所示。表33 LRMLPA主体算法Input：图G(V,E1，最大影响力粗糙团脚己RcOutput：社区节点集合communites1： oldLabelMap=InitLable0：2： newLabelMap_乃：3： rcNode 4-a：4： foreach RC了i11上厌尺C：5： rcNodeo：5： b卜newLabelMapv。耐(0+施；6： newLabelMapvput(c,b)；7： inf-label

39、lnfget(c)+u上R；8：labellnfput(c,现厂)；9： else：10： newLabelMapvput(c,bu)；1 1：labeIInfput(e,uLR)；12：foreach(c，彤)in labellnf：13： ifnfk：2l： k 4-b；22：6黼h+P；23：foreach(c,b)in newLabelMapv：24： if bb：25： newLabelMapvremove(c)；26：normalize(newLabelMapv)；从上一次的节点标签一从属系数映射集合oldLabelMap中取出节点y的邻接节点U对应的所有标签从属系数集合，根据公式

40、(31)计算出标签c的影响力并与节点v的LR值对比进行标签过滤，再对过滤后的标签根据公式(32)计算节点v拥有的标签C的系数，然后删除系数低于阈值的标签，归一化保留下来的标签的系数，最后得到此次迭代后节点v的标签从属系数映射。算法的时间复杂度分析如下：万方数据武汉科技大学硕士学位论文在一个具有m条边，n个节点的复杂网络中，节点平均所属社区的数目记为Vavg，节点的平均度数记为比增。算法首先通过LeaderRank算法计算网络中所有节点的重要性需要O(mtl)，其中tl为LeaderRank算法的迭代次数。在粗糙团生成阶段，按照节点重要性排序需要O(nlog，z)，找出所有粗糙团需要D(粕彬)，

41、故初始化部分的总时间复杂度为O(n(109刀+，妊曲)。在标签传播阶段，每次标签迭代需要O(va，gmlog(vavgmln)。对划分的社区结果去重和分裂需要D(玎)。故算法的总时间复杂度为O(mtl+n(109 n+va弘增+Vav93)+f2妒zlog(彬胁)，其中t2为标签迭代次数。在大规模稀疏网络中Yavg一般很小，因此算法的复杂度可以降低到O(mtl+nlog，z)。37本章小结本章介绍了一种新的多标签传播重叠社区发现方法LRMLPA，算法首先通过LeaderRank算法对网络中的节点进行重要性计算，再根据重要性大小进行团扩展生成若干粗糙团，对生成的粗糙团集合中的节点和非粗糙团中的孤

42、立节点进行标签初始化，然后通过合理的标签迭代顺序和改进的标签删选策略进行标签更新，直到达到迭代收敛条件，将所有拥有相同标签的节点划分成一个社区，去除重合的社区，分裂内部不连通的社区，得到最终的重叠社区划分结果。万方数据武汉科技大学硕士学位论文第4章实验及结果分析实验分别在人工网络图和真实数据集上对比了COPRA算法、BMLPA算法和本文提出的LRMLPA算法。考虑到对比的三种算法都是基于标签传播的算法，划分出的社区可能不稳定，因此取10次运行结果的平均值作为实验结果。实验中COPRA算法的系数v设为4，BMLPA算法和LRMLPA算法的平衡系数P均设为O75。41实验数据411人工网络图200

43、8年，Lancichinetti等人设计了一神用于生成人工网络图的测试程序LFRbenchmarkt451，被广泛用于检测社区发现算法的性能。该程序可以根据用户指定的参数生成对应的接近真实网络情况的人工网络，不仅适合用来检验非重叠社区发现算法，也很适合用来检验重叠社区发现算法。因此，本文使用LFR基准程序生成了四种不同结构的人工网络，用来检验本文提出的LRMLPA算法。网络的平均度数反映出边的稀疏程度，网络的平均度数越低，它的边越稀疏；社区规模通过每个社区包含的节点数量反映，每个社区包含的节点越多，社区规模越大。据此生成了四种人工网络图：小规模社区稀疏网络图SS；大规模社区稀疏网络图SL；小规

44、模社区的稠密网络图DS；大规模社区的稠密网络图DL。这四种人工网络的各个参数如表41所示，其中，表示网络中节点的数量；k表示网络中节点的平均度数；maxk表示网络中节点的最大度数；fJ表示网络中度数的指数分布；力表示网络中社区规模的指数分布；mine表示网络中一个社区包含的最小的节点数量；maxc表示网络中一个社区的包含的最大的节点数量；on表示网络中重叠节点的数量；on表示网络中重叠节点所属的社区数量；mu(mixingparameter)是混合参数，mu值越大，社区之问的界限就越模糊，发现社区的难度就越大45】。mu取值从01到08，每次增加01。万方数据武汉科技大学硕士学位论文表41两种人工网络图的参数设置412真实数据集本文选取了三种常用的小规模真实数据集，分别是Karate461、Dolphins471、Football5】，以及一种较大规模的真实数据集Intemet481。这些数据集的具体参数如表42所示。表42数据集基本信息42实验结果与分析通过实验发现COPRA算法对同一数据集多次运行得到的社区划分结果各不相同，说明COPRA算法划分出的社区结果很不稳定，而BMLPA算法和本