基于进化算法的复杂网络社区检测

《基于进化算法的复杂网络社区检测》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、基于进化算法的复杂网络社区检测作者姓名李冰杰导师姓名、职称刘若辰副教授一级学科电子科学与技术二级学科电路与系统申请学位类别工学硕士提交毕业论文日期2014年12月学校代码10701学号1202120827分类号TN82TP18密级公开西安电子科技大学硕士学位论文基于进化算法的复杂网络社区检测作者姓名：李冰杰一级学科：电子科学与技术二级学科：电路与系统学位类别：工学硕士指导教师姓名、职称：刘若辰副教授提交日期：2014年12月CommunityDetectionbasedonEvolutionaryAlgorithmincomplexnetworksAthesissub

2、mittedtoXIDIANUNIVERSITYinpartialfulfillmentoftherequirementsforthedegreeofMasterinElectronicScienceandTechnologyByLibingjieSupervisor:Prof.LiuruochenDecember2014西安电子科技大学学位论文独创性（或创新性）声明秉承学校严谨的学风和优良的科学道德，本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究

3、成果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。学位论文若有不实之处，本人承担一切法律责任。本人签名：日期：西安电子科技大学关于论文使用授权的说明本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生在校攻读学位期间论文工作的知识产权单位属于西安电子科技大学。学校有权保留送交论文的复印件，允许查阅、借阅论文；学校可以公布论文的全部或部分内容，允许采用影印、缩印或其它复制手段保存论文。同时本人保证，获得学位后结合学位论文研究成果撰写的文章，署名单位

4、为西安电子科技大学。保密的学位论文在年解密后适用本授权书。本人签名：导师签名：日期：日期：摘要摘要近些年来，复杂网络受到了越来越多的研究者关注，大量的科研工作者投入到复杂网络领域的研究工作中。社区结构是复杂网络一个重要的属性，它揭示了复杂网络的某些行为特征和内在隐藏规律。在现实世界中存在的许多系统，如手机通信网络、交通道路网等都可以建模成复杂网络，网络中的节点代表系统中的各种具体的事物，这些事物之间的联系用网络中节点与节点间的边表示。因此，对复杂网络的社区检测问题的研究，有助于我们了解和分析真实世界中实际系统中各种不同的具体的事物之间的关系。复杂网络社区检测问题作为一

5、个重要研究方向，它是一个非常有意义的研究课题。遗传算法和蚁群算法都是近年来进化算法领域的研究热点，两种算法都可以兼顾种群的全局搜索能力和个体的局部搜索能力，同时算法本身具有很好的自适应能力，它们在解决某些问题领域比传统的优化算法更有优势。遗传算法已经被用于复杂网络社区检测问题，并且取得了很好的结果，但是其结果具有进一步提高的潜力；蚁群算法很少被用于复杂网络社区检测问题，使用蚁群算法去检测复杂网络的社区结构是非常有意义的。本文基于遗传算法，提出了一种基于改进的遗传算法的复杂网络社区检测的方法；基于蚁群优化算法，提出了一种基于分解和多目标蚁群优化算法的复杂网络社区检测的方

6、法。本文主要工作的详细介绍如下：1.提出了一种基于改进的遗传算法的复杂网络社区检测方法。在遗传算法框架下，使用模块度函数作为目标函数，对网络的社区结构进行检测。算法中采用一种新的初始化策略和一种基于基因变异的局部搜索方法，此外，算法还采用精英保存策略，对历史最优个体进行保存。通过仿真实验并与其它对比算法的结果进行对比和分析，本文提出的算法在检测网络的社区结构上有很好的能力。2.提出了一种基于分解和多目标蚁群优化算法的复杂网络社区检测的方法。首先，算法中提出一种新的适用于复杂网络聚类的多目标蚁群优化算法的框架，用于检测复杂网络中的社区结构。算法中采用分解的机制把两目标问

7、题成功的分解为一系列单目标的子问题，并采用蚁群优化的思想优化这些子问题，其中，每一只蚂蚁负责解决一个子问题，每一直蚂蚁得到的解对应着Pareto前端一个特定的点。然后，算法采用了一种基于图的针对特定问题的个体编码方法。最后，为了提高算法的稳定性和准确性，算法中设计了一种新的有效的局部搜索方法。通过一系列的实验及与其它算法结果的对比和分析，证明了我们提出的算法在检测复杂网路的社区结构问题上具有很强的竞争力。I西安电子科技大学硕士学位论文本课题得到国家自然科学基金(No.61373111)、省自然科学基金(No.2014JM8321)、中央高校基本科研基