基于重叠节点的复杂网络社区发现方法.pdf

(19)中华人民共和国国家知识产权局(12)发明专利申请(10)申请公布号CN107103053A(43)申请公布日2017.08.29(21)申请号201710229682.7(22)申请日2017.04.10(71)申请人南京信息工程大学地址210044江苏省南京市宁六路219号(72)发明人马廷淮刘琴曹杰薛羽(74)专利代理机构江苏爱信律师事务所32241代理人唐小红(51)Int.Cl.G06F17/30(2006.01)G06Q50/00(2012.01)权利要求书2页说明书4页附图1页(54)发明名称基于重叠节点的复杂网络社区发现方法(57)摘要本发明公开了基于重叠节点的复杂网络社区发现方法，从基于重叠节点的一个新的角度出发，利用标签传播的思想确定重叠节点，并采用计算节点权重的方法对网络中的所有重叠节点进行筛选，使得具有较低权重的节点具有更高被选中的概率，保留网络影响力较高的节点。删除前k个重叠节点，从而对更新后的网络进行社区发现。每一次的选择不是完全随机的，具有一定的倾向性和目的性，从而降低了破坏网络结构的可能性，能够快速、有效的发现网络的社区结构，使得社区发现结果更加清晰、准确。可应用在Facebook、微博、Twitter等大型复杂网络，能够较好的进行社区发现。CN107103053ACN107103053A权利要求书1/2页1.基于重叠节点的复杂网络社区发现方法，其特征在于，包括以下步骤：步骤1)，初始化整个网络，网络中的每个节点分配唯一的一个标签，以其标签初始化节点内存；步骤2)，信息接收者挑选，在步骤1)得到的初始化的节点，随机选择一个节点作为信息接收者；步骤3)，信息传播，在步骤2)中确定一个节点信息接收者，该节点的每一个邻居节点根据传播规则发送一个标签；步骤4)，信息接收，信息接收者根据接收规则接受在步骤3)中发送来的一个标签。再执行步骤2),直到满足停止条件；步骤5)，重叠节点发现，在这个阶段,把具有多个不同标签的节点记录下来即为重叠节点；步骤6)，节点权重，根据步骤5)，获得重叠节点，计算这些节点的权重；步骤7)，k重叠节点的选择，根据步骤6)，将节点的权重按升序排列，从中选择前k个重叠节点；步骤8)，社区发现，分别对移除k个重叠节点前后的网络节点进行社区发现。2.如权利要求1所述的方法，其特征在于，步骤1)中，初始化网络图结构，给网络中的每个节点分配一个标签，每个节点的标签必须有且仅有一个，根据节点的标签进行内存初始化。3.如权利要求1所述的方法，其特征在于，步骤3)中，信息传播，根据传播规则选择一个标签进行传播；其传播规则为从其存储器中选择随机标签，其概率与存储器中该标签出现的频率成比例。4.如权利要求1所述的方法，其特征在于，步骤4)中，信息接收，信息接收者根据接收规则接受发送来的一个标签；其接收规则为从当前步骤中挑选最受欢迎即出现频率最高的标签。5.如权利要求1所述的方法，其特征在于，步骤5)中，重叠节点发现，当迭代停止后，对每一个节点历史标签序列中各标签出现的频率做统计，与一个给定阈值γ，当γ＝0.5相比较，如果小于γ，则删除节点的此标签信息，否则保留，最终具有多个不同标签的节点即为重叠节点。6.如权利要求5所述的方法，其特征在于，步骤4)中，终止条件包括：(1)达到迭代次数；(2)收集到充分的信息后任意时间均可停止。7.如权利要求1所述的方法，其特征在于，步骤6)中，重叠节点权重，其用于衡量节点在网络中的影响力，它的值越大表明节点的影响力越大，反之亦然；计算重叠节点权重，其定义为：其中，节点集合V＝{v1，v2，...，vn}，集合Ti＝{ti1，ti2，...，tik}为与节点i相连接节点的集合，函数g(vi)为节点的度；d为阻尼系数，取值在0～1之间，每个节点权重的求解主要采2CN107103053A权利要求书2/2页用迭代的方式进行。8.如权利要求1所述的方法，其特征在于，步骤7)中，k重叠节点的选择，根据步骤6)计算重叠节点的权重，将其按升序排列，并根据网络大小以及重叠节点个数确定k的值，从重叠节点权重序列中选择前k个，得到所对应的重叠节点即所求的节点。9.如权利要求1所述的方法，其特征在于，步骤8)中，社区发现，通过现有的多种社区发现算法比较移除k个重叠节点前后的网络节点进行社区发现的结果。10.如权利要求9所述的方法，其特征在于，步骤8)中，其评价模型方法如下：1)互信息用来衡量两个变量之间共享的信息,，互信息值越大表明两个变量之间共享的信息越多，反之则越少；其定义如下：2)模块度(Modularity)用于衡量网络的社区划分是否得到好的结果，模块度的值越大表明社区发现的结果越好，反之则越少；其定义如下：3CN107103053A说明书1/4页基于重叠节点的复杂网络社区发