Python代码:GitHub


​ 一般意义上讲,一个社区也可以被称为群、聚类或模块,是网络中一群阶段或边的集合,其内部的节点间连接较为紧密,而社区间的连接却相对稀疏。之前实现了针对无权网络的GN算法,这篇文章则是针对加权网络的GN算法

​ 针对无权网络的GN算法,可以看一看我之前的那篇文章

针对加权网络的GN算法

GN算法

GN算法是一种利用基于边介数的社区发现算法

这样的社区发现算法的主要思路为:计算网络中所有边的边介数,然后寻找边介数值最大的边并移除。在移除时,会改变一些边的边介数。以前经过被移除边的最短路径,现在改为经由其他边,因此必须重新计算边介数,然后再次搜索值最大的边并移除,依此类推。当一条接一条边被移除时,最初连通的网络最终会被分成两部分、三部分等等,直至网络的每一个成为一个社区,是一种分裂算法

算法的执行过程可用树状图表示,如下图所示。算法从顶部开始生成树状图,首先是单个连通网络,然后将其不断划分,直至每个分支只有单个结点为止。在算法运行期间,每个独立的网络结构状态对应于树状图的水平切分,在图2中用红线表示。与红线相交的每个分支代表一组节点,即一个社区,沿分支向下到底部的全部节点都为其成员。因此对于一个连通网络,树状图能够得到算法执行全过程中每个阶段里网络划分的社区结构。

1

针对加权网络的GN算法描述

这里给出针对有权网络的Girvan-Newman算法,加权Girvan-Newman算法求解的具体实现过程为:

  1. 忽略边的权重,以无权网络计算网络中所有连接边的边介数;
  2. 将边介数除以对应边的权重得到边权比;
  3. 找到边权比最高的边将它移除,并计算网络的模块性 Q 函数,在计算中当边权比最高的边有多条时,同时移除这些边,并将此时移除的边和Q值进行存储;
  4. 重复步骤1,2,直到网络中所有的边均被移除。
  5. Girvan-Newman算法划分结束后,取出Q值最大时的序号,在原始矩阵中依次去除截止到该次划分的边。得出最终连通矩阵,矩阵的值为权值。

Python实现

Python代码:GitHub

Python环境需求

这里使用Python的 NetworkX 包以及 Matplotlib 包来完成对于Girvan-Newman算法的演示

以及Gephi,一个基于JVM的可视化平台。

NetworkX是一个用于创建,操作和研究复杂网络的结构、动态和功能的Python包

Matplotlib是一个Python 2D绘图库,利用它完成模块化函数Q与划分社团数目的关系曲线,之后使用Gephi作为网络的可视化工具,将GML文件中的图中划分的社团表示出来。

Python环境需求:

  • Python-3.6.3
  • NetworkX-2.0
  • Matplotlib-2.1.0

Lesmiserables 网络

Lesmiserables网络是维克多·雨果所著《悲惨世界》(Les Misérables)一书中人物角色间的加权连接网络。一共有77个节点,254条边,也并不知道应划分的社团数量。

2

运行完毕 Girvan-Newman_weighted.py 我们可以得到以下结果,Q值在划分社团数为20时,达到最大值,如下图所示。当然我们也可以采用Q值与划分社区数量曲线中的极大值点,作为划分社团的依据。

3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
-------------------------------------theMax Q and divided communities---------------------------------------

Thenumber of Communites: 20

Communites:[

['Myriel','MlleBaptistine', 'MmeMagloire', 'CountessDeLo', 'Count', 'OldMan','Champtercier', 'Cravatte', 'Geborand', 'Napoleon'],

['Labarre'],

['Anzelma','Montparnasse', 'Gueulemer', 'Claquesous', 'MotherInnocent', 'Eponine','Babet', 'Fauchelevent', 'Woman2', 'MlleGillenormand', 'Marius','MmeThenardier', 'Brujon', 'Woman1', 'Thenardier', 'Javert', 'Gillenormand','Simplice', 'Valjean', 'Cosette'], ['Listolier', 'Tholomyes', 'Dahlia','Blacheville', 'Fameuil', 'Favourite', 'Zephine', 'Marguerite', 'Fantine'],

['MmeDeR'],

['Isabeau'],

['Gervais'],

['Brevet','Cochepaille', 'Judge', 'Champmathieu', 'Bamatabois', 'Chenildieu'],

['Perpetue'],['Scaufflaire'],

['MmePontmercy','Pontmercy'],

['Boulatruelle'],

['Gribier'],

['Jondrette'],

['Enjolras', 'Joly','Child1', 'Grantaire', 'Courfeyrac', 'MmeHucheloup', 'MotherPlutarch','Feuilly', 'Bahorel', 'Mabeuf', 'Combeferre', 'MmeBurgon', 'Prouvaire','Child2', 'Gavroche', 'Bossuet'],

['Magnon'],

['MlleVaubois'],

['LtGillenormand'],

['BaronessT'],

['Toussaint']]

Max_Q: 0.4701546903093807

将输出的结果导入到Gephi后,以group为依据着色,可得到下图,我们发现Girvan-Newman算法对带权值网络也是比较有效的。

4

Girvan-Newman算法分析

对于mm条边和nn个节点的网络,Girvan-Newman算法计算边介数的时间复杂度为O(n(m+n))O(n(m+n)),且在移除mm条边的每条边前都需要执行该计算,所以整个算法的时间复杂度为O(mn(m+n))O(mn(m+n))

若在mnm∝n稀疏网络中的时间复杂度为O(n3)O(n^3 )

这里总结下Girvan-Newman算法的优缺点。

Girvan-Newman算法的优点

  1. 在知道划分社团数量时,可以较为精确的给出社团的划分结果;

  2. 可以给出不同程度的社团划分结果,可以揭示关于网络层次结构的信息;

Girvan-Newman算法的缺点

  1. 在计算边介数的时候可能会有很多重复计算最短路径的情况,时间复杂度太高;
  2. 若无法知道应该划分社团的数量,算法效果会相对较差;

总而言之,Girvan-Newman算法不必依赖多余的信息来判断得到的社团结构是否具有实际意义,而是可以直接从网络的拓扑结构来进行分析。

但是该算法的耗时比较大,时间复杂度为O(mn(m+n))O(mn(m+n)),因此它仅仅适用于中等规模的复杂网络(n10000)(n≤10000)