社区发现算法的一种，基于信息论的Infomap算法

02.Infomap算法

​ Infomap是一款实现于Map Equation理论上的网络聚类算法，它能够高效地识别复杂网络中的信息流模式，由Martin Rosvall和Carl T. Bergstrom于2008年提出。它通过优化信息流来描述网络中的社区结构，被认为是当前最有效的社区发现算法之一。

目前作者仍有维护这个算法的官网 mapequation.org - code (opens new window)

核心思想

Infomap将网络中的社区发现问题转化为信息编码问题，其基本思想是：

1. 随机游走模型：将网络看作信息流动的通道，假设信息（或随机游走者）在网络中流动。
2. 两级编码：使用Huffman编码的思想，为频繁访问的节点（社区内部）分配短编码，为不频繁访问的节点（社区间转移）分配长编码。
3. 最小化描述长度：寻找社区划分，使得描述随机游走路径的平均编码长度最小。

数学原理

Infomap试图最小化的目标函数是Map方程：

$L(M)=qH(Q)+{\Sigma }_{i=1}^m{p}^{i}H(P^i)$

其中：

• M表示网络划分
• q是社区间转移的概率
• H(Q)是社区间转移的熵
• p^i是社区i内的访问概率
• H(P^i)是社区i内的熵

算法步骤

1. 初始化：将每个节点视为一个独立社区
2. 计算当前划分的编码长度
3. 尝试不同的节点移动或社区合并
4. 接受能最大程度减少编码长度的改变
5. 重复直到编码长度不再显著减少

文字写于：广东