引言：

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

一：louvain算法的大体介绍：

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

它有几个优势：

（1）：louvain算法被广泛应用。

（2）：它可以快速实现集群的划分。

（3）：集群的结果很好。

（4）：在实践中的表现很好。

二：实现louvain算法的两个步骤：

（1）：最大化Modularity（也就是Q函数）

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

然后，对于其中任意一个节点，louvain算法将做以下两个步骤：

（1）：假如选定节点i，对节点i的每一个邻居节点j计算出（下面详细步骤会说明这个计算）

（2）:   把节点i移动到计算出最大的的邻居节点j当中，使节点i，j成为一个新的‘community’。

（2）：把识别出来的‘community’聚合

三：具体步骤实现：

（1）：最大化Modularity（也就是Q函数）

如下图：

 

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

如下图：

计算要𝜟𝑸 （𝒊 → 𝑪）首先我们要定义两个新的量

𝜮𝒊𝒏：就是在集群c内部的边有几条

𝜮𝒕𝒐𝒕：就是在集群c内部所有节点的边数

（具体形式如图中的黑粗边）

然后我们有如图中的公式：

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

以上第一步算出来了Q（C）接下来还需要定义两个量：

如图：

𝒌𝒊,𝒊𝒏:你要添加进集群C的节点i与集群c中节点的连接边的数量。

𝒌𝒊 ：指节点i所有的边的数量

（具体形式如图中的黑粗边）

这样我们就可以得出如下图公式：

和是节点i插入集群C前后的模块化程度的变化，

Q（C）中我们上文已经得到

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

Q(C+{i})中绿色框的位置是因为节点i的加入而导致集群c中的内部边𝜮𝒊𝒏和全部边𝜮𝒕𝒐𝒕的变化导致的变化

所以我们可以得到下图中第一个式子：

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

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

（2）：把识别出来的‘community’聚合

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

四：效果图

如下图是经过一轮louvain算法后的集群效果图：

五：系列传送门：

‘ network communites’（网络社区）（一）（介绍和目标函数的建立）_小林学编程的博客-CSDN博https://blog.csdn.net/weixin_57643648/article/details/123545748?spm=1001.2014.3001.5501

    https://blog.csdn.net/weixin_57643648/article/details/123652501https://blog.csdn.net/weixin_57643648/article/details/123652501