面向大规模应用层拓扑社团发现技术

《面向大规模应用层拓扑社团发现技术》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、面向大规模应用层拓扑社团发现技术　　收稿日期：2013-05-09基金项目：国家重点基础研究发展计划（973）（2011CB302605）；国家高技术研究发展计划（863）（2011AA010705，2012AA012506）；国家自然科学基金（61173145，61202457）。作者简介：黄振（1989-），男，江西抚州人，硕士研究生，主要研究方向：复杂网络、DNS行为分析；张宇（1979-），男，河北乐亭人，博士，讲师，主要研究方向：网络拓扑、BGP、复杂网络等；张宏莉（1973-），女，吉林榆树人，博士，教授，博士生导师，主要研究方向：网络与信息安全、网络测量、并行计算等。面向大

2、规模应用层拓扑的社团发现技术黄振，张宇，张宏莉（哈尔滨工业大学计算机科学与技术学院，哈尔滨15150001）摘要：社团发现是复杂网络研究领域里一个极具挑战性的方向。特别地，对于现实世界中许多规模巨大的应用层拓扑，一些社团发现算法因为计算复杂度过高而不适用。另一些社团发现算法的实际性能还有待评估。为此，提出了可用于衡量社团发现算法实际应用价值的三个指标：（1）可扩展性，衡量算法能处理的应用层拓扑的规模；（2）准确度，衡量社团划分结果好坏；（3）敏感度，衡量社团划分结果的一致程度。在7个大规模的现实世界应用层拓扑图上，对三个针对大规模网络的社团发现算法（CNM算法、Wakita算法和Louv

3、ain算法）进行了比较分析。实验结果表明，Louvain算法在可扩展性上最优且所得划分结果准确度最高，CNM算法在敏感度上表现最好。关键词：社团结构；社团发现；社交网络；复杂网络；大规模网络中图分类号：TP393文献标识码：A文章编号：2095-2163（2013）04-0034-05CommunityDetectionforLarge-scaleApplication-layerTopologiesHUANGZhen，ZHANGYu，ZHANGHongli（SchoolofComputerScienceandTechnology，HarbinInstituteofTechnology，

4、Harbin150001，China）Abstract：Communitydetectionisaverychallengingresearchdirectioninthefieldofcomplexnetworks’research.Inparticular，asthelargescaleofrealworld’sapplicationlayertopology，somecommunitydetectionalgorithmsarenotapplicablebecauseofhighcomputationalcomplexity.Andsomealgorithms’15actualpe

5、rformanceremainstobeevaluated.Therefore，thepaperproposesthreeindicatorsthatcanbeusedtomeasurecommunitydetectionalgorithms’actualapplicationvalue：（1）extensibility，usedtomeasurethescaleofapplicationlayertopologythatcanbedealtwith；（2）accuracy，usedtomeasurethepartitionresultisgoodorbad；（3）sensitivity

6、，usedtomeasurethepartitionresult’sconsistent.Thepaperusessevenlarge-scaleapplicationlayertopologiestoanalyzethreecommunitydetectionalgorithmsforlarge-scalenetwork，i.e.CNMalgorithm，WakitaalgorithmandLouvainalgorithm.TheresultsshowthatLouvainalgorithmperformsbestonscalabilityandaccuracy，andCNMalgor

7、ithm’sperformanceonsensitivityisbest.Keywords：CommunityStructure；CommunityDetection；SocialNetworks；ComplexNetworks；MassiveNetworks0引言15随着复杂网络研究的深入进行，人们发现现实世界网络中普遍存在社团结构。社团结构是指网络可根据其自身的拓扑结构被划分为若干个社团；同一社团内的节点连接紧密，而不同社团间的