复杂网络的重叠社区及社区间的结构洞识别
teg刘世超;朱福喜;冯曦
【摘 要】边缘构件大数据环境下如何有效地、准确地识别复杂网络的重叠社区是近年来学者关注的重点。本文提出一种基于多标签传播方式MLPS（Multiple Label Propagation Strategy）的重叠社区识别算法，该算法首先利用影响力最大化模型选取初始种子集合并赋予它们唯一的标签，然后采用结点间的相似性和影响传播特性共同作用于标签的传播迭代过程，迭代停止后将具有相同标签的结点划分为同一社区。通过合成网络和真实网络的实验验证了MLPS算法具有较高的准确度和模块度，且具有接近线性的时间复杂度。另外，在对MLPS算法输出的重叠结构进行分析的基础上，本文提出社区间的结构洞识别算法SHCDA（Structural Holes Between Communities Detection Algorithm），该算法通过分析重叠结构和重叠结点的位置特征，计算重叠结点作为结构洞的得分，最后输出top-k结构洞。本文在不同特性的数据集上进行实验，结果证明了SHCDA算法具有最好的准确度。%Many rearchers focus on how to detect overlapping communities effectively and accurately when coping with large-scale networks in recent years.This paper propos a novel overlapping community detection alg
orithm bad on a multiple label propagation strategy,called MLPS algorithm.Firstly,MLPS lects a t of nodes as initial eds by using In-fluence Maximization Model,each of which is assigned a unique label;Inspired by strategy bad on similarity and influence diffusion,MLPS incorporates with the two strategies to guide the process of label propagation;Finally,nodes with the same tag are divided into one community after propagation.Experimental results on synthetic datats and real networks illustrate that MLPS has both high accuracy and modularity at the same time.In addition,another algorithm named Structural Holes between Communities Detection Algorithm (SHCDA)is prented on the basis of the output of MLPS.SHCDA computes the scores of overlapping nodes who rve as structural holes by analyzing the overlapping structure and position feature of overlapping nodes,and then lects top-k structural holes as the output.Experimental results on different datats show that SHCDA gets the best accuracy.
新党章
【期刊名称】注塑车间《电子学报》
【年(卷),期】2016(044)011
【总页数】7页(P2600-2606)
【关键词】复杂网络;重叠社区;多标签传播;结构洞识别
【作 者】刘世超;朱福喜;冯曦
【作者单位】武汉大学计算机学院，湖北武汉430072;武汉大学计算机学院，湖北武汉430072;武汉大学计算机学院，湖北武汉430072
【正文语种】中 文
【中图分类】TP391
现实世界的许多网络普遍体现了社区结构特性，即同一社区内的结点关系紧密，而不同社区间的结点关系稀疏[1].近年来针对社区发现的算法层出不穷，在社区的层次性和重叠性等方面开展了大量的研究[2～4].本文着重研究社区的重叠性，尤其是大数据环境下，如何有效地解决重叠社区挖掘的问题.社区重叠结点是社区间的桥梁即社区间的结构洞，社区间的结构洞是两个或多个社区之间的非重复关系，占据结构洞的个体拥有更多的机会获取信息
或资源[5].识别社区间结构洞的关键在于准确地挖掘网络的重叠结构，从而找出结构洞的候选集合，即社区重叠结点的集合.
一些学者针对结构洞的形成和作用进行建模研究[6,7]，而对结构洞的识别算法还比较少.文献[8]采用拓扑势的方式识别重叠社区和社区间的结构洞，但作者直接将重叠结点作为结构洞，没有定量地分析结构洞的重要性.在实际情况中，我们往往更加关心那些比较重要的结构洞，于是Tang J等[9]提出top-k结构洞挖掘的问题，作者认为结构洞的邻居结点在一定程度上反映该结构洞的重要性，但忽略了对重叠结构的分析.如图1(a)中的结构洞A与图1(b)的结构洞C拥有相同的结构，而图1(b)中的两个社区只存在一个结构洞C，定量计算时C的重要性应大于A.
本文的主要贡献：提出一种基于多标签传播方式(MLPS)的重叠社区挖掘算法，算法的输出结果拥有较高的准确度和模块度；分析社区重叠结构，提出社区间的结构洞识别算法(SHCDA)，能有效地挖掘top-k结构洞.
Raghavan等[10]提出的标签传播算法LPA(Label Propagation Algorithm)，首次将标签传播应用于社区发现，具有接近线性的时间复杂度.Barber等人[11,12]将标签传播算法转化为优
化问题，Xie J[13]结合了路径衰减的思想扩展了对结点邻居的计算，提高了社区划分结果的精度.COPRA(Community Overlap Propagation Algorithm)算法[14]是LPA算法的扩展，可以解决重叠社区挖掘的问题.初始化时每个结点被赋予一组标签对(c,b)，c是标签，b是结点拥有标签c的概率；在标签更新过程中设置阈值v，删除b小于v的标签对.文献[15]指出COPRA算法的阈值应根据结点所处的位置不同而变化，并通过平衡阈值的选择来提高生成社区的质量.SLPA(Speaker-listener Label Propagation Algorithm)[16]通过模拟人类交流的行为特性，定义了动态的交互规则来指导结点的标签更新.文献[17]提出了MLPA(Multi-label Propagation Algorithm)算法，该算法根据结点间的相似性来确定传播概率，具有较高的准确度，但是同COPRA算法一样，算法容易产生大量的社区，导致模块度较低.
良好的习惯3.1 算法主要思想
COPRA是经典的标签传播算法，在该算法的标签传播过程中，结点直接接受邻居结点的标签，本文定义这种标签传播的方式为DA(Directly Accept)，即
企业劳动合同模板其中,Pij表示标签ci从结点i传播到邻居结点j的概率，bi是结点i拥有标签ci的概率.这种直接接受标签的方式并不能真实地反应社会网络中信息和资源的传播，可能会降低算法的准确度.
MLPA算法假定两个结点拥有越多的共同邻居，标签在结点间传播的概率就越大，定义这种标签传播的方式为SS(Structural Similarity)，即
其中,Sij表示结点i和j的相似性，Γ(i)是结点i的邻居结点集合.在相关工作中[17]已经提到，MLPA算法同COPRA算法一样，容易产生大量的社区，导致输出结果的模块度较低.因此，如何在保证准确度的情况下提高算法的模块度和稳定性，是本文研究的重点.
分析现实的网络，结点影响(标签)的传播在一定程度上取决于结点所处的位置，具有较高影响力的结点往往处于社区的核心位置，能够影响周围影响力较低的结点[18].于是，本文定义了一种新的基于影响传播的标签传播方式ID(Influence Diffusion)，即
其中,lij为标签从结点i传播到j的度量，φi表示结点i在其邻域结构的相对影响能力，即
由式(6)可知结点i的相对影响能力φi取值区间为(0,1]，且φi值越大，结点i的标签传播能力越强.结合式(5)和式(6)可得标签从结点i传播到j的度量lij取值区间为(0,1)，且φi与φj的差值越大，标签越容易传播.由于大部分网络结点的相对影响力有明显的差异，导致标签在网络中不均衡地流动，降低了原有算法的随机性，使得算法能够很快收敛且输出的结果较为稳定.
于是本文提出一种基于多标签传播方式(MLPS)的重叠社区识别算法，综合SS和ID两种方式进行标签传播，那么结点i的标签传播到邻居结点j的概率Pij表示为：
目前的标签传播算法对网络进行初始化时，为每个结点都赋予一个独立的标签，这会导致输出结果出现大量孤立的小社区，从而降低输出社区的质量.为此，本文采用文献[20]提出的影响力最大化模型，选取网络中一组初始传播结点，使得这些结点能辐射到网络大部分结点，且尽可能的散落在每一个可能的社区，可以减少在传播时不需要的判断开销.
另外，COPRA算法的参数v是过滤标签对的阈值，设为全局值是不合理的.本文采用结点依赖的阈值选择方式[15,17]，即任意结点i拥有独立阈值vi.给定结点i的标签对集合为{(c1,b1),(c2,b2),…,(ck,bk)}，定义·p，其中=max{b1,b2,…,bk}，p作为算法的阈值选择参数.这样，既平衡了所有结点的阈值，又能有效地挖掘结构洞.
3.2 重叠社区发现的MLPS算法
为了提升算法运行的准确性和稳定性，本节提出一种基于多标签传播方式(MLPS)的重叠社区识别算法，算法逻辑流程如图2所示.
安神养心丸
MLPS算法的迭代停止条件和后处理沿用COPRA算法的设定，因此本文只给出改进的标签传播方式和阈值选择策略的部分代码，即算法1.算法设置两个标签向量：old和new，old.x(new.x)表示结点x更新前(后)的标签，每个结点都拥有一组标签对(c,b)，c是标签，b是结点拥有标签c的概率，N(x)是结点x的邻居集合，算法的唯一参数是阈值选择参数p.
3.3 算法的复杂度分析
定义N是结点个数，表示平均度，m为结点拥有的平均标签个数，在COPRA算法的基础上，MLPS算法：在初始化时增加了种子集合的选取O(N)；增加了结点间的相似性计算2)和影响传播度量的计算)+O(N·logN)；平衡了阈值后，算法不限制结点拥有的标签数，每次迭代的复杂度·m).算法的迭代次数一般很小，且大部分网络是稀疏的<<N)，当数据量变大时(m<<N)，MLPS算法拥有O(N·logN)的复杂度.在实际计算中，O(N·logN)的复杂度主要是影响力计算造成的.对此，我们可以离线计算所有结点的影响力来提高算法效率.
本节根据MLPS算法的输出结果，提出社区间的结构洞识别算法(SHCDA).算法首先将所有重叠结点加入结构洞的候选集合，然后分析社区重叠结构和重叠结点的位置特征，输出重要性得分top-k的结构洞.
定义ON为重叠结点集合，Ci是重叠结点i(i∈ON)归属的社区集合，pi,c表示结点i属于社区c的概率，满足pi,c=1.根据文献[9]的分析，结构洞的邻居结点能一定程度地反映其重要性，于是本文将结构洞的邻居结点的加权影响力均值作为该结构洞的重要性得分.那么，结构洞i的重要性得分为：
其中,n为结点i的邻居数，Infj表示结点j的重要性；wij=pi,c为结构洞i与其邻居结点j的关系权重，c是结点j归属的社区.
再别康桥图片
