igraph社区检测algorithm有什么区别？
我有一个约100个igraph对象的列表，其中包含约700个顶点和3500条边的典型对象。
我想确定哪些关系更有可能的顶点组。 我的计划是使用混合模型来预测有多less组内关系顶点使用顶点和组属性。
有些人可能想回应我的项目的其他方面，这将是伟大的，但我最感兴趣的是有关igraph函数的信息分组顶点的信息。 我遇到了这些社区检测algorithm，但是我不确定它们的优缺点，还是其他function对我的情况会更好。 我也看到了这里的链接，但它们并不是特定于igraph。 谢谢你的build议。
以下是igraph当前实现的社区检测algorithm的简短摘要：
-
edge.betweenness.community是一个层次分解过程，其边缘以其边缘介数分数（即通过给定边的最短path的数量）的递减顺序被去除。 这是因为连接不同群体的边缘更可能被包含在多个最短path中，这是因为在很多情况下，它们是从一个群组到另一个群组的唯一select。 这种方法产生了很好的结果，但是由于边缘介数计算的计算复杂性以及因为必须在每一个边缘去除之后重新计算介差值，所以速度很慢。 具有〜700个顶点和〜3500个边的图是围绕着可以用这种方法进行分析的图的上限大小。 另一个缺点是edge.betweenness.communitybuild立了一个完整的树状图，并没有给你任何关于在哪里削减树状图以获得最终组的指导，所以你必须使用其他一些措施来决定（例如模块化在树状图的每个级别的分区得分）。 -
fastgreedy.community是另一种分层次的方法，但它是自上而下的，而不是自上而下的。 它试图以贪婪的方式优化称为模块化的质量函数。 最初，每个顶点属于一个单独的社区，并且迭代地合并社区，使得每个合并在局部最优（即产生当前的模块性值的最大增加）。 当不可能增加模块性时，algorithm停止，所以它给你一个分组以及一个树形图。 该方法是快速的，这是通常尝试作为一个近似的方法，因为它没有参数调整。 但是，已知会遭受分辨率限制，即低于给定大小阈值的社区（如果我没有记错的话，取决于节点和边缘的数量）将总是与邻居社区合并。 -
walktrap.community是一种基于随机散步的方法。 一般的想法是，如果你在图上进行随机游走，那么散步更有可能停留在同一个社区内，因为只有less数边缘在特定社区之外。 Walktrap运行3-4-5个步骤（取决于其中一个参数）的短随机步行，并使用这些随机游走的结果以自下而上的方式合并单独的社区，如fastgreedy.community。 再次，您可以使用模块化分数来select切割树状图的位置。 它比快速贪婪的方法慢一点，但也更准确一些（根据原始出版物）。 -
spinglass.community是基于所谓Potts模型的统计物理学方法。 在这个模型中，每个粒子（即顶点）可以处于c个自旋状态中的一个，并且粒子之间的相互作用（即图的边缘）指定哪些顶点希望保持相同的自旋状态，哪些喜欢有不同的自旋状态。 然后模拟一个给定的步数，粒子的自旋态最终定义了团体。 结果如下：1）最终将不会超过c个社区，尽pipe你可以将c设置为200，这对于你的目的来说可能是足够的。 2）由于一些旋转状态可能变空，所以最终可能会less于C族。 3）不能保证networking中完全远程（或不连续）部分的节点具有不同的自旋状态。 这更可能是一个孤立的graphics只是一个问题，所以我不会担心这一点。 该方法不是特别快速且不确定（因为模拟本身），但是具有决定簇大小的可调parsing参数。 spinglass方法的一个变体也可以考虑到负面链接（即terminal喜欢在不同社区的链接）。 -
leading.eigenvector.community是一种自顶向下的分层方法，可以再次优化模块化function。 在每个步骤中，图表分成两个部分，分离本身会显着提高模块性。 分裂是通过评估所谓的模块性matrix的主导特征向量来确定的，并且还存在阻止紧密连接的组进一步分裂的停止条件。 由于涉及到特征向量计算，所以在ARPACK特征向量求解器不稳定的退化图上可能不起作用。 在非简并图上，它可能产生比快速贪婪方法更高的模块化分数，虽然速度稍慢。 -
label.propagation.community是一个简单的方法，其中每个节点被分配k个标签之一。 然后该方法迭代地进行，并且以每个节点以同步方式获取其邻居的最频繁标签的方式将标签重新分配给节点。 当每个节点的标签是其邻居中最频繁的标签之一时，方法停止。 它的速度非常快，但在初始configuration（随机决定）的基础上产生不同的结果，因此应该多次运行该方法（比如说，graphics1000次），然后构build一个共识标签，乏味。
igraph 0.6还将包含最先进的基于信息理论原理的Infomap社区检测algorithm; 它试图build立一个分组，它为graphics上的随机游走提供了最短的描述长度，其中描述长度由编码随机游走path所需的每个顶点的期望位数来度量。
无论如何，我可能会与fastgreedy.community或walktrap.community作为第一个近似值，然后评估其他方法，当事实certificate，这两个由于某种原因不适合特定的问题。
不同的社区检测algorithm的总结可以在这里find： http : //www.r-bloggers.com/summary-of-community-detection-algorithms-in-igraph-0-6/
值得注意的是，InfoMAPalgorithm是最近的新手，可能是有用的（它也支持有向图）。
