基于标签传播的可并行复杂网络重叠社区发现算法

被引：12

作者：

李春英 ^{[1
,2
]}

汤庸 ^{[1
]}

林海 ^{[1
]}

袁成哲 ^{[1
]}

麦辉强 ^{[1
]}

机构：

[1] 华南师范大学计算机学院

[2] 广东技术师范学院计算机网络中心

来源：

中国科学:信息科学 | 2016年 / 46卷 / 02期

基金：

国家高技术研究发展计划(863计划);

关键词：

复杂网络; 社区发现; 重叠社区; 标签传播; 并行计算;

D O I：

暂无

中图分类号：

O157.5 [图论]; TP301.6 [算法理论];

学科分类号：

摘要：

针对复杂网络重叠社区发现算法中预先输入参数的局限性以及标签冗余等缺点,提出一种改进的复杂网络重叠社区发现算法,最小极大团标签传播算法MMCLPA(minimal maximal clique label propagation algorithm).该算法通过寻找网络中的最小极大团(MMC)并对每个MMC中的节点赋予相同的标签来减少冗余标签,提高算法的稳定性.标签更新时采用亲密度作为权重并由MMC构成的核心节点群向四周扩散,后期处理采用自适应阈值方式克服了预先输入参数对未知网络的局限性.通过仿真和真实网络数据与其他几种有代表性的社区发现算法的实验对比分析,表明MMCLPA算法提高了对混合参数u的容忍度以及算法的鲁棒性.利用分布式计算模型Map Reduce和Hadoop云平台实现了MMCLPA算法的并行化,实验结果表明并行化的MMCLPA算法在百万级节点的复杂网络大数据中拥有单机系统下近似的社区发现质量以及良好的可扩展性.

引用

页码：212 / 227

页数：16

共 19 条

[1] 基于链接密度聚类的重叠社区发现算法 [J].

朱牧 ;

孟凡荣 ;

周勇 .

计算机研究与发展, 2013, (12) :2520-2530

[2] 一种有效的社会网络社区发现模型和算法 [J].

林友芳 ;

王天宇 ;

唐锐 ;

周元炜 ;

黄厚宽 .

计算机研究与发展, 2012, 49 (02) :337-345

[3]

基于局部相似性的复杂网络社区发现方法[J]. 刘旭,易东云.自动化学报. 2011(12)

[4]

局部搜索与遗传算法结合的大规模复杂网络社区探测[J]. 金弟,刘杰,杨博,何东晓,刘大有.自动化学报. 2011(07)

[5]

复杂网络社区挖掘—基于聚类融合的遗传算法[J]. 何东晓,周栩,王佐,周春光,王喆,金弟.自动化学报. 2010(08)

[6] An efficient community detection algorithm using greedy surprise maximization [J].

Jiang, Yawen ;

Jia, Caiyan ;

Yu, Jian .

JOURNAL OF PHYSICS A-MATHEMATICAL AND THEORETICAL, 2014, 47 (16)

[7]

Closed walks for community detection[J] . Yang Yang,Peng Gang Sun,Xia Hu,Zhou Jun Li.Physica A: Statistical Mechanics and its Applicat . 2014

[8]

Community detection in social networks using hybrid merging of sub-communities[J] . Mohsen Arab,Mohsen Afsharchi.Journal of Network and Computer Applications . 2013

[9] Detection of community overlap according to belief propagation and conflict [J].

Fu, Xianghua ;

Liu, Liandong ;

Wang, Chao .

PHYSICA A-STATISTICAL MECHANICS AND ITS APPLICATIONS, 2013, 392 (04) :941-952

[10]

A unified community detection algorithm in complex network[J] . Kan Li,Yin Pang.Neurocomputing . 2012

← 1 2 →