Infomap社区检测理解

Question

我需要一个可理解的Infomap社区检测算法的描述.我看过报纸,但对我来说并不清楚.我的问题:

1. 算法基本上如何工作？
2. 什么随机散步呢？
3. 什么是地图方程式,(明确地)与模块化优化的区别是什么？(图3中的论文给出了一个例子,但我没有得到)
4. 在他们的主页上,有两个改进.第一个是子模块运动,第二个是单节点运动.为什么使用它们以及为什么合并的模块不能分离？

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

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

Answer 1

InfoMap算法背后的基本思想是将图的社区分区用作霍夫曼代码，该霍夫曼代码可压缩有关探索图的随机步行者的信息。

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

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

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

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