r - igraph中的社区检测算法有什么区别？

Question

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

我想确定更可能存在联系的顶点组。我的计划是然后使用混合模型来预测使用顶点和组属性的组内连接顶点的数量。

有些人可能想回应我项目的其他方面，这会很棒，但我最感兴趣的是有关 igraph 中用于对顶点进行分组的函数的信息。我遇到过这些 community detection algorithms但我不确定它们的优缺点，或者其他一些功能是否更适合我的情况。我看到了链接 here同样，但它们并非特定于 igraph。谢谢你的建议。

Answer 1

以下是有关当前在 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个社区，尽管您可以将c设置为高达200，这可能足以满足您的目的。 2) 最终可能会少于 c 个社区，因为一些自旋状态可能会变空。 3) 不能保证网络中完全远程(或断开连接)部分的节点具有不同的自旋状态。这更可能是断开连接图的问题，所以我不会担心。该方法不是特别快，也不是确定性的(因为模拟本身)，但具有确定簇大小的可调分辨率参数。 Spinglass 方法的一个变体也可以考虑负链接(即端点更喜欢在不同社区中的链接)。

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

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

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

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