发明名称 |
一种复杂网络中的社区划分方法 |
摘要 |
本发明提出一种复杂网络中的社区划分方法,以若干个不同的局部带有影响力的节点为核心,并使节点的影响力从核心逐层向外均匀扩散,最终形成了以影响力最大的节点为核心,逐层扩展中节点的影响力不断衰减,它们之间相互关联形成一个局部区域,扩展到方法的停止,节点影响力很小,到达该局部区域的网络边缘。对于一个大规模的无序复杂网络,能够迅速的定位不同重要程度的节点位置,挖掘出一些更细粒度上的信息,同时可以保持了原有网络的结构特性不变,对原有的大规模复杂网络进行简化与规模的缩小,不仅可以提高搜索的效率,更可以从宏观上更清晰的分析出大规模网络的结构。 |
申请公布号 |
CN101383748A |
申请公布日期 |
2009.03.11 |
申请号 |
CN200810224175.5 |
申请日期 |
2008.10.24 |
申请人 |
北京航空航天大学 |
发明人 |
韩言妮;武文琛;李德毅;张书庆 |
分类号 |
H04L12/44(2006.01)I;G06F17/30(2006.01)I |
主分类号 |
H04L12/44(2006.01)I |
代理机构 |
北京永创新实专利事务所 |
代理人 |
周长琪 |
主权项 |
1、一种复杂网络中的社区划分方法,其特征在于,包括如下步骤:步骤一:对于给定的拓扑结构,基于节点局部影响力的特性,选取整个网络结构中的影响范围,计算网络中所有节点相互作用之后而产生的影响力叠加值;步骤二:选取影响力值最大的节点为中心,选取与该节点直接相连的节点为第一层,按跳数向外扩展,扩展与它相邻的邻居节点作为下一层,形成一个以影响力最大的节点为中心,各层节点中最大影响力数值不断下降趋势的区域;步骤三:计算每层扩展节点对下一层节点和对上一层节点连接的边数的比值,当这个比值下降时,停止该局部中心的扩展;在扩展的过程中,如果在当前扩展层中存在节点的影响力数值大于前一层节点的最大影响力值,那么就删除该节点,并且对该次扩展的所有剩余节点,利用归属度对剩余节点中每个节点是否属于该局部区域进行判断;否则当前扩展层中存在节点的影响力数值都小于前一层节点的最大影响力值,全部归入该中心形成的局部社团;步骤四:输出与该局部中心最大值节点存在紧密连接的所有成员,即属于该局部区域的骨干成员(它们对该局部影响力最大的节点都产生影响力的叠加,同时也被最大影响力的局部中心所影响和覆盖),结束本次扩展;步骤五:对网络中剩余的节点,转到步骤二,直至网络中所有节点都被扩展过;步骤六:输出不同局部社区之间的重叠节点和边缘节点,并对边缘节点进行社区归属的判断,统计它与已有局部社区的连接情况,判断该边缘节点是属于哪个局部社区,本方法结束。 |
地址 |
100083北京市海淀区学院路37号 |