infomap从随机游走的角度实现网络的模块划分假设我们要描述一个随机游走者在网络上的活动每走一步我们都要增加游走过程的编码长度即visit的节点编码每个节点的编码都独一无二如果说都是使用0/1编码那节点越多自然就会存在更多长编码的节点。久而久之要编码一个随机游走信息流它的编码长度就可能非常大 (图1。为了降低编码长度我们可以利用随机游走在节点间运动的规律随机游走可能在长期在某几个节点组成的群之间跳跃然后又跳到另一个节点群在那个节点群之内移动。那么我们可以给这些随机游走者经常“光顾”的节点群一个编码可以理解为“小区号”而节点群内每个节点就可以有一个“门牌号”。在每一个“小区”内“门牌”都是可以复用的这样就可以去缩短整体的编码长度没有必要每个节点都有一个独一无二的编号图2。这个就是infomap的思想看基于怎样的模块可以最小化随机游走过程中的编码长度。这样的一个方法可以发现随机游走经常在哪些节点之间游走自然这样的节点群可以被认为是“模块”。图1不进行模块划分的随机游走描述图2使用模块划分的随机游走描述方式具体怎么做infomap设计了几类事件进入某个模块在模块内visit某个节点退出某个模块。假设给每个具体事件一个用0/1构成的编码huffman编码原则就是让高频事件编码短低频事件编码长这样就可以让随机游走的平均编码长度最低。事件编码长度的理论下限就是它的自信息然后一组事件的平均事件编码长度就是熵。infomap就是要最小化一个损失函数L(M):这个损失函数代表了随机游走者在图中每走一步平均增加的编码长度。首先看前面一部分熵率这一部分代表了在模块间切换事件的平均编码长度贡献q左箭头这个qi 左箭头就是随机游走者下一步进入i模块的概率pβ是稳态下随机游走者处于β节点的概率pβ-α是从β到α一步到达的概率。H(Q)就是转移到每个模块的不确定性熵后面一部分熵率这部分是在模块内进行切换或者退出模块的平均编码长度贡献。这个变量是在模块i内发生事件的概率之和pα就是随机游走处于α节点的稳态概率q右箭头就是退出i模块的概率i模块内发生事件的熵直观来说最小化L就是在随机游走在模块内和模块间的事件切换不确定性进行一个权衡如果每个节点都各自为政自然模块内的切换不确定性就很低但是这样模块间的就很高但如果所有节点都在同一模块虽然没有模块间的切换但是模块内切换不确定性又很高了。我觉得为什么最小化L可以实现合理的模块划分1.L最小化模块间切换的概率(q左箭头)可能低对应L前面一项从一个模块退出(qi 右箭头)的概率也可能低qi 右箭头低模块内事件的熵及熵率可能也就低了对应L后面一项。这样体现了随机游走者是长期处于这些划分出来的模块内的。2.L最小化务求让模块内切换不确定性和模块间切换不确定性整体最低infomap手册原文The optimal network partition corresponds to a modular code structure that balances the cost of specifying movements within and between modules这样可能就得到一个适中分辨率的模块划分。infomap还会使用teleportation机制来避免信息流在有向网络中走到“死胡同”离开不了当前节点。这样可能会导致稳态概率依赖于信息流的起点。具体来说可以把稳态概率写成前面一部分就还是正常的沿边游走。后面一项就是每一步从其它节点”突然“移动到当前节点α这个概率和这个节点的入度呈正比。 这个稳态概率可以用迭代法计算。具体怎么最大化L函数思想和鲁汶算法差不多首先每个节点单独作为一个模块。之后按照随机顺序将每个节点迁移至其它节点构成的模块使L降幅最大如果任何迁移操作都无法降低映射方程该节点保留在原有模块。然后将上一层得到的模块作为本层的新节点并且和上一层操作完全一致对新节点进行模块合并。不断迭代这种分层网络重构直到L无法继续降低。研究者还会引入以下两种机制来避免鲁汶进入局部最优1.子模块迁移Submodule movements。首先把每个聚类簇单独看作一个网络在该子网络上运行核心算法。该过程会为每个原始模块生成一个或多个子模块。之后将所有子模块放回上一步对应的原始模块但允许各个子模块在不同模块之间自由迁移运行类鲁汶算法。2.单节点迁移Single-node movements。首先将每个节点重新独立成模块实现单节点可迁移。随后把所有节点放回上一步对应的原始模块。允许各个独立节点在不同模块之间自由迁移运行类鲁汶算法。