基于拓扑势和谱聚类的社区发现研究-软件工程专业论文.docx

万方数据 万方数据 论文审阅认定书 研究生 在规定的学习年限内，按照研究生培养方案 的要求，完成了研究生课程的学习，成绩合格；在我的指导下完成本 学位论文,经审阅，论文中的观点、数据、表述和结构为我所认同， 论文撰写格式符合学校的相关规定，同意将本论文作为学位申请论文 送专家评审。 导师签字： 年 月 日 致谢 依稀记得 12 年初次步入研究生实验室的场景，三年硕士研究生生涯即将结 束，时间如白驹过隙，回首这段时光，令人一生难忘。在这三年里，我收获颇多， 不仅仅学习了专业的理论知识，同时也通过实验室的项目锻炼自我，提升动手能 力，在此，衷心地向给予我支持、帮助、关怀的老师们、同学们以及亲爱的师兄 师弟们表示感谢！ 首先，非常诚挚的感谢我的导师王志晓副教授，是他将我带领到了科研的道 路上，并在三年的学习和生活中给予我莫大的指导和帮助。本文是在王老师的悉 心指导下完成的。在科学研究中，王老师精湛的专业知识，严谨的逻辑思维和踏 实的创新精神都无时不刻激励着我，并且在工作中精益求精的作风，深深的影响 了我。使我不仅仅在三年的研究生学习生活中严格要求自我，在以后工作的岗位 上更要严于律己，踏实工作。在实践中，王老师带领我们在项目中攻克难关，完 成任务，并且给我们提供了很多现场实践的机会，给予技术上的指导。 其次，感谢夏院长、孟老师给我们提供良好的科研环境，给了我们一个具有 温馨科研氛围的实验室，同时也感谢实验室的师兄师姐们，在我们刚刚步入研究 生生活时给我们科研和实践上的帮助与建议，使我们少走很多弯路，也要感谢各 位同学，在科研中一同讨论，共同进步，在项目中分工合作，提升效率。三年的 科研生活，有了你们的帮助，才会有多彩的颜色，那些一同体会过的酸甜苦辣， 那些成功的喜悦，失败的教训，都是我宝贵的财富，衷心祝愿大家一帆风顺。 另外，感谢我的父母和亲人们，是你们一直无私的支持我，无微不至的关怀 我，你们的鞭策、激励、鼓舞都是我前进的不竭动力，我会继续勇往直前，你们 是我最坚强的后盾。 最后，再次感谢导师王老师对我论文的指导，感谢各位师兄师弟们，同学们 对我论文的帮助，鄙人才疏学浅，虽然几经修改，但是疏漏之处在所难免，衷心 地感谢在百忙之中评阅论文和参加答辩的各位专家、教授，还望各位老师批评指 正，提出宝贵意见！ 摘 要 社区发现是复杂网络领域的热点研究内容。社区发现算法有很多种，谱聚类 方法是其中一类典型的方法。与其他的传统方法相比，该方法具有映射简单，数 理逻辑严密，及适用于任何形状的数据集等优点。但是，谱聚类方法也存在一些 不足。首先，需要人工确定社区数目，虽然可以利用谱间隙的梯形结构确定社区 数目，但是当网络社区结构不明显时，无法通过 Normal 矩阵的特征向量对应的 阶梯数目判断社区个数。其次，构建谱聚类的映射矩阵多采用节点度构造，节点 的度能够直观地反映节点与邻接节点间的关系，但是无法反映其与网络中其他节 点之间的联系，无法包含更多的结构信息，致使特征值及其相应特征向量的计算 出现偏差，在一定程度上影响了社区划分结果的准确性。 本文提出基于拓扑势场模型的社区数量检测方法。该算法基于复杂网络构建 拓扑势场，然后根据节点的拓扑势值计算网络的凹凸性参数。该值越大，复杂网 络对应拓扑势模型的波峰波谷越明显，该值越小，复杂网络所对应拓扑势模型的 起伏越平缓。本文针对上述两种类型复杂网络的特点分别搜索局部极大势值节 点，并对这些节点进行必要的判定和合并，最终检测出整个复杂网络的社区数目。 通过对真实复杂网络和人工生成的网络的实验，表明该方法具有较高的社区数量 检测的正确率。 本文提出融合拓扑势场和谱聚类的社区发现算法。该算法利用节点拓扑势值 构造谱聚类中的节点标准矩阵，并通过基于拓扑势场模型的复杂网络社区数量检 测方 法所 获得 的局 部 极值 点指 导谱 聚类 进 行社 区发 现， 将局 部 极值 点作为 K-means 聚类算法的初始中心点，减少迭代次数，提高谱聚类算法的性能。节点 拓扑势是周围节点在本节点处产生势值的叠加和，能从全局角度反映节点间的紧 密关系，使得节点标准矩阵包含了更多的节点间结构信息，有助于提高社区划分 结果的准确性。通过对真实复杂网络和人工生成的网络的实验，表明该方法对能 够有效的发现网络的社区，划分正确率更高。 本文共有图 15 幅，表 8 个，参考文献 61 篇。 关键词：拓扑势；谱聚类；社区数目；社区发现 I II Abstract Community detection is a hot topic in research of complex networks. There are many kinds of community detection algorithms. Spectral cluster