基于自然计算的复杂网络社区检测

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

1、代号10701学号1011120657分类号TP18密级公开题（中、英文）目基于自然计算的复杂网络社区检测CommunityDetectioninComplexNetworksBasedonNaturalComputation作者姓名陈静指导教师姓名、职务李阳阳副教授学科门类工学学科、专业电路与系统提交论文日期二○一三年一月西安电子科技大学学位论文独创性（或创新性）声明秉承学校严谨的学风和优良的科学道德，本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别

2、加以标注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说明并表示了谢意。申请学位论文与资料若有不实之处，本人承担一切的法律责任。本人签名：日期西安电子科技大学关于论文使用授权的说明本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。学校有权保留送交论文的复印件，允许查

3、阅和借阅论文；学校可以公布论文的全部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。同时本人保证，毕业后结合学位论文研究课题再撰写的文章一律署名单位为西安电子科技大学。（保密的论文在解密后遵守此规定）本学位论文属于保密，在年解密后适用本授权书。本人签名：日期导师签名：日期摘要I摘要随着科技的迅速发展，当今世界跨入了网络时代，现实世界中的很多复杂系统都可以用复杂网络来表示，如社会网络，生物网络，交通运输网络，电力网络和协作网络等。复杂网络可以用图模型表示，图中的节点表示现实世界复杂系统中的

4、对象，图中的边表示对象之间的连接关系。近年来，国内外掀起了研究复杂网络的热潮，复杂网络受到了来自各个领域研究者们的关注，例如数学，物理学，生物学和社会学等。研究发现，复杂网络不仅具有“小世界特性”和“无标度特性”，而且还具有另外一个重要的网络属性——社区结构特性。社区是网络中节点的子集，同一社区内节点之间的连接比较紧密，而不同社区间的节点的连接相对稀疏。同一社区内的节点在网络中具有相似的功能，因此这个社区在网络中有一个特定的作用。研究复杂网络中的社区结构对于分析复杂网络的拓扑结构、理解网络所具有的

5、功能以及预测网络可能具备的行为具有非常重要的意义，此外还具有广泛的应用前景。近年来，很多社区检测方法相继被提了出来，这些算法大致可以被分为三类：基于图分割的方法，基于层次聚类的方法和基于优化的方法，其中基于优化的方法得到了越来越多的关注。复杂网络的社区检测与数据的聚类分析很相似，本文在对已有的复杂网络社区检测算法进行深入研究的基础上，将聚类分析方法应用到复杂网络社区检测问题研究中，首先把网络转化为适合聚类分析的数据结构，然后对转化后的数据采用自然计算领域的算法进行聚类，从而得到网络的社区结构。本文

6、所做的主要工作如下：(1)研究了遗传算法(GeneticAlgorithm)的基本理论，针对传统遗传算法的缺陷引入局部搜索策略，并将其应用于复杂网络社区检测中。该算法引入了局部搜索策略，克服了传统遗传算法收敛速度慢，容易陷入局部最优的缺点。(2)研究了社区检测算法中编码方式引起的时间复杂度较高的问题，为了解决这个问题，我们提取共邻矩阵的谱信息代表节点，采取基于中心的编码方式，缩短了编码长度，降低了时间复杂度。在该方法中，我们把社区检测问题模型化为一个两个目标的多目标优化问题，并利用自适应多目标和声

7、搜索算法来优化这两个目标。可以从不同的分辨率分析网络，克服了传统的单目标优化算法只能得到一种划分的缺陷。(3)研究了复杂网络中的社区重叠现象，在复杂网络中，许多节点通常同时属于多个社区，形成了相互重叠的社区。为了对复杂网络进行重叠社区划分，我们II摘要把复杂网络的原图转化为边图，提取边图的谱信息，对边图利用改进的多目标量子粒子群算法进行社区划分，然后将边图的非重叠社区划分结果转化为对应的原图的重叠社区划分。本文得到如下基金资助：国家自然科学基金：61272279和61001202；中国博士后科学基

8、金特别资助：200801426；中国博士后科学基金：20080431228以及中央高校基本科研业务费专项资金资助：JY10000902040。关键词：复杂网络社区检测自然计算和声搜索算法量子粒子群算法多目标优化AbstractIIIAbstractWiththerapiddevelopmentofscienceandtechnology,theworldstepsintothenetworkage,andcomplexnetworksareanabstractrepresentat