基于局部影响力的通信网络社团检测方法常振超，陈鸿昶，刘阳，黄瑞阳（国家数字交换系统工程技术研究中心，郑州450002）摘要：发现复杂网络中的社在社会网络，生物组织网络和在线计算机网络等具备十分重要的意义，由于这些网络呈现出规模大的特点，基于全局结构的社团检测方法往往不能够适用，而从局部信息角度出发存在诸多问题，如对节点初始位置敏感、拓扑信息难以有效利用和社团扩展方向无法有效控制等问题。本文聚焦于研究局部社团方法，首先，借助于一种半局部的节点中心性衡量指标，找到与给定节点邻近的最具影响力的节点集合，这些节点在网络中具备较快的信息传播能力；然后，从这些具备较大影响力的节点集合发去检测局部社团结构。对真实网络和计算机生成网络的实验表明，本文所提的方法具有更高的识别性能，且由于其算法复杂度较低，能够很好的适用于大规模网络处理。关键词：通信网络；社团检测；局部信息；影响力节点中图分类号：TP391CommunitydetectionbasedonlocalinfluentialnodesincommunicationnetworksChangZhen-chao,ChenHong-chang,LiuYang,HuangRui-yang(NationalDigitalSwitchingSystemEngineering&TechnologicalResearchCenter,Zhengzhou450002,China)Abstract:Detectingcommunitiesisofgreatimportanceincomputersciencebiologyandsociologynetworks.Therehavebeenlotsofmethodstodetectcommunity.Methodsusingglobalinformationareunsuitabletodetectthecommunitiesinlarge-scalenetworksasthestructureofthewholenetworkcannotbedetected.Recently,communitydetectionbasedonlocalinformationhasattractedmanyresearchers’attention.Buttraditionallocalcommunitydetectionmethodshaveanumberoflimits,suchasthedetectionresultsaresensitivetothepositionofsourcenode.Inthispaperweproposedacommunitydetectionalgorithmbasedonlocalinfluentialnodes.Firstly,asetofinfluentialnodesbasedonsemi-localcentralitymeasureisconstructedwhichhasafasterspreadingspeedofinformation.Then,weapplytheseinfluentialnodesinsteadoftheoriginalsourcenodeforlocalcommunitydetection.Communitydetectionfromthelocalinfluentialnodeswhichhaveahigherspreadingratethanrandomnodescanbemoreaccurateandstable.ExperimentalresultsonbothLFRbenchmarknetworksandrealnetworksshowthatourmethodcanwelldetectlocalcommunity.Asthecomputationalcomplexityisverylow,ourmethodiseffectivetoexplorelocalcommunitystructureoflarge-scalenetworks.Keywords：Communicationnetworks;Communitydetection;Localinformation;influentialnodes基金:国家重点基础研究发展计划（批准号：2012CB315901，2012CB315905）和国家自然科学基金(批准号：61171108)资助的课题．†通讯作者.E-mail:changzc2012@126.com电话：037181632795一、引言通信网络在我们生活中随处可见，例如在线社交网络、电子邮件网和WWW网等[1]。这些网络通常具备多种节点和边，具备较高的复杂特性，因此，人们称之为复杂通信网络研究复杂通信网络最重要的任务之一是去识别网络中的社团结构[1-2]。现代网络科学给我们理解复杂网络带来了非常显著的便利，从生物工程到社会科学，检测和分析网络中的社团结构具备十分重要的意义。社团是有组织的非常有意义的单元构成，社团结构指的是同一个社团内部连边多余不同的社团之间的连边个数。目前，已经有很多种社团检测的方法提出来，一些是基于全局信息的，另一些是从局部角度出发的[3]。基于全局信息出发角度，首先通过某种定义将整个网络视为一张图，进而分析整个图的全局信息，其在一些规模比较小的网络取得了较好的效果[4-6]。但是，由于其计算复杂度较高，很难适用于当前规模比较大和局部信息残缺的网络。例如，Facebook和twitter包含了上亿个节点，web网络包含了数十亿个网页和超链接，在这些规模巨大的复杂网路中检测社团将会非常耗时[7]。因此，基于全局的算法难以适应规模大且结构动态变化的社团结构。近些年，局部社团的研究由于能够克服全局方法的...