A Monte Carlo Evaluation of Weighted Community Detection Algorithms.
A Monte Carlo Evaluation of Weighted Community Detection Algorithms.
复制标题
DOI：
10.3389/fninf.2016.00045
复制
发表时间：
2016
影响因子：
3.5
通讯作者：
Fair DA
中科院分区：
文献类型：
--
作者：
Gates KM;Henry T;Steinley D;Fair DA
在过去的十年中，以社区检测算法的激增为标志，这些算法旨在将节点（例如，个人，大脑区域，变量）组织成指示子群体，集群或社区的模块化结构。由于大数据在许多研究领域的出现，这些方法的发展主要集中在从非常大的矩阵中检测节点群落。然而，目前尚不清楚这些算法是否能够可靠地检测到通常用于大脑研究的较小图大小（即1000个节点或更少）的社区。更重要的是，这些算法主要只在二进制或稀疏计数矩阵上进行了测试，目前尚不清楚这些算法在多大程度上可以恢复不同类型矩阵的社区结构，例如经常使用的相互关联矩阵，表示预定义大脑区域之间的功能连接。在公开可用的加权图方法中，可以检测图大小至少为1000的社区，先前的研究表明，Newman的光谱方法（即领先特征值）、Walktrap、Fast Modularity、Louvain方法（即多层社区方法）、Label Propagation和Infomap在某些情况下都能很好地恢复社区。本蒙特卡罗模拟研究的目的是在大量条件下测试这些方法，包括不同的图大小和矩阵类型（稀疏计数、相关性和反射欧几里得距离），以确定哪种算法对特定类型的数据矩阵是最优的。结果表明，当数据以稀疏计数网络的形式出现时（例如在扩散张量成像中看到的那些），标签传播（Label Propagation）和步行陷阱（Walktrap）成为最可靠的社区检测方法。对于密集的加权网络，如捕获功能连通性的相关矩阵，Walktrap在恢复社区方面始终优于其他方法。
The past decade has been marked with a proliferation of community detection algorithms that aim to organize nodes (e.g., individuals, brain regions, variables) into modular structures that indicate subgroups, clusters, or communities. Motivated by the emergence of big data across many fields of inquiry, these methodological developments have primarily focused on the detection of communities of nodes from matrices that are very large. However, it remains unknown if the algorithms can reliably detect communities in smaller graph sizes (i.e., 1000 nodes and fewer) which are commonly used in brain research. More importantly, these algorithms have predominantly been tested only on binary or sparse count matrices and it remains unclear the degree to which the algorithms can recover community structure for different types of matrices, such as the often used cross-correlation matrices representing functional connectivity across predefined brain regions. Of the publicly available approaches for weighted graphs that can detect communities in graph sizes of at least 1000, prior research has demonstrated that Newman's spectral approach (i.e., Leading Eigenvalue), Walktrap, Fast Modularity, the Louvain method (i.e., multilevel community method), Label Propagation, and Infomap all recover communities exceptionally well in certain circumstances. The purpose of the present Monte Carlo simulation study is to test these methods across a large number of conditions, including varied graph sizes and types of matrix (sparse count, correlation, and reflected Euclidean distance), to identify which algorithm is optimal for specific types of data matrices. The results indicate that when the data are in the form of sparse count networks (such as those seen in diffusion tensor imaging), Label Propagation and Walktrap surfaced as the most reliable methods for community detection. For dense, weighted networks such as correlation matrices capturing functional connectivity, Walktrap consistently outperformed the other approaches for recovering communities.
登录
查看更多内容
影响因子：
5.7
作者：
Mumford, Jeanette A.;Horvath, Steve;Oldham, Michael C.;Langfelder, Peter;Geschwind, Daniel H.;Poldrack, Russell A.
通讯作者：
Poldrack, Russell A.
DOI：
10.1073/pnas.0605965104
发表时间：
2007-01-02
影响因子：
11.1
作者：
Fortunato, Santo;Barthelemy, Marc
通讯作者：
Barthelemy, Marc
DOI：
10.1088/1742-5468/2008/10/p10008
发表时间：
2008-10-01
影响因子：
2.4
作者：
Blondel, Vincent D.;Guillaume, Jean-Loup;Lefebvre, Etienne
通讯作者：
Lefebvre, Etienne
影响因子：
3.7
作者：
Gates KM;Molenaar PC;Iyer SP;Nigg JT;Fair DA
通讯作者：
Fair DA
DOI：
10.1073/pnas.122653799
发表时间：
2002-06-11
影响因子：
11.1
作者：
Girvan, M;Newman, MEJ
通讯作者：
Newman, MEJ