基于改进遗传算法的社区挖掘研究

doi:10.19678/j.issn.1000-3428.0049128

计算机工程 ›› 2019, Vol. 45 ›› Issue (1): 159-164. doi: 10.19678/j.issn.1000-3428.0049128

基于改进遗传算法的社区挖掘研究

郭旭超¹,王鲁¹,郝霞²,孙晓勇¹,孙博¹

1.山东农业大学信息科学与工程学院,山东泰安 271018; 2.中国农业大学信息与电气工程学院,北京 100083

收稿日期:2017-10-30 出版日期:2019-01-15 发布日期:2019-01-15
作者简介:郭旭超(1992—),男,硕士研究生,主研方向为遗传算法、复杂网络、数据挖掘;王鲁(通信作者),副教授、硕士;郝霞,博士研究生;孙晓勇,副教授、博士;孙博,讲师、博士
基金资助:
国家自然科学基金重大研究计划(91746104);山东农业大学重点培育学科(计算机科学与技术)建设项目

Study of Community Mining Based on Improved Genetic Algorithm

GUO Xuchao¹,WANG Lu ¹,HAO Xia ²,SUN Xiaoyong ¹,SUN Bo ¹

1.College of Information Science and Engineering,Shandong Agricultural University,Taian,Shandong 271018,China; 2.College of Information and Electrical Engineering,China Agricultural University,Beijing 100083,China

Received:2017-10-30 Online:2019-01-15 Published:2019-01-15

摘要/Abstract

摘要：

传统遗传算法应用于社区挖掘时初始种群划分精确度不高,且容易降低算法整体搜索性能。为此,提出一种改进的遗传算法,并将其引入到社区挖掘研究中。结合结构相似度与轮盘赌选择法,使染色体的每个基因趋向于选择结构相似度较大的邻居节点,提高初始种群的社区划分质量并加速算法收敛速度。实验结果表明,在人工基准网络中,该算法的初始种群划分精确度和模块度比传统遗传算法平均提高18%和12%,整体划分精确度比FEC和FN算法平均提高24.02%和22.01%,在真实世界网络中,社区划分精确度均优于FN、FEC和LPA算法,从而验证该算法具有较好的社团挖掘性能。

关键词: 复杂网络, 社区挖掘, 遗传算法, 结构相似度, 轮盘赌选择法

Abstract:

The partition accuracy of the initial population which is generated by the community mining based on traditional Genetic Algorithm(GA) tends to be low,which can easily lead to the poor overall search performance.To solve this problem,an improved GA is proposed and introduced into community mining study.In the algorithm,the structural similarity and the roulette wheel selection method are adopted so that each gene of chromosomes tends to choose the neighbor node with a larger structure similarity.In this way,the community partitioning quality of the initial population is improved and the convergence rate of this algorithm is accelerated.Experimental results show that in the artificial benchmark network,the partition accuracy and modularity of the initial population generated by the propose algorithm are generally increased by 18% and 12%,compared with the traditional GAs,and the overall partition accuracy of that is averagely increased by 24.02% and 22.01% compared with that of FEC and FN algorithms.In the real world network,the accuracy of community parition of the proposed algorithm is also much better than those of FN,FEC and LPA algorithms.It is verified that the algorithm has better community mining performance.

Key words: complex network, community mining, Genetic Algorithm(GA), structural similarity, roulette selection method

中图分类号:

TP18

郭旭超,王鲁,郝霞,孙晓勇,孙博. 基于改进遗传算法的社区挖掘研究[J]. 计算机工程, 2019, 45(1): 159-164.

GUO Xuchao,WANG Lu,HAO Xia,SUN Xiaoyong,SUN Bo. Study of Community Mining Based on Improved Genetic Algorithm[J]. Computer Engineering, 2019, 45(1): 159-164.

https://www.ecice06.com/CN/Y2019/V45/I1/159

参考文献

［1］WATTS D J,STROGATZ S H.Collective dynamics of‘small-world’networks［J］.Nature,1998,393(6684):440-442.
［2］BARABASI A L,ALBERT R.Emergence of scaling in random networks ［J］.Science,1999,286(5439):509-512.
［3］GIRVAN M.NEWMAN M E J.Community structure in social and biological networks［J］.Proceedings of the National Academy of Science,2002,99(12):7821-7826.
［4］BILAL S,ABDELOUAHAB M.Evolutionary algorithm and modularity for detecting communities in networks［J］.Physica A:Statistical Mechanics and Its Applications,2017,473:89-96.
［5］刘大有,金弟,何东晓,等.复杂网络社区挖掘综述［J］.计算机研究与发展,2013,50(10):2140-2154.
［6］PARK Y J,SONG M S.A genetic algorithm for clustering problems［EB/OL］.［2017-09-18］.https://www.researchgate.net/publication/243773422_A_genetic_algorithm_for_clustering_problems.
［7］RAGHAVAN U N,ALBERT R,KUMARA S.Near linear time algorithm to detect community structures in large-scale networks［J］.Physical Review E,2007,76(2).
［8］YANG B,CHEUNG W,LIU J.Community mining from signed social networks［J］.IEEE Transactions on Knowledge and Data Engineering,2007,19(10):1333-1348.
［9］NEWMAN M E J.Fast algorithm for detecting community structure in networks［J］.Physical Review E,2004,69(6).
［10］BLONDEL V D,GUILLAUME J L,LAMBIOTTE R,et al.Fast unfolding of communities in large networks［J］.Journal of Statistical Mechanics Theory and Experiment,2008(10):155-168.
［11］GUIMER A R,AMARALL A N.Functional cartography of complex metabolic networks［J］.Nature,2005,433(7028):895-900.
［12］HU Y,LI M,ZHANGP,et al.Community detection by signaling on complex networks［J］.Physical Review E,2008,78(2).
［13］GUERRERO M,MONTOYA F G,BANOS R,et al.Adaptive community detection in complex networks using genetic algorithms［EB/OL］.［2017-09-18］.https://arxiv.org/abs/cond-mat/0604419.
［14］SHANG Ronghua,BAI Jing.Community detection based on modularity and an improved genetic algorithm［J］.Physica A:Statistical Mechanics and Its Applications,2013,392(5):1215-1231.
［15］PIZZUTI C.GA-Net:a genetic algorithm for community detection in social networks［C］//Proceedings of International Conference on Parallel Problem Solving from Nature.Berlin,Germany:Springer-Verlag,2008:1081-1090.
［16］金弟,刘杰,杨博,等.局部搜索与遗传算法结合的大规模复杂网络社区探测［J］.自动化学报,2011,37(7):873-882.
［17］NEWMAN M.Modularity and community structure in networks［J］.Proceedings of the National Academy of Science,2006,103(23):8577-8582.
［18］PIZZUTI C.A multi-objective genetic algorithm for community detection in networks［C］//Proceedings of IEEE International Conference on Tools with Artificial Intelligence.Washington D.C.,USA:IEEE Computer Society,2009:379-386.
［19］MA T,WANG Y,TANG M,et al.LED:a fast overlapping communities’ detection algorithm based on structural clustering［J］.Neurocomputing,2016,207:488-500.
［20］金弟,刘大有,杨博,等.基于局部探测的快速复杂网络聚类算法［J］.电子学报,2011,39(11):2540-2546.
［21］DANON L,DIAZGUILERA A,DUCH J,et al.Comparing community structure identification［J］.Journal of Statistical Mechanics-theory and Experiment,2005(9).
［22］LUSSEAUD.The emergent properties of a dolphin social network［J］.Proceedings Biological Sciences,2003,270(Suppl2):186.
［23］GLEISER P M,DANON L.Community structure in Jazz［J］.Advances in Complex Systems,2003,6(4):565-573.
［24］GUIMERA R,DANON L,DIAZGUILERA A,et al.Self-similar community structure in a network of human interactions［J］.Physical Review E,2003,68(2).

[1]	周春雷, 宋继勐, 沈子奇, 余晗, 雷杰, 林兵. 数联网标识解析系统中的标识数据布局策略[J]. 计算机工程, 2024, 50(6): 311-320.
[2]	孙毅, 王会梅, 鲜明, 向航. Kubeflow异构算力调度策略研究[J]. 计算机工程, 2024, 50(2): 25-32.
[3]	白祉旭, 王衡军. 基于改进遗传算法的对抗样本生成方法[J]. 计算机工程, 2023, 49(5): 139-149.
[4]	桑永宣, 魏江坡, 王博, 宋莹. 具有边缘缓存机制的混合启发式任务卸载算法[J]. 计算机工程, 2023, 49(4): 149-158.
[5]	刘宇航, 尹小庆, 林云. 基于网络资源流量的链路预测方法[J]. 计算机工程, 2022, 48(9): 78-88.
[6]	潘金凤, 尹丽菊, 高明亮, 邹国峰. 压缩感知观测信号的低秩稀疏分解[J]. 计算机工程, 2022, 48(8): 234-239.
[7]	马华伟, 马凯, 郭君. 考虑多投递的带无人机车辆路径规划问题研究[J]. 计算机工程, 2022, 48(8): 299-305.
[8]	吴翼腾, 于洪涛, 顾泽宇. 基于统一描述网络结构模型的链路预测方法[J]. 计算机工程, 2022, 48(7): 51-58.
[9]	宋勇春, 王茜竹, 高正念. 基于HAGA的D2D-NOMA资源分配优化算法[J]. 计算机工程, 2022, 48(2): 275-280,290.
[10]	缪欣, 陈璇, 鲍红莹, 张静轩, 余炜. 移动传感器网络中路径扫描覆盖问题研究[J]. 计算机工程, 2022, 48(12): 150-155,164.
[11]	曾蓉晖, 林兵, 王明芬, 林凯, 卢宇. 超密集边缘计算网络中面向能耗优化的任务卸载方法[J]. 计算机工程, 2022, 48(11): 39-48.
[12]	吴铁洲, 邹智, 姜奔, 张晓星. 基于TLBGA-GRU神经网络的短期负荷预测[J]. 计算机工程, 2022, 48(11): 69-76.
[13]	曾茜, 韩华, 马媛媛. 基于模体的朴素贝叶斯链路预测方法[J]. 计算机工程, 2022, 48(10): 95-102.
[14]	杜秀丽, 周敏, 吕亚娜, 邱少明. 基于RBF神经网络优化的装备保障系统效能评估[J]. 计算机工程, 2021, 47(9): 282-287,296.
[15]	刘迪洋, 张震, 张进. 基于社区结构的复杂网络鲁棒性优化策略[J]. 计算机工程, 2021, 47(8): 84-92.

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

选择包含的内容

基于改进遗传算法的社区挖掘研究

Study of Community Mining Based on Improved Genetic Algorithm

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

模态框（Modal）标题

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

选择包含的内容

基于改进遗传算法的社区挖掘研究

Study of Community Mining Based on Improved Genetic Algorithm

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价