9

我正在使用igraph包中的 InfoMap 算法对有向和非加权图（34943 个顶点，206366 个边）执行社区检测。在图中，顶点代表网站，边代表网站之间是否存在超链接。

我在运行该算法后遇到的一个问题是，大多数顶点都属于一个庞大的社区（32920 或 94%）。其余的顶点分散到数百个其他小社区中。

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

我感到相当恼火，因为算法的运行时间相当长，所以我每次都必须等待结果（还没有运气！！）。

非常感谢。

4

2 回答 2

8

感谢所有优秀的评论。最后，我通过下载并运行 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

于 2013-12-05T03:21:26.807 回答
5

我打算把它放在评论中，但它最终太长而且很难以这种格式阅读，所以这是一个切线相关的答案。

您应该做的一件事是评估算法在寻找社区结构方面是否做得很好。您可以尝试可视化您的网络以建立：

  1. 算法返回的社区结构是否有意义？也许有一个庞大的社区？
  2. 如果不是，可视化是否提供了关于为什么的洞察力？

这将有助于告知您接下来的步骤。也许网络的结构需要不同的算法？

我发现对大型网络有用的一件事是将边缘绘制为热图。如果您将边缘存储在邻接矩阵中，这很容易做到。

为此，您可以使用该image函数，将边矩阵作为参数传递z。希望这将使您能够直观地看到社区结构。

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

需要注意的另一件事是，如果您的边缘是定向的，则可能更难以通过肉眼评估，因为边缘可能出现在热图对角线的任一侧。您可以做的一件事是绘制underlying graph- 即假设您的边缘是无向的邻接矩阵。

如果你的算法做得很好，你会期望看到沿对角线的方块，每个检测到的社区都有一个方块。

于 2013-12-04T04:34:22.170 回答