88

我有一个大约 100 个 igraph 对象的列表，其中一个典型对象具有大约 700 个顶点和 3500 个边。

我想确定更有可能发生联系的顶点组。然后我的计划是使用混合模型来预测使用顶点和组属性有多少组内关系顶点。

有些人可能想回应我项目的其他方面，这很好，但我最感兴趣的是关于 igraph 中用于分组顶点的函数的信息。我遇到过这些社区检测算法，但我不确定它们的优缺点，或者其他一些功能是否更适合我的情况。我也看到了这里的链接，但它们并不特定于 igraph。谢谢你的建议。

4

2 回答 2

197

以下是关于当前在 igraph 中实现的社区检测算法的简短摘要：

  • edge.betweenness.community是一个层次分解过程，其中边缘按照边缘介数分数（即通过给定边缘的最短路径的数量）的递减顺序被移除。这是因为连接不同组的边更有可能包含在多个最短路径中，因为在许多情况下，它们是从一个组到另一个组的唯一选择。这种方法产生了很好的结果，但由于边缘介数计算的计算复杂性以及每次边缘去除后必须重新计算介数分数，因此速度非常慢。您的图具有约 700 个顶点和约 3500 条边，大约是可以用这种方法分析的图的大小上限。另一个缺点是edge.betweenness.community构建一个完整的树状图，并且没有给你任何关于在哪里切割树状图以获得最终组的指导，所以你必须使用其他一些措施来决定这一点（例如，每个级别的分区的模块化分数树状图）。

  • fastgreedy.community是另一种分层方法，但它是自下而上而不是自上而下。它试图以贪婪的方式优化称为模块化的质量函数。最初，每个顶点都属于一个单独的社区，并且社区被迭代合并，使得每次合并都是局部最优的（即在当前的模块化值中产生最大的增加）。当无法再增加模块化时，该算法就会停止，因此它会为您提供分组和树状图。该方法速度很快，并且由于没有要调整的参数，因此通常作为第一个近似值尝试该方法。然而，众所周知，它会受到分辨率限制的影响，即低于给定大小阈值的社区（如果我没记错的话，取决于节点和边的数量）将始终与相邻社区合并。

  • walktrap.community是一种基于随机游走的方法。一般的想法是，如果你在图上执行随机游走，那么游走更有可能留在同一个社区内，因为只有少数边在给定社区之外。Walktrap 运行 3-4-5 步的短随机游走（取决于其参数之一），并使用这些随机游走的结果以自下而上的方式合​​并单独的社区，例如fastgreedy.community. 同样，您可以使用模块化分数来选择切割树状图的位置。它比快速贪心方法慢一点，但也更准确（根据原始出版物）。

  • spinglass.community是一种来自统计物理学的方法，基于所谓的 Potts 模型。在这个模型中，每个粒子（即顶点）可以处于c个自旋状态之一，粒子之间的相互作用（即图形的边）指定了哪些顶点对更愿意保持相同的自旋状态以及哪些喜欢有不同的自旋状态。然后对给定数量的步骤模拟模型，最终粒子的自旋状态定义社区。后果如下： 1）虽然你可以将c设置为高达 200，但最终不会有超过c个社区，这可能足以满足你的目的。2) 可能小于c社区最终因为一些自旋状态可能会变空。3) 不能保证网络中完全远程（或断开）部分的节点具有不同的自旋状态。这更有可能只是断开连接图的问题，所以我不会担心。该方法不是特别快，也不是确定性的（因为模拟本身），但有一个可调节的分辨率参数来确定集群大小。spinglass 方法的一种变体也可以考虑负链接（即，其端点更喜欢位于不同社区中的链接）。

  • leading.eigenvector.community是一种自上而下的分层方法，再次优化了模块化功能。在每个步骤中，图被分成两部分，分离本身会显着增加模块化。拆分是通过评估所谓的模块化矩阵的前导特征向量来确定的，并且还有一个停止条件可以防止紧密连接的组被进一步拆分。由于涉及特征向量计算，它可能不适用于 ARPACK 特征向量求解器不稳定的退化图。在非退化图上，它可能比快速贪心方法产生更高的模块化分数，尽管它有点慢。

  • label.propagation.community是一种简单的方法，其中每个节点都分配有k个标签中的一个。然后该方法迭代地继续并以每个节点以同步方式获取其邻居的最频繁标签的方式将标签重新分配给节点。当每个节点的标签是其邻域中最频繁的标签之一时，该方法停止。它非常快，但会根据初始配置（随机决定）产生不同的结果，因此应该多次运行该方法（例如，一张图 1000 次），然后建立一个共识标签，这可能是乏味。

igraph 0.6 还将包括基于信息论原理的最先进的 Infomap 社区检测算法；它试图建立一个分组，为图上的随机游走提供最短的描述长度，其中描述长度由编码随机游走路径所需的每个顶点的预期比特数来衡量。

无论如何，当事实证明这两种方法由于某种原因不适合特定问题时，我可能会使用fastgreedy.community或作为第一个近似值，然后评估其他方法。walktrap.community

于 2012-02-28T09:00:20.490 回答
14

可以在此处找到不同社区检测算法的摘要：http ://www.r-bloggers.com/summary-of-community-detection-algorithms-in-igraph-0-6/

Notably, the InfoMAP algorithm is a recent newcomer that could be useful (it supports directed graphs too).

于 2013-11-01T00:57:47.467 回答