社区发现 louvain(fast unfolding)算法_fast unfolding louvain

整个算法是基于Modularity的计算，然后就是迭代，社区改变，然后收缩，继续迭代，社区改变，然后收缩，如此以往。
这里贴上算法的流程：

算法形式化描述
1）初始化：
将图中的每个节点看成一个独立的社区，社区的数目与节点个数相同；

2）开始first phase迭代 - 社区间节点转移：
对每个节点i，依次尝试把节点 i 分配到其每个邻居节点所在的社区，计算分配前与分配后的模块度变化ΔQ

3）重复2）- 继续进行社区间节点转移评估：
直到所有节点的所属社区不再变化，即社区间的节点转移结束，可以理解为本轮迭代的 Local Maximization 已达到；

4）second phase - Rebuilding Graph：
因为在这轮的first phase中，社区 C 中新增了一个新的节点 i，而 i 所在的旧的社区少了一个节点，因此需要对整个图进行一个rebuild。

对图进行重构，将所有在同一个社区的节点重构成一个新社区，社区内节点之间的边的权重更新为新节点的环的权重，社区间的边权重更新为新节点间的边权重；

5）重复2）- 继续开始下一轮的first/second phase：
直到整个图的模块度不再发生变化。
（https://www.cnblogs.com/LittleHann/p/9078909.html）

然后其实关于louvain算法，基本理解用自己的话来重复一遍。
每次找一个节点，算它分配到邻居的社区的ΔQ，将其改为选最大的的那个社区，这样找一轮下来，（不过不知道这里是同步还是异步的，应该是同步的，及时改变及时用），一轮找下来，每个节点所属的社区肯定有所变化，再来一轮，再来一轮，直到现在的Q不会再改变，即每个节点的所属社区不再变化，则进入第二阶段。
第二个阶段是将之前形成的社区缩成一个节点，比如原本网络中有200个节点（初始是每个节点一个社区），经过了第一个阶段，形成了45个社区，那么第二阶段就会将整个网络转化成45个节点的网络（依然是每个节点一个社区），社区内的边权变成该节点的自环。从而转换完成。
下面继续进行第一阶段，直到不变。
然后再第二阶段，直到不变。

至于louvain算法能够检测层次性社区，是因为比如对于社区1，它在第一阶段之后，它有20个节点，然后在第二阶段缩成一个节点，依然代表社区1。然后继续第一阶段。然后发现此时有社区1有3个节点。那么社区1就有层次性了，其中一开始20个是第一层，而后来新增的两个节点包含的多个节点就是第二层了。如是便是层次性的体现。

在算法执行过程中，很明显的就是一开始较为复杂，因为涉及到的节点多，每次都要计算与改变到邻接节点的ΔQ，计算量比较大。
而一旦涉及到第二阶段，再执行第一阶段，所有的节点和边的数目就变小了，所以计算量会变小。
总体来看，越往后，计算量越来越小。