吉林大学学报(工学版) ›› 2015, Vol. 45 ›› Issue (5): 1592-1600.doi: 10.13229/j.cnki.jdxbgxb201505031

• • 上一篇    下一篇

谱分析与启发式遗传算法相结合的多尺度社区检测方法

郭玉泉1, 李雄飞1, 刘昕2   

  1. 1.吉林大学 计算机科学与技术学院,长春 130012;
    2.吉林大学 网络中心,长春 130022
  • 收稿日期:2014-05-04 出版日期:2015-09-01 发布日期:2015-09-01
  • 通讯作者: 刘昕(1976-),女,高级工程师.研究方向:智能交通与网络计算.E-mail:lx@jlu.edu.cn
  • 作者简介:郭玉泉(1974-）,男,博士研究生.研究方向:复杂网络分析,数据挖掘.E-mail:guoyuquan@sohu.com
  • 基金资助:
    吉林省科技发展计划项目(20090468,20100508,201105017)

Heuristic genetic algorithm associated with spectral analysis uncovering multi-scale community of complex networks

GUO Yu-quan1, LI Xiong-fei1, LIU Xin2   

  1. 1.College of Computer Science and Technology, Jilin University, Changchun 130012,China;
    2.Network Center, Jilin University, Changchun 130022,China
  • Received:2014-05-04 Online:2015-09-01 Published:2015-09-01

RICH HTML

0   

PDF (PC)

341

摘要： 针对常规的社区检测方法不能揭示出社区结构的多尺度特征这一问题,本文通过对复杂网络传导率函数C与社区平均凝聚概率的分析,提出了一种局部启发变异策略,同时将复杂网络谱分析与遗传算法相结合,提出了多尺度社区检测算法HGASA。在人工网络和现实网络上对HGASA算法进行了测试,实验结果表明了HGASA算法的有效性和高效性。

关键词: 计算机应用, 多尺度社区, 遗传算法, 启发函数, 局部启发变异算法

Abstract: The community structure of complex networks has attracted much attention. However, previous methods can not investigate the multi-scale property of the community. To address this problem, by analyzing conduct function C and average agglomerate probability, a local heuristic heteromorphosis strategy is proposed; then, spectral analysis of complex networks is combined with genetic algorithm; finally a multi-scale community detection algorithm HGASA (Heuristic genetic algorithm with spectral analysis) is proposed. Extensive tests on artificial networks and real world networks justify the superiority of the HGASA algorithm.

Key words: computer application, multiple-scale community, genetic algorithm, heuristic function, local heuristic mutation algorithm

中图分类号: 

  • TP391
[1] Girvan M, Newman M E J. Community structure in social and biological networks[J]. Proceedings of the National Academy of Sciences of the United States of America, 2002, 99(12): 7821-7826.
[2] Newman M E J. Fast algorithm for detecting community structure in networks[J]. Physical Review E, 2004, 69(6):066133.
[3] Barber M J, Clark J W. Detecting network communities by propagating labels under constraints[J]. Physical Review E, 2009, 80(2): 026129.
[4] Liu D Y, Jin D, Baquero C, et al. Genetic algorithm with a local search strategy for discovering communities in complex networks[J]. International Journal of Computational Intelligence Systems, 2013, 6(2): 354-369.
[5] Newman M E J. Detecting community structure in networks[J]. European Physical Journal B, 2004, 38(2): 321-330.
[6] Shen H W, Cheng X Q, Cai K, et al. Detect overlapping and hierarchical community structure in networks[J]. Physica A:Statistical Mechanics and Its Applications, 2009, 388(8): 1706-1712.
[7] Palla G, Derenyi I, Farkas I, et al. Uncovering the overlapping community structure of complex networks in nature and society[J]. Nature, 2005, 435(7043): 814-818.
[8] Jin D, Yang B, Baquero C, et al. A Markov random walk under constraint for discovering overlapping communities in complex networks[J]. Journal of Statistical Mechanics-Theory and Experiment, 2011(5):P05031.
[9] Alex Arenas, Albert Diaz-Guilera, Conrad J. Synchronization reveals topological scales in complex networks[J]. Physical Review Letters, 2006, 96(11): 114102.
[10] Delvenne J C, Yaliraki S N, Barahona M. Stability of graph communities across time scales[J]. Proceedings of the National Academy of Sciences, 2010, 107(29): 12755-12760.
[11] Cheng X Q, Shen H W. Uncovering the community structure associated with the diffusion dynamics on networks[J]. Journal of Statistical Mechanics-Theory and Experiment, 2010(4):P04024,
[12] Fortunato S, Barthelemy M. Resolution limit in community detection[J]. Proceedings of the National Academy of Sciences, 2007, 104(1): 36-41.
[13] Arenas A, Fernandez A, Gomez S. Analysis of the structure of complex networks at different resolution levels[J]. New Journal of Physics, 2008, 10(5): 053039.
[14] Shen H W, Cheng X Q. Spectral methods for the detection of network community structure: a comparative analysis[J]. Journal of Statistical Mechanics-Theory and Experiment, 2010(10):P10020,
[15] Shen H W, Cheng X Q, Wang Y Z, et al. A dimensionality reduction framework for detection of multiscale structure in heterogeneous networks[J]. Journal of Computer Science and Technology, 2012, 27(2): 341-357.
[16] Tasgin M, Herdagdelen A, Bingol H. Community detection in complex networks using genetic algorithms[EB/OL].[2013-07-08] .http://arxiv.org/abs/0711.0491.
[17] Gregory S. Finding overlapping communities in networks by label propagation[J]. New Journal of Physics, 2010, 12(10):103018
[18] Lancichinetti A, Fortunato S, Radicchi F. Benchmark graphs for testing community detection algorithms[J]. Physical Review E, 2008, 78(4):046110.
[19] Lee C, Reid F, Mcdaid A, et al. Detecting highly overlapping community structure by greedy clique expansion[EB/OL].[2013-09-22].http://arxiv.org/abs/1002.1827.
[20] Zachary W. An information flow modelfor conflict and fission in small groups1[J]. Journal of Anthropological Research, 1977, 33(4): 452-473.
[21] Lusseau D. The emergent properties of a dolphin social network[J]. Proceedings of the Royal Society of London Series B: Biological Sciences, 2003, 270(Suppl 2): 186-188.
[1] 吴蔚楠,崔乃刚,郭继峰,赵杨杨. 多异构无人机任务规划的分布式一体化求解方法[J]. 吉林大学学报(工学版), 2018, 48(6): 1827-1837.
[2] 刘富,宗宇轩,康冰,张益萌,林彩霞,赵宏伟. 基于优化纹理特征的手背静脉识别系统[J]. 吉林大学学报(工学版), 2018, 48(6): 1844-1850.
[3] 王利民,刘洋,孙铭会,李美慧. 基于Markov blanket的无约束型K阶贝叶斯集成分类模型[J]. 吉林大学学报(工学版), 2018, 48(6): 1851-1858.
[4] 金顺福,王宝帅,郝闪闪,贾晓光,霍占强. 基于备用虚拟机同步休眠的云数据中心节能策略及性能[J]. 吉林大学学报(工学版), 2018, 48(6): 1859-1866.
[5] 赵东,孙明玉,朱金龙,于繁华,刘光洁,陈慧灵. 结合粒子群和单纯形的改进飞蛾优化算法[J]. 吉林大学学报(工学版), 2018, 48(6): 1867-1872.
[6] 刘恩泽,吴文福. 基于机器视觉的农作物表面多特征决策融合病变判断算法[J]. 吉林大学学报(工学版), 2018, 48(6): 1873-1878.
[7] 焦玉玲, 张鹏, 田广东, 邢小翠, 邹连慧. 基于多种群遗传算法的自动化立体库货位优化[J]. 吉林大学学报(工学版), 2018, 48(5): 1398-1404.
[8] 欧阳丹彤, 范琪. 子句级别语境感知的开放信息抽取方法[J]. 吉林大学学报(工学版), 2018, 48(5): 1563-1570.
[9] 刘富, 兰旭腾, 侯涛, 康冰, 刘云, 林彩霞. 基于优化k-mer频率的宏基因组聚类方法[J]. 吉林大学学报(工学版), 2018, 48(5): 1593-1599.
[10] 桂春, 黄旺星. 基于改进的标签传播算法的网络聚类方法[J]. 吉林大学学报(工学版), 2018, 48(5): 1600-1605.
[11] 刘元宁, 刘帅, 朱晓冬, 陈一浩, 郑少阁, 沈椿壮. 基于高斯拉普拉斯算子与自适应优化伽柏滤波的虹膜识别[J]. 吉林大学学报(工学版), 2018, 48(5): 1606-1613.
[12] 车翔玖, 王利, 郭晓新. 基于多尺度特征融合的边界检测算法[J]. 吉林大学学报(工学版), 2018, 48(5): 1621-1628.
[13] 赵宏伟, 刘宇琦, 董立岩, 王玉, 刘陪. 智能交通混合动态路径优化算法[J]. 吉林大学学报(工学版), 2018, 48(4): 1214-1223.
[14] 黄辉, 冯西安, 魏燕, 许驰, 陈慧灵. 基于增强核极限学习机的专业选择智能系统[J]. 吉林大学学报(工学版), 2018, 48(4): 1224-1230.
[15] 傅文博, 张杰, 陈永乐. 物联网环境下抵抗路由欺骗攻击的网络拓扑发现算法[J]. 吉林大学学报(工学版), 2018, 48(4): 1231-1236.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
版权所有 © 《吉林大学学报(工学版)》编辑部
地址：长春市人民大街5988号　电话：+86-431-85095297　传真：+86-431-85094074　E-mail: xbgxb@jlu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发