块模型和复杂网络社区检测

《块模型和复杂网络社区检测》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、块模型和复杂网络社区检测作者姓名王佳利学校导师姓名、职称吴建设教授领域电子与通信工程企业导师姓名、职称罗二平教授申请学位类别工程硕士提交学位论文日期2014年12月学校代码10701学号1202121326分类TN82号TN82密级公开西安电子科技大学硕士学位论文块模型和复杂网络社区检测作者姓名：王佳利领域：电子与通信工程学位类别：工程硕士学校导师姓名、职称：吴建设教授企业导师姓名、职称：罗二平教授提交日期：2014年12月BlockmodelandComplexNetworkCommunityDetectionAthesissubmittedtoXIDIANUNIVERSIT

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

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

4、文属于保密，在年解密后适用本授权书。本人签名：导师签名：日期：日期摘要摘要本文以进化算法为基础，先后研究了基于图分割的块模型问题和基于分解的多目标进化在社区检测上的问题。论文主要进行了以下三个工作：1.研究进化算法求解块模型问题。算法过程包括利用提取完全子图的思想进行种群初始化，采用冲突交叉算子产生子代，再采用修复操作优化子代。最后，经过反复迭代，算法逐渐收敛，目标函数值达到最大。通过在四组不同来源的网络上分别用进化算法EA和分组遗传算法GGA做块模型分割，证明了本章提出了基于进化算法EA的块模型方法在处理大规模网络上具有明显的优势,尤其在节点数较多和边密度较大的网络上。2.提

5、出了一种基于模块度的符号网络多目标社区检测方法。文中针对符号网络的特性，首先定义了两个目标函数，然后采用分解的方法使得种群不断进化，其中遗传操作过程包括采用提取完全子图的方法对种群进行初始化，单路交叉算子产生子代和基于正邻居的变异操作，从而使个体不断向最优解收敛。实验中通过分析符号网络呈现的Pareto前端验证了本章提出的两个多目标函数在符号网络社区检测上是可行的，通过与对比算法的实验结果比较、分析，证明了本章提出的基于模块的MOEA/D在呈现网络不同层次结构和提取小社区方向上具有明显的优势。3.提出了一种基于密度型的多目标社区检测算法。此算法在是第二个工作的基础上，重新定义了

6、两个目标函数，使得此算法不仅可以检测符号网络的社区结构还可以检测无符号网络的社区结构。文中详细描述了目标函数的具体定义和其动机来源，遗传操作同样包括提取完全子图的方法、单路交叉算子和基于邻居的变异。通过分别对符号网络和无符号网络做社区检测，验证了本章提出的两个多目标函数在社区检测上是可行的，通过与基于模块度MOEA/D及其他算法的实验结果比较，证明了本章提出的基于密度型的MOEA/D是一种更全面更高效的社区检测方法。关键词：进化算法，块模型，多目标，社区检测，符号网络，分解论文类型：应用基础技术I西安电子科技大学硕士学位论文IIABSTRACTABSTRACTThispaper

7、basedontheevolutionaryalgorithmhasstudiedtheproblemofblockmodelbasedongraphpartitioningandproblemofmulti-objectiveevolutionarywithdecompositionappliedtocommunitydetection.Thispapermainlystudiesthefollowingthreeworks:1.Applyevolutionaryalgorithmtobl