基于进化算法和节点局部信息的复杂网络社区检测

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

1、基于进化算法和节点局部信息的复杂网络社区检测作者姓名罗爽导师姓名、职称尚荣华副教授一级学科电子科学与技术二级学科电路与系统申请学位类别工学硕士提交学位论文日期2014年11月学校代码10701学号1202120900分类TN82号TP18密级公开西安电子科技大学硕士研究生毕业论文基于进化算法和节点局部信息的复杂网络社区检测作者姓名：罗爽一级学科：电子科学与技术二级学科：电路与系统学科门类：工学硕士指导教师姓名、职称：尚荣华副教授提交日期：2014年11月Communitydetectionbasedonevol

2、utionaryalgorithmandnodelocalinformationAthesissubmittedtoXIDIANUNIVERSITYinpartialfulfillmentoftherequirementsforthedegreeofMasterinElectronicScienceandTechnologyByLuoshuangSupervisor:Assoc.Prof.ShangronghuaNovember2014西安电子科技大学学位论文独创性（或创新性）声明秉承学校严谨的学风和优良的科学

3、道德，本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。学位论文若有不实之处，本人承担一切法律责任。本人签名：日期：西安电子科技大学关于论文使用授权的说明本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生在校攻读学位期间论

4、文工作的知识产权单位属于西安电子科技大学。学校有权保留送交论文的复印件，允许查阅、借阅论文；学校可以公布论文的全部或部分内容，允许采用影印、缩印或其它复制手段保存论文。同时本人保证，获得学位后结合学位论文研究成果撰写的文章，署名单位为西安电子科技大学。保密的学位论文在年解密后适用本授权书。本人签名：导师签名：日期：日期：摘要摘要复杂网络的社区检测问题是指利用网络中节点之间相互连接的拓扑结构关系，找出图形中内部连接相对紧密、外部连接相对稀疏的社区结构。针对这些社区结构的研究，有助于我们更好的探测到复杂网络的拓扑结

5、构层次图，从而挖掘网络中个体元素的特性和有用信息。随着计算机科学技术的不断发展，复杂网络的应用模型不断渗透到科学研究和数据信息挖掘的各个方面，相应的研究算法如层次聚类的算法、谱聚类的算法和基于进化的目标优化的算法等相继被提出。然而，目前存在的这些算法存在着准确率较低、收敛速度较慢等的问题。同时，随着信息时代的到来，复杂网络的规模也在不断增长，现有的算法已经很难高效的检测到大规模中存在的社区结构。因此，本文根据上述问题，分别设计了以下三种社区检测的算法，主要工作如下：(1)提出了一种基于近邻传播的进化多目标优化算

6、法来解决社区检测问题。将经典快速的数据聚类的方法，即近邻传播算法和基于多目标优化的进化算法相结合，在利用数据聚类算法有效快速地获得网络预划分结果的同时，利用多目标进化算法的全局寻优性，最终使得社区检测的结果达到更好的划分精度，同时得到较好的收敛速度。(2)提出了一种基于局部核节点和社区融合策略改进的标签传播算法以解决大规模复杂网络的社区检测。标签传播算法是一种半监督学习的算法，针对大规模网络的社区检测具有很低的时间复杂度，仅为O(m)。然而LPA算法的聚类结果具有较大的随机性，根据每次在节点上标签传播的顺序不同

7、，得到的社区结构差异很大。因此本算法在标签传播算法的基础上设计加入了一种基于局部核节点和社区融合的策略，利用核节点与其邻居节点之间相似度关系，先形成局部小社区，然后通过核节点与核节点之间的关系对这些小社区进行有选择的合并，然后在此基础上再对所有节点按照标签传播的思想赋予标签。该算法在继承了标签传播算法时间复杂度较低的优点同时，进一步提高了算法的检测精度。在大规模真实网络的实验结果上表明了该算法要优于标签传播算法。(3)提出了一种基于节点隶属度和子社区融合的大规模社区检测方法。该方法首先根据提出的局部邻居节点间隶

8、属度函数，将亲密度较高的节点对融合，实现对网络进行预处理，提高现有算法精度的同时可以快速挖掘局部潜在的完全子图结构。其次，根据提出的局部节点与相邻社区间的隶属度函数，对得到的网络进行修正，并且通过调解节点与相邻社区隶属度函数的参数，可以在精确检测到I西安电子科技大学硕士研究生毕业论文非重叠社区的同时涉及到重叠社区的检测。同时由于本算法采用了标签传播的算法框架，具有较低的时间复杂度，可适