文档介绍：复杂网络中重叠社区发现算法的研究

重庆大学硕士学位论文
（学术学位）

学生姓名：李亚楠
指导教师：朱征宇教授
专业：计算机软件与理论
学科门类：工学

重庆大学计算机学院
二 O 一六年四月
Research on the Algorithm for Detecting
Overlapping Communities in Complex
Network

A Thesis Submitted to Chongqing University
in Partial Fulfillment of the Requirement for the
Master’s Degree of Engineering
By
Li Yanan

Supervised by Prof. Zhu Zhengyu
Specialty: Computer Software and Theory

College of Computer Science of
Chongqing University, Chongqing, China
April 2016
重庆大学硕士学位论文          中文摘要 

摘要
 
伴随着互联网技术的发展，大量的复杂网络和社会结构正源源不断的产生。人
们对复杂网络的研究，已经从早期的简单图论阶段进入到了现在的大批网络模型
与算法并现的繁荣阶段。社区结构是复杂网络的一种中观结构，是对复杂网络某
种程度的压缩，对了解网络结构与功能具有重要意义。传统的社区发现算法大都
只能发现非重叠社区，对于重叠社区的发现算法的研究，目前还处于早期探索阶
段。现实网络中存在大量的重叠社区，如一个人可以参加多个兴趣小组、一篇学
术论文可以横跨多个学术领域、一个单词可以具有多个词性等等，因此发现网络
中具有重叠性的社区结构往往具有更加实际的意义。针对当前各种应用的需要，
本文在探索各种更加有效的重叠社区发现算法上进行了较系统和深入的研究，并
形成了以下主要研究成果：
①针对当前基于局部扩展类算法的不稳定性，提出了一种 DOCNR 算法。首先，
新算法针对 PageRank 均匀分配策略进行改进，形成一种更适应于无向图处理的
NodeRank 算法，利用 NodeRank 算法计算所有网络节点的重要性，并依据节点的
重要性选取种子节点。其次，一个没有外部链接的无向网络，经过 NodeRank 算
法处理后，所有节点的重要度值之和近似保持不变，基于此提出了一种新的适应
度函数，并在该适应度函数基础上，以种子节点为核心，按照广度遍历的思想逐
层向外扩展社区，不同的种子节点扩展出的社区间会有交集，因此新算法能够发
现重叠社区。最后，对重叠度过高的社区进行合并处理，作为最终计算结果。
②针对当前 LFM