社团检测方法4

基于局部影响力的通信网络社团检测方法常振超，陈鸿昶，刘阳，黄瑞阳（国家数字交换系统工程技术研究中心，郑州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:[e-mail]电话：[phone]一、引言通信网络在我们生活中随处可见，例如在线社交网络、电子邮件网和网等[1]。这些网络通常具备多种节点和边，具备较高的复杂特性，因此，人们称之为复杂通信网络。研究复杂通信网络最重要的任务之一是去识别网络中的社团结构[1-2]。现代网络科学给我们理解复杂网络带来了非常显著的便利，从生物工程到社会科学，检测和分析网络中的社团结构具备十分重要的意义。社团是有组织的非常有意义的单元构成，社团结构指的是同一个社团内部连边多余不同的社团之间的连边个数。目前，已经有很多种社团检测的方法提出来，一些是基于全局信息的，另一些是从局部角度出发的[3]。基于全局信息出发角度，首先通过某种定义将整个网络视为一张图，进而分析整个图的全局信息，其在一些规模比较小的网络取得了较好的效果[4-6]。但是，由于其计算复杂度较高，很难适用于当前规模比较大和局部信息残缺的网络。例如，Facebook和twitter包含了上亿个节点，web网络包含了数十亿个网页和超链接，在这些规模巨大的复杂网路中检测社团将会非常耗时[7]。因此，基于全局的算法难以适应规模大且结构动态变化的社团结构。近些年，局部社团的研究由于能够克服全局方法的限制，引起了研究者的广泛关注。与全局方法不同，局部社团检测聚焦于研究子图结构，从节点的邻居信息出发，检测包含该节点的社团结构，而不考虑整个图中其余节点的归属。局部社团检测并不需要提前预知整个网络的全局信息，该方法从一个节点出发，逐渐获取当前社团的局部信息，已经有大量的局部社团检测算法提出来[8-23]。然而，局部社团检测结果对于节点的位置敏感，如果初始节点位于社区的核心位置（具备较高的影响力），那么社团检测的结果将会更好于初始节点位于边界位置（具备较低的影响力）的节点。尽管在局部网络研究中已经取得了很多成果，但是由于其算法要求的特殊性，有效性的鲁棒算法仍然需要继续研究。本文聚焦于局部社团的研究，从节点聚类出发，提出了一种两阶段的基于局部节点影响力的社团检测算法IN-LCD(Communitydetectionbasedonlocalinfluentialnodesincomplexnetworks)。该方法由影响力节点识别和社团节点聚合优化两阶段组成。首先，从给定的节点出发，寻找该节点邻近节点中最具影响力的节点，构造最具影响力的候选节点集合。然后，基于构造的节点集合，采用节点连接相似度进行聚类的局部社区发现方法，去检测整个社团。该方法有效的克服了局部信息角度下社团对初始节点敏感的问题，从最具影响力的节点出发，能够较快且准确的覆盖整个局部社团的社区结构，与传统的方法相比，具有更高的稳定性和准确性。本文剩下的章节组织结构如下：第二部分回顾了局部社团发现的相关工作，并分析了现有方法发现的问题，接着第三部分描述了本文所提出方法，第四部分在实验中验证了本文所提方法的有效性。第五部分给出了算法总结。二、局部信息下社团检测局部信息下社团检测问题指的是仅仅检测网络中给定节点所率属的社团，也成局部社团检测。复杂网络的节点将会被分为两个部分，节点归属于包含原始节点的局部社团和网络中剩下的节点。局部社团检测并不需要提前预知社团的整体信息。对于局部社区发现来说，由于只有网络的局部信息，因此，许多全局社区评价指标(如模块度等)不再适用，适用于局部网络的社区评价指标也被提出来。下面将回顾了网络中一些非常有效的局部社团检测方法。2.1相关工作Bagrow等人首先提出了一种检测局部社团的方法[9]，该方法从一个源节点出发，不断添加连续的外壳上的顶点。这些“外壳”定义为距离源节点固定测地线距离范围内的节点。算法的性能取决于初始节点位置，当节点处于社团的边界位置时，那么其算法效果将不会很好。在同一年，Clauset提出了一种基于测度的局部社团检测方法[10]。一个局部社团B包含一个边界C的R测度如下式子所示(,)ijijijijBijIRTB(1)式中当给定的节点分别位于B和C中，(,)ij的取值为1，其他情况下取值为0。T是端点之一在B内部的边个数，I是端点全部在B中的边的个数。根据这个定义，局部社团检测用过最大化R的贪婪算法来实现。它通过迭代搜索找到具有最大R值增益的邻接节点，将其添加到局部社团中来，直至局部社区达到预先设定的规模。与Clauset方法相似，Luo等定义了局部模块度M，并基于此指标提出了相应的局部社区发现算法[11]，(,)()()(,)ijijijijSijindSMoutdSSij(2)其中outE表示社区边界与外部节点的连接数，inE表示社区内部的连接数之和。为使M值最大，该算法以式2为目标函数搜索满足聚类条件的邻接节点，从而得到局部社区划分。Lancichinetti等人[12]提出了适应度函数（Fitnessfunction）以度量社区内部和外部的连接密度差异()CincCCinexkfkk(3)其中表示控制局部社区规模的参数，Cink表示局部社区C内部所有节点的度数之和，Cexk表示社区C内部与外部的度数之和。需要注意的是，Cink是社区C中内部连接数的两倍。该算法随机选取初始节点，然后围绕初始节点以适应度函数为标准进行局部社区聚类。当所有邻接节点的适应度值为负时，社区发现停止。该算法简单易行，但初始节点的随机选取往往社区发现的不稳定，而适应度指标的相关参数也需要预先确定。Raghavan提出了一种基于标签传播的社团检测方法(LPA,LabelPropagationAlgorithm)[13]。该方法从信息传播的角度出发，每个节点首先被初始化为一系列节点，在每个重复的处理过程中，每个节点将采用他的邻居节点中数目最多的标号进行标记，最终每个节点都会拥有一个独立的标签，拥有相同标签的节点将会归属于同一个社团。标签传播方法具备很低的算法复杂度，一些改进的标签传播方法也被提出来[14-16]。这些改进的方法主要是改进了更新顺序和节点选择方面，已经取得了一些较好的性能。Chen等人提出了一种基于局部度中心的社团检测方法[17]。该方法定义了局部度中心节点，这些节点的度数大于其邻居节点，围绕这些节点去发现整个局部社团准确度更高。首先，从给定节点出发寻找度中心节点，然后从这些节点出发去扩张整个社团。在其文章中，分别比较了所提方法与R、M和F测度的方法，其方法能够达到最佳的识别性能。2.2问题分析尽管当前已经有多种局部社团发现方法提出来，但是对于这个方向的研究仍然有很多问题尚待解决。基于R、M和F模块度的方法敏感于初始节点的位置，当初始节点位置位于边界时候，其发现效果往往不是很好。LPA方法在更新节点时，对每个标签相同处理，忽略了节点的亲密程度，另外，LPA每次迭代都通过直接紧邻来操作，将会导致其他跳的拓扑信息的缺失。LMD能够有效的避免社区发现结果对于节点位置的敏感度，该方法从局部度中心节点替代源节点出发去发现局部社团，但仍然存在相关的问题：首先，局部度中心节点仅仅考虑了最近邻信息，而没有考虑次近邻信息和更远的拓扑信息；然后，局部度中心节点的重要性无法进行排序，这就导致了获取到得局部度中心节点集合的尺寸无法控制；同时，由于算法对位于核心节点集合中的节点子团同时进行扩展，社团扩展的方向没有进行确定。总之，现有算法大多存在以下三个缺陷：1)算法对起始节点的位置敏感，当节点位于社团的边缘部分时，对于社团的发现精度不够；2)难以有效利用拓扑