infomap这个算法确实不好理解，所以独立开一章来学习。

首先回顾下louvain的算法实现过程：

而infomap的算法实现过程：

1、最开始，每个原始节点堪称一个独立的社区；

2、对图里的节点随机采样出一个序列，按顺序依次尝试将每个节点赋给邻居节点所在的社区，取平均比特下降最大时的社区赋给该节点，如果没有下降，该节点的社区不变；

3、重复步骤2直到平均每步编码长度收敛为止。

louvain和infomap都是遵循一种自下而上的思路，类似于凝聚聚类，而不同之处在于：

1、louvain使用模块度增益而infomap使用平均比特增益用于决定如何合并社区；

2、louvain遍历所有节点的邻节点而infomap则是通过random walk随机采样；

下面就来详细解释一下：

数据压缩与信息熵 - 阮一峰的网络日志​www.ruanyifeng.com

首先需要了解，信息熵（对，就是西瓜书的决策树那一章节里的那个信息熵，二者是完全相同的）和平均每步编码长度的关系。上述的文章写的非常清晰易懂，这里就不复制黏贴了，给定了关于数据压缩的背景，

信息熵=最小平均编码长度

原文来自：

最小熵原理（五）：“层层递进”之社区发现与聚类 - 科学空间|Scientific Spaces​kexue.fm

我们常说信息熵用于衡量事物的不确定性，信息熵越大则不确定性越小，早期的决策树通过分裂，是一个不断的降低信息熵，也就是降低不确定性的过程，而infomap则是从平均编码长度的角度来论述信息熵在该算法中的角色； 可以看到，数据中概率的分布越均匀（数据的不确定性越大），则理论最短平均编码越大，即信息熵越大。

而infomap 的设计目的，是为了：

Infomap 将社区发现同信息编码（数据压缩）联系到了一起。 一个好的社区划分，可以带来更短的编码。所以，如果能量化编码长度，找到使得长度最短的社区划分，那就找到了一个好的社区划分。

这是infomap的重要思想。（直观上来体会也比较让人好接受，假设我们没有划分社区，也就是假设每一个节点都是一个社区，那么对于人类的直观感受来说原始的图数据的混乱程度很高，信息熵大，如果说节点有序的划分为不同的社区，对于人类的直观感受来说原始的图数据的混乱程度就降低了）

注意，我们这里谈及的编码都是 二进制编码的形式，也就是编码的方式都是通过0，1的方式来进行编码的。

那么对于图数据来说，怎么去编码？刚接触的时候我的第一反应是，这怎么编码，每个节点都是独立的，这岂不是一个均匀分布？按照这个例子：

假设有100个节点，每个节点出现的概率是1/100，那么按照公式不是可以直接计算出来其最短平均编码长度了（信息熵）了吗。。。

但是实际上是这样的：

给定变量X，变量 X的样本空间是图上所有节点的集合， X的概率分布为网络所有节点被随机游走访问的频率分布

这意味着，图上的节点的概率分布不是直接通过统计的方法来计算的（如果通过这种方式计算，那么显然所有节点的出现概率都是1/n，n表示节点数量）节点的概率分布为网络所有节点被随机游走访问的频率分布。

---

太难了。。。先这样吧。。头看炸