‘networkcommunites’（网络社区）（二）（louvain算法实现）（全站最详细）

引言&＃xff1a;

在&＃xff08;一&＃xff09;中我们学习到了什么是‘network communites’&＃xff08;网络社区&＃xff09;及其目标函数Q的求取&＃xff0c;接下来我们要说明的是&＃xff0c;我们要通过怎样的算法来实现将你的网络分成若干个集群。

一&＃xff1a;louvain算法的大体介绍&＃xff1a;

我们这里用到的把网络划分成若干个集群的算法就是louvain算法。

它有几个优势&＃xff1a;

&＃xff08;1&＃xff09;&＃xff1a;louvain算法被广泛应用。

&＃xff08;2&＃xff09;&＃xff1a;它可以快速实现集群的划分。

&＃xff08;3&＃xff09;&＃xff1a;集群的结果很好。

&＃xff08;4&＃xff09;&＃xff1a;在实践中的表现很好。

二&＃xff1a;实现louvain算法的两个步骤&＃xff1a;

&＃xff08;1&＃xff09;&＃xff1a;最大化Modularity&＃xff08;也就是Q函数&＃xff09;

首先&＃xff0c;我们输入进一个原始网络&＃xff0c;将其中的每一个节点看做是一个‘community’。

然后&＃xff0c;对于其中任意一个节点&＃xff0c;louvain算法将做以下两个步骤&＃xff1a;

&＃xff08;1&＃xff09;&＃xff1a;假如选定节点i&＃xff0c;对节点i的每一个邻居节点j计算出&＃xff08;下面详细步骤会说明这个计算&＃xff09;

&＃xff08;2&＃xff09;:   把节点i移动到计算出最大的的邻居节点j当中&＃xff0c;使节点i&＃xff0c;j成为一个新的‘community’。

&＃xff08;2&＃xff09;&＃xff1a;把识别出来的‘community’聚合

三&＃xff1a;具体步骤实现&＃xff1a;

&＃xff08;1&＃xff09;&＃xff1a;最大化Modularity&＃xff08;也就是Q函数&＃xff09;

如下图&＃xff1a;

Q的计算就是把节点i从集群D转移到集群C对网络Modularrity&＃xff08;Q函数在作者&＃xff08;一&＃xff09;中讲到的目标函数&＃xff09;的变化&＃xff0c;其中可分成两个公式&＃xff0c;一个是把节点i移除集群D中的Q变化&＃xff0c;另一个是将节点i移到新的集群C中Q的变化。&＃xff08;因为这两个步骤相似&＃xff0c;所以下文中只提到将节点i移到新的集群C中Q的变化的实现&＃xff09;。

如下图&＃xff1a;

计算要&＃x1d71f;&＃x1d478; &＃xff08;&＃x1d48a; → &＃x1d46a;&＃xff09;首先我们要定义两个新的量

&＃x1d72e;&＃x1d48a;&＃x1d48f;&＃xff1a;就是在集群c内部的边有几条

&＃x1d72e;&＃x1d495;&＃x1d490;&＃x1d495;&＃xff1a;就是在集群c内部所有节点的边数

&＃xff08;具体形式如图中的黑粗边&＃xff09;

然后我们有如图中的公式&＃xff1a;

ps&＃xff1a;第一个恒等于号后面的函数是我们在&＃xff08;‘network communites’&＃xff08;一&＃xff09;&＃xff09;中定义的对每个集群的的模块化程度&＃xff08;Modularity&＃xff09;&＃xff0c;而第二个等于号后面的式子是将前面的式子的展开&＃xff0c;而第三个等于号后面用我们上面的定义替换。

以上第一步算出来了Q&＃xff08;C&＃xff09;接下来还需要定义两个量&＃xff1a;

如图&＃xff1a;

&＃x1d48c;&＃x1d48a;,&＃x1d48a;&＃x1d48f;:你要添加进集群C的节点i与集群c中节点的连接边的数量。

&＃x1d48c;&＃x1d48a; &＃xff1a;指节点i所有的边的数量

&＃xff08;具体形式如图中的黑粗边&＃xff09;

这样我们就可以得出如下图公式&＃xff1a;

和是节点i插入集群C前后的模块化程度的变化&＃xff0c;

Q&＃xff08;C&＃xff09;中我们上文已经得到

Q&＃xff08;{i}&＃xff09;是由目标函数Q定义而来&＃xff0c;第一项因为把节点i作为一个小的‘community’其内部没有边&＃xff0c;所以为0&＃xff0c;第二项因为小‘community’内部只有i一个节点所以没有&＃xff0c;只有.

Q(C&＃43;{i})中绿色框的位置是因为节点i的加入而导致集群c中的内部边&＃x1d72e;&＃x1d48a;&＃x1d48f;和全部边&＃x1d72e;&＃x1d495;&＃x1d490;&＃x1d495;的变化导致的变化

所以我们可以得到下图中第一个式子&＃xff1a;

然后将第一个式子和第二个式子相加得到第三个式子。

最后将节点i对每个集群计算的结果进行比对&＃xff0c;结果最大的就把节点i加入到那个集群中。

&＃xff08;2&＃xff09;&＃xff1a;把识别出来的‘community’聚合

在&＃xff08;1&＃xff09;步骤中&＃xff0c;我们已经把集群都展示出来了&＃xff0c;在&＃xff08;2&＃xff09;步骤中&＃xff0c;我们就把属于每一个集群的所有节点都融入到一个‘super node’&＃xff08;超级节点&＃xff09;&＃xff08;每一个集群一个&＃xff09;。

四&＃xff1a;效果图

如下图是经过一轮louvain算法后的集群效果图&＃xff1a;