我需要一个Infomap社区检测算法的易于理解的描述。我读了论文,但对我来说还不清楚。我的问题:

  • 该算法基本如何工作?
  • 它与随机游走有什么关系?
  • 什么是映射方程,并且(显然)与模块化优化有什么区别? (在图3的论文中给出了一个示例,但我没有得到)
  • 在他们的主页上,有2个改进。第一个是子模块运动,第二个是单节点运动。为什么使用它们,为什么合并的模块不可分离?

  • 主页:
    http://www.mapequation.org/code.html

    论文:
    http://www.mapequation.org/assets/publications/EurPhysJ2010Rosvall.pdf

    最佳答案

    InfoMap算法背后的基本思想是将图的社区分区用作Huffman code,它压缩有关探索图的随机步行者的信息。

    让我们解开这意味着什么。中心对象是随机步行者,其探索网络的可能性是步行者在其马尔可夫转移矩阵给定的两个节点之间转移。至此,我们已经为每个节点使用单独的代码字对网络进行了有效编码。但是,在大多数现实世界的网络中,我们知道网络中存在某些区域,因此一旦随机步行者进入某个区域,它就会在该区域停留很长时间,并且区域之间的移动相对很少。这使我们能够将代码字组合成霍夫曼代码:我们可以为每个区域使用前缀代码,然后为模块内的每个节点使用唯一的代码字,但是我们可以为每个模块重用这些节点级别的代码字。通过查看街道名称可以收集到相同的直觉。在美国每条街道都有一个唯一的街道名称会很疯狂,相反,我们使用州和城镇,然后指定街道名称,从而允许我们在城镇之间重用街道名称(那里有几条主要街道?)。

    这是优化算法出现的地方:当您使用的模块太少时,您实际上仍然回到为每个节点使用单独的代码字的水平,但是使用了太多的模块,并且前缀代码的数量变得太大了。因此,我们需要找到一个将节点分配给模块的最佳分区,以使压缩我们的随机步行者的运动所需的信息最小化(从他们的论文中得出方程式1)。

    可能的分区数量在节点数量(由Bell数给定)中呈指数级增长,因此无法进行强力搜索。相反,作者利用了Louvain method的一种变体(最初是为模块化最大化而设计的),以帮助他们找到合适的分区。您要问的2个``改进''(问题4)只是启发式方法,可帮助有效地探索分区空间:子模块探索检查可验证我们没有创建太大的模块,应该将其拆分成较小的模块,单节点移动允许单个节点在模块之间移动。

    InfoMap算法和Modularity都是最佳社区检测方法的实例:它们各自具有质量函数,然后搜索图形分区的空间以找到优化该质量函数的分区。区别在于质量功能:InfoMap专注于压缩随机助步器的运动所需的信息,而Modularity基于边缘密度(模块中的边缘多于偶然性)定义模块。

    10-07 13:37