问

使用InfoMap算法进行社区检测,生成一个大型模块

京江晚报经济民生部发布于 2023-02-13 08:29

算法

我正在使用igraph包中的InfoMap算法在有向和非加权图(34943顶点,206366边)上执行社区检测.在图中,顶点表示网站,边表示网站之间存在超链接.

我在运行算法后遇到的一个问题是,大多数顶点都具有单个大型社区的成员资格(32920或94%).其余的顶点分散在数百个其他小型社区中.

我已经尝试了不同的nb.trials参数设置(即50,100,现在运行500).但是,这似乎并未改变结果.

我感到相当恼怒,因为算法的运行时间非常高,所以我每次都要等待结果(没有运气!!).

非常感谢.

2 个回答

我打算把它放在评论中,但结果太长了,很难以这种格式阅读,所以这是一个切向相关的答案.

您应该做的一件事是评估算法是否在寻找社区结构方面做得很好.您可以尝试可视化您的网络以建立:
这有助于您了解后续步骤.也许网络结构需要不同的算法？

我认为对大型网络有用的一点是将边缘绘制为热图.如果将边存储在邻接矩阵中,这很容易做到.

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

但是,您还需要评估算法的正确性,因此您希望按照已分配给它们的社区对节点(邻接矩阵的行和列)进行排序.

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

如果您的算法做得很好,您可能会看到对角线上的方块,每个检测到的社区都有一个块.
2023-02-13 08:37 回答

梦幻星之海洋1997_643
感谢所有优秀的评论.最后,我通过下载并运行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

2023-02-13 08:38 回答

大华出入境

撰写答案

今天，你开发时遇到什么问题呢？

立即提问

热门标签