[科普中国]-基于信息论的社团发现算法

Martin Rosvall1等人基于信息论提出了Infomap算法。该算法使用随机游走作为网络上信息传播的代理，网络上的随机游走会产生相应的数据流。随机游走产生的信息量使用平均一步随机游走产生的码字长度衡量，即平均码字长度。为了最大的压缩平均码字长度，需要开发有效的编码方法。霍夫曼编码是一种常用的编码方式，在示例图上使用该编码，分配较短的码字给随机游走经常访问的节点，香浓信源编码理论给出了霍夫曼编码码字长度的理论界限：每一步的平均码字长度不低于变量X的熵。其中，变量X的样本空间是网络所有节点的集合，X的概率分布为网络所有节点被随机游走访问的频率分布。由于霍夫曼编码没有利用网络结构的规律性，所以该平均码字长度仍然比较长。为了进一步压缩信息流的编码长度，可以考虑使用突出网络社区结构的二级编码。

这个规则类似于地图上的命名规则，社区类似于城市，节点类似于城市里的街道，不同的城市里的街道可以同名，同一个城市里的街道不能同名。将随机游走访问社区或者节点的频率分布作为变量的概率分布，社区的码字和每个社区内部节点的码字都使用霍夫曼编码。每次随机游走跨越不同的社区时，需要在描述中加上前一个社区的离开码和后一个社区的码字，以表示随机游走所处的社区发生了变化。直观上看，如果社区的划分较好，则随机游走者在某个社区内部游走的概率将较大，跨越社区的概率将较小，因此使用社区编码和离开码的概率将较小，同时由于两级编码降低了每个节点的码字长度，因此信息流的平均码字长度将会被压缩。二级编码方法将网络的社区划分问题转化成了最优编码问题：寻找网络的一个最优划分，使无限随机游走的平均描述长度最小。这里，描述长度包括两个部分：随机游走者在社区内部游走时节点的码字长度和跨越社区时社区的码字长度。显然，如果社区划分较好，那么随机游走在社区间的转移频率就比较低，从而使描述中社区的平均码字长度较低，同时，节点的码字长度因为二级编码被大大降低，因此总的描述长度就会被大大的压缩。相反，如果社区没有被很好的划分，社区间的转移将会很频繁，从而二级编码将不能压缩随机游走的描述长度。

假设给定网络的一个社区划分M，将网络的n个节点划分到m个社区中，则网络上无限随机游走每一步的平均描述长度L（M）为：

H(Q)+pH(P)

称为map等式。其中，第一项q H（Q）表示在社区间转移所需要的平均码字长度，第二项H（P）表示在所有社区内游走的平均码字长度。网络社区发现的目标就是在所有可能的社区划分中，找出使平均描述长度L（M）最小的划分作为网络最优的社区划分。

采用贪心算法寻找最优划分，即开始时为每个节点分配一个独立的社区，合并使平均描述长度L（M）下降最多的两个社区，重复这个过程，直到最后合并成一个社区。算法的具体的步骤如下所述：

（1）去掉网络中所有的边，网络的每个节点都单独作为一个社区；

（2）网络中的每个连通部分作为一个社区，将还未加入网络的边分别重新加回网络，如果加入网络的边连接了两个不同的社区，即合并了两个社区，则计算形成的新的社区划分的平均描述长度的减少量。选择使平均描述长度减少最大的两个社区进行合并；

（3）如果网络的社区数大于1，则返回步骤 （2） 继续迭代，否则转到步骤 （4） ；

（4）遍历每种社区划分对应的平均描述长度的值，选取平均描述长度最小的社区划分作为网络的最优划分。