生物医学网络科学Biomedical Network Science
社团结构与社区发现08 / 19

映射方程与 Infomap

阅读
约 3 分钟

社团是“流”停留的地方

模块度和 SBM 都从连边的分布出发定义社团。Rosvall 与 Bergstrom（2008）换了一个角度：许多网络承载着“流”——信号在通路中传递、信息在脑区间流动、引文从一篇论文流向另一篇。若一个随机游走者进入某组节点后往往要停留很久才离开，这组节点就是一个社团。他们把“找社团”变成一个数据压缩问题：要把随机游走者的轨迹编码成尽量短的比特串，最好的编码方式就会揭示社团结构。

两层编码与映射方程

用类似地图的方式编码轨迹：每个模块内部有一本模块码本，给模块内的节点分配短码，同一个短码可以在不同模块中重复使用（就像不同城市可以有同名的街道）；另有一本索引码本，只在游走者进入一个新模块时使用，记录进入了哪个模块；每本模块码本中再有一个退出码，表示离开当前模块。若社团划分得好，游走者大部分时间在模块内部，只用短的模块码本；跨模块的“索引 + 退出”开销很少出现。

映射方程（map equation）：对划分 MM，描述随机游走每一步所需的平均码长下界为 L(M)=qH(𝒬)+∑i=1ncpiH(𝒫i),L(M)=q\,H(\mathcal Q)+\sum_{i=1}^{n_c}p_i\,H(\mathcal P_i), 其中 q=∑iqiq=\sum_i q_i 为每一步“进入某个模块”的概率（使用索引码本的频率），H(𝒬)H(\mathcal Q) 为索引码本的熵；pi=qi+∑α∈ipαp_i=q_i+\sum_{\alpha\in i}p_\alpha 为使用模块 ii 码本的频率（模块内节点的访问概率加上退出概率），H(𝒫i)H(\mathcal P_i) 为模块码本的熵。熵以 2 为底，单位为比特。

对无向无权网络，随机游走的稳态访问概率 pα=kα/2mp_\alpha=k_\alpha/2m，模块 ii 的退出概率 qiq_i 等于它的外连边数除以 2m2m。把熵展开后，L(M)L(M) 只依赖于 qiq_i、pαp_\alpha 两类量（数学推导与算法）。Infomap 就是最小化 L(M)L(M) 的算法：先用与 Louvain 相似的局部移动和聚合，再加入子模块移动、单节点移动等细化步骤，复杂度与 Louvain 同量级。

小例子：空手道网络中，所有节点放在一个模块时 L=4.70L=4.70 比特（即节点访问分布的熵）；按真实两派划分时 L=4.46L=4.46 比特；用 Louvain 的 4 社团划分时 L=4.34L=4.34 比特（代码示例）。划分越能“困住”游走者，描述越短。

与模块度的区别

  • 有向与加权网络：映射方程天然使用有向网络上的流（对有向网络需加入“传送”以保证游走遍历，类似 PageRank），而有向模块度只看边的密度。在引文网络、信号转导网络、有效连接网络中，二者可能给出明显不同的结果。
  • 分辨率：映射方程不使用配置模型零模型，在“团组成的环”这一构造中，即使团数很多也偏好把每个团分开，而模块度会合并相邻团（代码示例）。但它并非完全没有分辨率限制：模块很多、跨模块流很大时，索引码本的开销也会促使合并。
  • 随机网络：在没有结构的网络上，最优 LL 往往对应单一模块，Infomap 倾向于不报告虚假社团；但这只是经验行为，不是统计检验。
  • 层次与重叠的推广：多层映射方程（Rosvall 与 Bergstrom 2011）用嵌套的码本描述层次模块；带“记忆”的高阶版本可以让同一个节点在不同流动路径中属于不同模块，从而得到重叠社团。

基准测试中，Infomap 与 Louvain 都属于表现最好的一类方法（Lancichinetti 与 Fortunato 2009）。Power 等（2011）对静息态功能脑网络划分功能系统时，使用的正是 Infomap。

其他基于动力学的方法

  • 马尔可夫稳定性（Markov stability，Delvenne、Yaliraki 与 Barahona 2010）：用“随机游走在时间 tt 后仍留在起始社团的概率超出随机期望的程度”作为质量函数，马尔可夫时间 tt 起分辨率参数的作用，在特定的线性化极限下与模块度对应；扫描 tt 可以得到多尺度划分。
  • 标签传播（label propagation，Raghavan 等 2007）：每个节点反复采用邻居中最常见的标签，直到收敛。几乎线性时间，但结果高度依赖随机顺序，且在社团不清晰时可能整体塌缩为一个社团。

继续阅读