Department of Mathematics, Imperial College London, London, United Kingdom.
PLoS One. 2012;7(2):e32210. doi: 10.1371/journal.pone.0032210. Epub 2012 Feb 27.
In recent years, there has been a surge of interest in community detection algorithms for complex networks. A variety of computational heuristics, some with a long history, have been proposed for the identification of communities or, alternatively, of good graph partitions. In most cases, the algorithms maximize a particular objective function, thereby finding the 'right' split into communities. Although a thorough comparison of algorithms is still lacking, there has been an effort to design benchmarks, i.e., random graph models with known community structure against which algorithms can be evaluated. However, popular community detection methods and benchmarks normally assume an implicit notion of community based on clique-like subgraphs, a form of community structure that is not always characteristic of real networks. Specifically, networks that emerge from geometric constraints can have natural non clique-like substructures with large effective diameters, which can be interpreted as long-range communities. In this work, we show that long-range communities escape detection by popular methods, which are blinded by a restricted 'field-of-view' limit, an intrinsic upper scale on the communities they can detect. The field-of-view limit means that long-range communities tend to be overpartitioned. We show how by adopting a dynamical perspective towards community detection [1], [2], in which the evolution of a Markov process on the graph is used as a zooming lens over the structure of the network at all scales, one can detect both clique- or non clique-like communities without imposing an upper scale to the detection. Consequently, the performance of algorithms on inherently low-diameter, clique-like benchmarks may not always be indicative of equally good results in real networks with local, sparser connectivity. We illustrate our ideas with constructive examples and through the analysis of real-world networks from imaging, protein structures and the power grid, where a multiscale structure of non clique-like communities is revealed.
近年来，人们对复杂网络的社区检测算法产生了浓厚的兴趣。已经提出了各种计算启发式方法，其中一些具有悠久的历史，用于识别社区或，或者，用于良好的图分区。在大多数情况下，算法会最大化特定的目标函数，从而找到“正确”的社区划分。尽管算法的全面比较仍然缺乏，但已经努力设计基准，即具有已知社区结构的随机图模型，算法可以对其进行评估。然而，流行的社区检测方法和基准通常假设基于团状子图的隐含社区概念，这种社区结构形式并不总是具有真实网络的特征。具体而言，由几何约束产生的网络可能具有具有大有效直径的自然非团状子结构，可以将其解释为长程社区。在这项工作中，我们表明，流行的方法会漏掉长程社区，这些方法受到受限的“视野”限制的影响，这是它们可以检测到的社区的内在上限。视野限制意味着长程社区往往会过度分区。我们展示了如何通过采用社区检测的动态视角[1]，[2]，其中图上的马尔可夫过程的演化被用作网络所有尺度结构的变焦镜头，而无需对检测施加上限，就可以检测到团状或非团状社区。因此，算法在固有低直径、团状基准上的性能并不总是能够反映在具有局部、稀疏连接的真实网络中的同等良好结果。我们通过建设性的例子和通过对成像、蛋白质结构和电网等真实网络的分析来说明我们的想法，揭示了非团状社区的多尺度结构。
