我需要 Infomap 社区检测算法的易于理解的描述。我读了报纸，但我不清楚。我的问题:
- 该算法的基本工作原理是什么？
- 随机游动与它有什么关系？
- 映射方程是什么？与模块化优化有什么(明显)区别？ (图3的论文中给出了一个例子，但我没看懂)
- 在他们的主页上，有 2 处改进。第一个是子模块运动，第二个是单节点运动。为什么使用它们以及为什么合并后的模块不可分离？
首页: http://www.mapequation.org/code.html
论文: http://www.mapequation.org/assets/publications/EurPhysJ2010Rosvall.pdf
最佳答案
InfoMap 算法背后的基本思想是使用图的社区分区作为 Huffman code压缩有关随机游走者探索您的图表的信息。
让我们解开这意味着什么。中心对象是探索网络的随机游走者，游走者在其马尔可夫转移矩阵给出的两个节点之间转移的概率。至此，我们已经使用每个节点的单独代码字有效地对我们的网络进行了编码。然而，在大多数现实世界的网络中，我们知道网络中存在这样的区域，随机游走者一旦进入一个区域，往往会在那里停留很长时间，区域之间的移动相对较少。这允许我们将代码字组合成霍夫曼代码:我们可以为每个区域使用前缀代码，然后为模块内的每个节点使用唯一代码字，但我们可以为每个模块重用这些节点级代码字。通过查看街道名称可以收集到相同的直觉；如果美国的每条街道都有一个唯一的街道名称，那将是疯狂的，相反，我们使用州和城镇，然后指定街道名称，允许我们在城镇之间重复使用街道名称(有多少条主要街道？)。
这里是优化算法出现的地方:当你使用太少的模块时，你实际上仍然回到为每个节点使用单独的代码字的水平，但使用太多的模块，前缀代码的数量变得太大。因此，我们需要找到一个最佳分区，将节点分配给模块，以使压缩随机游走者移动所需的信息最小化(他们论文中的等式 1)。
可能的分区数量在节点数量(由贝尔数给出)中呈超指数增长，因此不可能进行蛮力搜索。相反，作者利用了 Louvain method 的变体。 (最初是为模块化最大化而设计的)来帮助他们找到合适的分区。您询问的 2 个“改进”(问题 4)只是帮助有效探索分区空间的启发式方法:子模块探索检查以验证我们没有创建太大的模块并且应该被分解成更小的模块，而单节点移动允许单个节点在模块之间移动。
InfoMap 算法和 Modularity 都是最优社区检测方法的实例:它们都有一个质量函数，然后搜索图分区空间以找到优化该质量函数的分区。不同之处在于质量函数:InfoMap 侧重于压缩随机游走者运动所需的信息，而 Modularity 根据边缘密度定义模块(模块内的边缘比偶然预期的多)。
关于algorithm - Infomap社区检测理解，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/48528648/