2网络社区发现算法分析与比较本文来自优,文'论#文^网，
毕业论文 www.youerw.com
网络社区发现算法的实现与比较是把根据用户对该内容的认识，通过对网络社区的分析，了解它的发现算法。本文主要讲解的网络社区发现算法，具有以下3个：GN算法；基于潜在语义的网络社区发现算法；派系过滤算法。
2.1网络社区发现算法分析
2.1.1Girvan-Newman算法
Girvan-Newman算法简称GN算法，Girvan和Newman将交通模型应用于社区发现这一场景中，把社会网络看成一个交通网，其特种就是连接某两个社区的路线会有更高的流量。将这些边找出来去掉，便可以将社会网络划分为很自然的社区。Girvan和Newman将这些边称为社团间瓶颈。
Girvan与Newman提出了使用边的中介度衡量某条边成为瓶颈的程度，边的中介度其实是对定点中介度的扩展，定义为网络中经过某条边得所有最短路径的数目。在有n个顶点，m条边的网络中，这个量可以在O(mn)时间计算得到。
高三毕业班班主任寄语G-N算法包括三个阶段：⑴计算网络中的所有边的介数；⑵找到介数最高的边并将它从网络中移除⑶重复前一步骤，知道每个节点就是一个退化社区为止。算法的整个工程也可以像层次类聚算法一样由一个社团结构树来表示，但是它是由根部向叶子进行构建的，与层次类聚算法恰好相反。树的分枝就表示随着边得删除而形成的社区结构。同样，在树的不同位置进行切割就会得到不同大小的社区结构。
G-N算法采用的是modularity,它是专门为社区划分而被提出的，着眼于社区内部顶点之间联系的紧密与社团之间顶点联系的稀疏。Modularity其实是社会网络中社区结构与随机网络中社区结构之间的区别。其定义如下：其中，表示连接社区i与社区j中的顶点的边的权值所占的比例；表示与社区i中顶点相关联的所有边得权值所占的比例，包括两个顶点全在社区内部和仅有一个顶点在社区内部两种情况。为了使用方便，将Qw记为Q。
不管是自顶向下的分割方法，还是自底向上的类聚方法，都会产生一个社团结构树，如果将毎一层的划分结果对应一个原图的划分Pk,整棵树就会对应原网络的一系列的划分，可以将其表示为P=(Pk)1≤k≤n,提出Q的目的就是在这一个序列中取出使其最大的一个Pk，对应找到的就是对原网络的最佳划分。
上一页 [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] 下一页
GN算法的设计与源代码+网络社区发现算法分析与比较 第3页下载如图片无法显示或论文不完整，请联系qq752018766
