使用InfoMap算法进行社区检测，产生一个巨大的模块。

Question

我正在使用igraph软件包中的InfoMap算法对一个具有34943个顶点和206366条边的有向非加权图（顶点表示网站，边表示网站之间的超链接）进行社区检测。

然而，运行算法后遇到的问题是大多数顶点都属于单个大型社区（32920个，占94%）。其余的顶点被分散到数百个其他小型社区中。

我已经尝试了不同的nb.trials参数设置（即50、100，现在正在运行500），但结果并没有改变太多。

我感到相当沮丧，因为算法的运行时间相当长，每次都要等待结果（目前没有成功！）。

非常感谢。

- timothyjgraham

---

你尝试过可视化图表来查看预期的社区结构吗？也许可以尝试绘制整个网络的热力图，或者绘制结果社区结构的圆形图表——这将帮助你确定找到的社区结构是否正确，或者检测算法是否存在问题（并给出下一步的思路）。 - Scott Ritchie

嗨@Manetheran，感谢你的建议。我以前没有使用过热力图或圆形图。你能告诉我正确的包或函数吗？谢谢。 - timothyjgraham

我会建议尝试其他方法，看看它们的结果是否有意义。只是为了确保这不是实现中的错误。 - Gabor Csardi

@timothyjgraham 大多数社区检测方法仅支持无向图的原因之一是在有向图中不清楚“社区”的含义。InfoMap算法认为，当您在图上进行随机游走时，社区是一些难以逃离的东西，因此对于有向图来说是有意义的。基于模块化的算法则认为，社区是一个子图，其中包含比具有相同度数分布的随机图更多的边，但请注意，这完全忽略了边的方向。 - Tamás

我在这里有点晚了，但也试试multilevel.community。它可以扩展到非常大的图形（我目前正在使用它处理250万个边缘）。它还可以给你一个社区的层次结构，所以你不仅仅局限于它选择的具有最高模块度的单一结果。 - Zach

Answer 1

感谢所有出色的评论。最终，我通过下载并运行Infomap的源代码解决了问题，该代码可以在http://www.mapequation.org/code.html上获得。

由于许可证问题，最新代码尚未与igraph集成。

这解决了将太多节点“合并”为一个巨大的社区的问题。

具体来说，我从命令行中使用了以下选项：-N 10 --directed --two-level --map 感谢Infomap项目的Martin Rosvall提供详细的帮助以解决此问题。

对于有兴趣的读者，这里是更多关于此问题的信息：

当网络崩溃为一个主要群集时，往往是因为非常密集和随机的链接结构...在iGraph实现的定向网络代码中编码了传送。如果许多节点没有出站链接，则传送的影响可能很大，因为它会随机连接节点。我们在这里提供了新的代码：http://www.mapequation.org/code.html，可以聚类网络而不编码必须使动态遍历的随机传送。有关详细信息，请参见本文：http://pre.aps.org/abstract/PRE/v85/i5/e056107

- timothyjgraham

---

你能帮我看一下infomap代码吗？我遇到了错误1。 - academic.user

嗨，@academic.user，请您提供有关错误代码的更多信息。您能否提供有关您正在分析的图形的信息（例如，顶点/边数？是否定向？是否带权重？密度等）。此外，在发生错误时，您在做什么或尝试做什么。 - timothyjgraham

文件本身存在一些问题，我从Bitbucket上下载了它。现在它可以工作了，再次感谢您的回复。 - academic.user

抱歉 @timothyjgraham，我想知道您是否创建了一个多路输入数据以与infomap一起使用，请参见此问题：http://stackoverflow.com/questions/28818695/how-to-write-a-dataframe-graph-to-pajek-format - academic.user

Answer 2

我本来想把这个放在评论里，但是格式太长了，很难阅读，所以这是一个相关的答案。

你应该做的一件事是评估算法是否能够很好地找到社区结构。您可以尝试可视化您的网络以确定：

1. 算法是否返回有意义的社区结构？也许有一个巨大的社区？
2. 如果没有，可视化是否提供了为什么的见解？

这将有助于指导您的下一步。也许网络的结构需要不同的算法？

对于大型网络，我发现绘制边缘热图非常有用。如果您的边缘存储在邻接矩阵中，则可以轻松完成此操作。

为此，您可以使用image函数，将您的边缘矩阵作为参数z传递。希望这能让您通过眼睛看到社区结构。

但是，您还要评估算法的正确性，因此您需要按照它们被分配到的社区对节点（邻接矩阵的行和列）进行排序。

另一个要注意的问题是，如果您的边缘是有向的，则可能更难通过眼睛进行评估，因为边缘可以出现在热图的对角线两侧。您可以做的一件事是代替绘制底层图 - 假设您的边缘是无向的邻接矩阵。

如果您的算法表现良好，您应该期望看到沿对角线的正方形块，每个块代表一个检测到的社区。

- Scott Ritchie

---

你好，感谢您的建议。我尝试了通过绘制边缘邻接矩阵来生成热力图的方法 - '热度'主要集中在绘图区域的顶部10%左右的一个矩形区域内（即沿着y轴延伸的矩形块，从y轴顶部向下延伸约10%）。其余的绘图区域基本上是白色空间（只有一些小的热点，不超过几个像素大小）。 - timothyjgraham

算法似乎无法返回具有意义的社区结构。约95%的节点在单个社区中，其余5%主要各占据一个社区（即每个社区一个节点）。因此，每个节点要么在庞大的社区中，要么独自一个社区！我正在使用InfoMap算法，因为它支持有向图，而其他社区检测算法不支持。我尝试了Spinglass，它返回的社区是有意义的（总共7个社区） - 但它忽略了图的有向性。 - timothyjgraham