基于进化计算的社区挖掘算法及其应用研究

《基于进化计算的社区挖掘算法及其应用研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、CommunityMiningAlgorithmBasedonEvolutionaryComputationandResearchonItsApplicationADissertationSubmittedfortheDegreeofMasterCandidate：LiJiajiaSupervisor：Prof.FengJiuchaoProf.WeiWenhongSouthChinaUniversityofTechnologyGuangzhou,China分类号：TP3-05学校代号：10561学号：

2、201320108036华南理工大学硕士学位论文基于进化计算的社区挖掘算法及其应用研究作者姓名：李佳家指导教师姓名、职称：冯久超教授魏文红副教授申请学位级别：工学硕士学科专业名称：电路与系统研究方向：复杂网络论文提交日期：2016年4月20日论文答辩日期：2016年6月7日学位授予单位：华南理工大学学位授予日期：年月日答辩委员会成员：主席：余华教授委员：余卫宇副教授刘徐迅副教授赵平高级工程师冯久超教授摘要生活中，可以用网络来表示大量的复杂系统，比如说，朋友关系网络，交通运输网络，因特网，电话线路网络，

3、新陈代谢网络，食物链网络等。近些年来，复杂网络成为了一个研究热点，吸引了越来越多的国内外各个领域的研究人员的关注。在早期的研究中，发现复杂网络具有小世界特性和无标度特性，但在后续的研究中，研究人员还发现复杂网络还具有极其重要的社区结构特性，社区结构定义为：同一社区内的节点之间的连接比较紧密，不同社区之间的连接比较稀疏。挖掘复杂网络中的社区结构，我们可以更好的分析网络的结构，从而理解网络的功能。此外，还有利于我们发现网络中潜在的规律进而可以对网络的行为做出预测，故社区挖掘具有十分重要的意义以及广泛的应用

4、前景。为了研究复杂网络，研究人员提出了许多社区挖掘算法，这些算法总的来说可以归为以下三类：基于图分割的方法，基于层次聚类的方法和基于模块度(modularity)优化的方法，在这三类方法中，研究人员比较关注的是基于模块度优化的方法。模块度是Newman和Girvan提出来的，它是一个用于衡量网络社区划分质量的目标函数。通常来说，得到的模块度值越大，划分得到的社区结构也会越明显。文化基因算法(Memeticalgorithm)最近在进化计算领域里受到了很多研究人员的关注，它除了对种群的全局搜索还具有对个

5、体的局部启发式搜索，这两者的结合使其在解决某些问题的搜索效率上要比传统的遗传算法高。利用文化基因算法的优点，将其应用于复杂网络社区挖掘中。本文所做的主要工作如下：(1)研究了使用基于模块度优化的方法挖掘出的社区结构会存在分辨率限制的问题，我们通过采用一个新的目标函数——扩展模块度密度(generalmodularitydensity)来解决这个问题，该目标函数可以通过调节里面的参数来解决分辨率限制问题。(2)在研究文化基因算法(Memeticalgorithm)基本理论的基础上，提出了一种可应用于复杂

6、网络社区挖掘的文化基因算法。我们将复杂网络社区挖掘问题看成是一个单目标优化问题，把模块度Q和扩展模块度密度??作为目标函数，并采用文化基因算法MA-Net分别优化这两个目标，得到了基于MA-Net框架的两种社区挖掘算法：MA-Net(Q)和MA-Net(??)。接着，我们在人工合成网络和真实I世界网络中进行了实验，实验表明，带有局部搜索策略的文化基因算法相比于传统的遗传算法具有收敛速度快，不容易陷入局部最优，而且挖掘出的网络社区准确度比传统遗传算法更高的优点。最后，通过与GN算法比较，验证了本文的算法

7、是有效的。关键词：复杂网络社区挖掘扩展模块度密度进化算法文化基因算法IIAbstractInourlife,thenetworkcanbeusedtorepresentalargenumberofcomplexsystems,suchasfriendshipnetworks,transportnetworks,theInternet,telephonelinenetworks,metabolicnetworks,foodchainnetworksandsoon.Inrecentyears,comple

8、xnetworkshavebecomeahotresearchtopic,attractingtheattentionofagrowingnumberofresearchersinvariousfieldsathomeandabroad.Inearlierstudies,wefoundthatcomplexnetworkswithsmallworldandscale-freeproperty,butinthefollow-upstudy,theresea