GN算法的设计与源代码+网络社区发现算法分析与比较
摘要： 复杂网络中,节点可以被划分成若干组,组内节点之间的连接比较稠密,而不同组节点之间的连接则比较稀少,这样的划分结果被定义为复杂网络的社区结构。通过对复杂网络社区结构的研究,一方面可以使我们更好地了解和解释现实世界中所呈现出的各种社区现象,如人际关系网络、疾病传播区域;另外一方面我们可以将复杂网络社区结构的研究理论成果应用到具体问题当中去,如可以设计出具有更好特性的实际网络。本文首先介绍了复杂网络社区结构的基本概念,以及用于复杂网络社区结构发现的若干著名算法,总结了不同算法所存在的优缺点。分析和比较了Girvan-Newman(GN)算法，基于潜在语义的网络社区发现算法，派系过滤算法。本文来自辣,文'论#文^网，毕业论文 www.751com.cn最后对GN算法进行了编程并对算法进行了测试。
关键词： 复杂网络；社区发现；GN算法；潜在语义；派系过滤算法
The Research and Realization of Girvan-Newman Algorithm
Abstract: In complex networks, nodes can be divided into several groups. The density of links in group is bigger than those between, which is defined as the community of complex networks. The research of community of complex network leads two aspects virtues. On the one hand, it enables us to better understand the community of real world, such as interpersonal networks, disease transmission area; on the other hand, the theory of community structure of complex networks theory can be applied to design the actual network with good characteristics. The basic concepts of community are introduced firstly, and then several community detection algorithms are introduced. Three community detection algorithms are analyzed and compared, such as Girvan-Newman(GN) algorithm, online community detection algorithm based on latent semantic, factions filter algorithm. At last GN algorithm is realized and testing.
Keywords: complex networks; community structure detection; GN algorithm; latent semantic; faction filter algorithm
目录
摘要 i
Abstract i
目录 ii
1 绪论 1
1.1 研究的背景 2
1.2 国内外研究现状 2
1.3 论文的组织结构 3
1.4 课题的目的和意义 3
2 网络社区发现算法分析与比较 4
2.1 网络社区发现算法分析 4
2.1.1 Girvan-Newman算法 4
2.1.2 基于潜在语义的网络社区发现算法 5
2.1.3 派系过滤法 6
2.2 网络社区发现算法的比较 7
2.3 分析三种算法的弊端及改进 10
2.3.1 GN算法的弊端及改进 10
2.3.2 基于潜在语义算法改进 10
3 GN算法的实现 12
3.1 GN算法的数学概念 12
3.2 GN算法的详细设计 13
3.3 GN算法的程序实现 14
3.3.1 开发环境 14
3.3.2 程序详细设计 15
3.4 GN算法测试结果及分析 27
4 结论 31
4.1 总结 31
4.2 心得体会 31
致谢 33
参考文献 34，2883
[1] [2] [3] [4] [5] [6] [7] [8] [9] [10] 下一页