一种求解社区检测问题的改进分布估计算法

doi:10.3969/j.issn.1000-3428.2013.07.054

计算机工程 ›› 2013, Vol. 39 ›› Issue (7): 242-246. doi: 10.3969/j.issn.1000-3428.2013.07.054

一种求解社区检测问题的改进分布估计算法

周本达¹，王煦法²，姚宏亮³

(1. 皖西学院应用数学学院，安徽六安 237012；2. 安徽省智能计算及其应用重点实验室，合肥 230037；3. 合肥工业大学计算机科学与技术系，合肥 230009)

收稿日期:2012-07-05 出版日期:2013-07-15 发布日期:2013-07-12
作者简介:周本达(1974－)，男，副教授、硕士，主研方向：智能算法，复杂网络；王煦法，教授；姚宏亮，副教授、博士
基金资助:
国家自然科学基金资助项目(61175051, 61070131)；安徽省高校省级自然科学研究基金资助重点项目(K2011A267, KJ2013 A259)

An Improved Estimation of Distribution Algorithm for Solving Community Detection Problem

ZHOU Ben-da¹, WANG Xu-fa ², YAO Hong-liang³

(1. School of Applied Mathematics, West Anhui University, Lu’an 237012, China; 2. Nature Inspired Computation and Its Applications Laboratory of Anhui Province, Hefei 230037, China; 3. School of Computer Science & Technology, Hefei University of Technology, Hefei 230009, China)

Received:2012-07-05 Online:2013-07-15 Published:2013-07-12

摘要/Abstract

摘要： 在分析网络模块性函数局部单调性的基础上，设计局部搜索变异算子，提出一种求解社区检测问题的改进分布估计算法。基于基准测试网络和大规模复杂网络对算法进行测试，实验结果表明，对于不同网络，该算法运行100次得到的Q函数平均值均优于Girvan- Newman算法、Newman快速算法和Tasgin遗传算法。

关键词: 社区检测, 分布估计算法, 复杂网络, 局部搜索变异, 模块性函数

Abstract: Based on the analysis of local monotonic of modularity function, this paper designs a Local Search and Mutation(LSM) operator, and proposes an improved Estimation of Distribution Algorithm(EDA) for solving community detection problem. The proposed algorithm is tested on basic network and big scale complex network. Experimental results show that the Q function average values of this algorithm while running 100 in different networks times is better than Girvan-Newman(GN) algorithm, Fast Newman(FN) algorithm and Tasgin Genetic Algorithm(TGA).

Key words: community detection, Estimation of Distribution Algorithm(EDA), complex network, Local Search and Mutation(LSM), modular function

中图分类号:

TP301.6

周本达, 王煦法, 姚宏亮. 一种求解社区检测问题的改进分布估计算法[J]. 计算机工程, 2013, 39(7): 242-246.

ZHOU Ben-Da, WANG Xiu-Fa, TAO Hong-Liang. An Improved Estimation of Distribution Algorithm for Solving Community Detection Problem[J]. Computer Engineering, 2013, 39(7): 242-246.

http://www.ecice06.com/CN/Y2013/V39/I7/242

参考文献

[1] Watts D J, Strogatz S H. Collective Dynamics of Small-world Networks[J]. Nature, 1998, 393(6684): 440-442.
[2] Adamic L A, Huberman B A, Barabasi A L, et al. Power-law Distribution of the World Wide Web[J]. Science, 2000, 287(5461).
[3] Girvan M, Newman M E J. Community Structure in Social and Biological Networks[J]. Proceedings of National Academy of Sciences, 2002, 99(12): 7821-7826.
[4] Yan G, Chen G, Lv J, et al. Synchronization Performance of Complex Oscillator Networks[J]. Physical Review E, 2009, 80(5).
[5] Fortunato S. Community Detection in Graphs[J]. Physics Reports, 2010, 486(3-5): 75-174.
[6] Newman M E J, Girvan M. Finding and Evaluating Com- munity Structure in Networks[J]. Physical Review E, 2004, 69(2).
[7] Brandes U, Delling D, Gaertler M, et al. Maximizing Modu- larity is Hard[EB/OL]. (2010-11-21). http://www.researchgate. net/publication/2176834_Maximizing_Modularity_is_hard.
[8] Tasgin M, Herdagdelen A, Bingol H. Community Detection in Complex Networks Using Genetic Algorithms[EB/OL]. (2010-01-21). http://arxiv.org/abs/cond-mat/0604419.
[9] Li Shuzhuo, Chen Yinghui, Du Haifeng, et al. A Genetic Algorithm with Local Search Strategy for Improved Detection of Community Structure[J]. Complexity, 2010, 15(4): 53-60.
[10] Pizzuti C. Community Detection in Social Networks with Genetic Algorithms[C]//Proc. of the 10th Annual Conference on Genetic and Evolutionary Computation. New York, USA: ACM Press, 2008.
[11] Jin D, He D, Liu D, et al. Genetic Algorithm with Local Search for Community Mining in Complex Networks[C]//Proc. of the 22nd IEEE International Conference on Tools with Artificial Intelligence. Arras, France: IEEE Press, 2010.
[12] Hauschild M, Pelikan M, Lima C, et al. Analyzing Probabilistic Models in Hierarchical BOA on Traps and Spin Glasses[C]//Proc. of GECCO’07. London, UK: IEEE Press, 2007.
[13] 刘明芳. 基于分布估计算法的整数规划研究[D]. 武汉: 武汉理工大学, 2008.
[14] 周树德, 孙增炘. 分布估计算法综述[J]. 自动化学报, 2007, 33(2): 113-124.
[15] 金弟, 刘杰. 局部搜索与遗传算法结合的大规模复杂网络社区探测[J]. 自动化学报, 2011, 37(7): 873-882.
[16] 何东晓. 网络社区智能挖掘算法的研究[D]. 吉林: 吉林大学, 2010.
[17] 朱文强. 粗糙集与蚁群算法在网络社区结构发现中的应用研究[D]. 苏州: 苏州大学, 2011.
[18] 周本达, 姚宏亮, 李国成. 一种求解聚类问题的分布估计算法[J]. 计算机工程, 2011, 37(22): 191-195.
[19] Danon L, Diaz G A, Duch J, et al. Comparing Community Structure Identification[J]. Journal of Statistical Mechanics: Theory and Experiment, 2005, 2005(9).
[20] Newman M E J. Fast Algorithm for Detecting Community Structure in Networks[J]. Physical Review E, 2004, 69(6).
[21] Zachary W. An Information Flow Model for Conflict and Fission in Small Groups[J]. Journal of Anthropological Research, 1977, 33(4): 452-473.
[22] Lusseau D. The Emergent Properties of a Dolphin Social Network[J]. Proceedings of the Royal Society B: Biological Sciences, 2003, 270(S2): 186-188.
[23] 数据堂. 科研数据共享平台[EB/OL]. (2011-04-18). http:// www.datatang.com/.
编辑刘冰

选择文件类型/文献管理软件名称

选择包含的内容

一种求解社区检测问题的改进分布估计算法

An Improved Estimation of Distribution Algorithm for Solving Community Detection Problem

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	刘宇航, 尹小庆, 林云. 基于网络资源流量的链路预测方法[J]. 计算机工程, 2022, 48(9): 78-88.
[2]	吴翼腾, 于洪涛, 顾泽宇. 基于统一描述网络结构模型的链路预测方法[J]. 计算机工程, 2022, 48(7): 51-58.
[3]	孙福禄, 王宇嘉, 刘子怡. 基于节点引力与鱼记忆的社区检测算法[J]. 计算机工程, 2022, 48(5): 104-111.
[4]	曾茜, 韩华, 马媛媛. 基于模体的朴素贝叶斯链路预测方法[J]. 计算机工程, 2022, 48(10): 95-102.
[5]	刘迪洋, 张震, 张进. 基于社区结构的复杂网络鲁棒性优化策略[J]. 计算机工程, 2021, 47(8): 84-92.
[6]	吕少卿, 赵雪莉, 张潘, 任新成. 一种保留社区结构信息的网络嵌入算法[J]. 计算机工程, 2021, 47(12): 122-130.
[7]	孙登第, 凌媛, 丁转莲, 罗斌. 基于稀疏子空间聚类的多层网络社团检测[J]. 计算机工程, 2021, 47(10): 52-60.
[8]	李英乐, 何赞园, 王凯, 许明艳. 基于资源传输节点拓扑紧密性的链路预测方法[J]. 计算机工程, 2021, 47(1): 50-57.
[9]	邱少明, 於涛, 杜秀丽, 陈波. 基于节点多属性相似性聚类的社团划分算法[J]. 计算机工程, 2020, 46(7): 84-90,97.
[10]	张志敏, 柴变芳, 李文斌. 基于稀疏自编码器的属性网络嵌入算法[J]. 计算机工程, 2020, 46(7): 98-103,109.
[11]	赵琪琪, 马慧芳, 刘海姣, 贾俊杰. 融合节点属性与结构信息的子空间异常社区检测方法[J]. 计算机工程, 2020, 46(6): 94-102.
[12]	谢菁, 羿舒文, 张毅. 基于双曲空间嵌入的极小值社区划分算法[J]. 计算机工程, 2020, 46(6): 73-80.
[13]	王曙燕, 韩雪, 孙家泽. 基于风险轨迹与复杂网络的缺陷定位方法[J]. 计算机工程, 2020, 46(6): 202-208.
[14]	朱江, 包崇明, 王崇云, 周丽华, 孔兵. 基于图结构特征分析的Top-k结构洞发现算法[J]. 计算机工程, 2020, 46(5): 94-101,108.
[15]	吴涛, 任淑霞, 张书博. 基于三角形子图的复杂网络过滤压缩算法[J]. 计算机工程, 2020, 46(5): 70-77.

模态框（Modal）标题

选择文件类型/文献管理软件名称

选择包含的内容

一种求解社区检测问题的改进分布估计算法

An Improved Estimation of Distribution Algorithm for Solving Community Detection Problem

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价