Tam*_*más 183
以下是目前在igraph中实施的社区检测算法的简短摘要:
edge.betweenness.community是一种分层分解过程,其中边缘以其边缘中介分数(即通过给定边缘的最短路径的数量)的递减顺序被移除.这是因为连接不同组的边缘更可能包含在多个最短路径中,这仅仅是因为在许多情况下它们是从一个组到另一个组的唯一选择.由于边缘中介性计算的计算复杂性,并且因为在每次边缘移除之后必须重新计算中间性得分,因此该方法产生良好的结果但是非常慢.具有~700个顶点和~3500个边缘的图形大约是可以使用此方法分析的图形的上限大小.另一个缺点是edge.betweenness.community构建一个完整的树形图,并没有给出任何关于在何处削减树形图以获得最终组的指导,因此您将不得不使用其他一些措施来确定(例如,分区的模块化分数)树形图的每个级别).
fastgreedy.community是另一种分层方法,但它是自下而上而不是自上而下.它试图以贪婪的方式优化称为模块化的质量功能.最初,每个顶点属于一个单独的社区,并且迭代地合并社区,使得每个合并是局部最优的(即,产生模块化的当前值的最大增加).当不可能再增加模块性时算法停止,因此它为您提供分组和树形图.该方法很快,并且它通常作为第一近似尝试,因为它没有要调整的参数.然而,众所周知,它具有分辨率限制,即低于给定大小阈值的社区(取决于节点和边缘的数量,如果我没记错的话)将始终与邻近社区合并.
walktrap.community是一种基于随机游走的方法.一般的想法是,如果您在图表上执行随机游走,那么步行更有可能保持在同一社区内,因为在给定社区之外只有少数边缘.Walktrap运行3-4-5步骤的短随机游走(取决于其中一个参数),并使用这些随机游走的结果以自下而上的方式合并单独的社区fastgreedy.community.同样,您可以使用模块化分数来选择剪切树形图的位置.它比快速贪婪方法慢一点,但也更准确一些(根据原始出版物).
spinglass.community是一种基于所谓的波茨模型的统计物理学方法.在这个模型中,每个粒子(即顶点)可以处于c自旋状态之一,并且粒子之间的相互作用(即图的边缘)指定哪些顶点对将更喜欢保持在相同的自旋状态以及哪些喜欢有不同的自旋状态.然后针对给定数量的步骤模拟模型,并且最终粒子的自旋状态定义社区.结果如下:1)最终永远不会超过c社区,尽管你可以将c设置为高达200,这可能足以满足你的需要.2)最终可能会有少于c个社区,因为一些自旋州可能变空.3)不能保证网络中完全远程(或不连接)部分的节点具有不同的自旋状态.对于断开连接的图形,这更可能是一个问题,所以我不担心这一点.该方法不是特别快且不具有确定性(因为模拟本身),但具有可调整的分辨率参数,用于确定簇大小.spinglass方法的变体还可以考虑负链接(即,其端点更喜欢在不同社区中的链接).
leading.eigenvector.community是一种自上而下的分层方法,可以再次优化模块化功能.在每个步骤中,图表被分成两部分,分离本身会使模块性显着增加.通过评估所谓的模块化矩阵的前导特征向量来确定分裂,并且还存在阻止紧密连接的组进一步分裂的停止条件.由于涉及特征向量计算,它可能不适用于ARPACK特征向量求解器不稳定的退化图.在非简并图上,它可能比快速贪婪方法产生更高的模块性分数,尽管它有点慢.
label.propagation.community是一种简单的方法,其中每个节点都分配一个k标签.该方法然后迭代地进行并且以每个节点以同步方式获取其邻居的最频繁标签的方式将标签重新分配给节点.当每个节点的标签是其邻域中最频繁的标签之一时,该方法停止.它非常快,但根据初始配置(随机决定)产生不同的结果,因此应该多次运行该方法(例如,图表的1000次),然后建立共识标签,这可能是乏味.
igraph 0.6还将包括最先进的Infomap社区检测算法,该算法基于信息理论原理; 它试图建立一个分组,为图上的随机游走提供最短的描述长度,其中描述长度是通过编码随机游走路径所需的每个顶点的预期比特数来测量的.
无论如何,我可能会使用fastgreedy.community或walktrap.community作为第一个近似值然后评估其他方法,当事实证明这两个方法由于某种原因不适合特定问题.
tim*_*ham 13
可以在此处找到不同社区检测算法的摘要:http://www.r-bloggers.com/summary-of-community-detection-algorithms-in-igraph-0-6/
值得注意的是,InfoMAP算法是最近才有用的新手(它也支持有向图).