%0 Generic %1 Schaub2011 %A Schaub, Michael T. %A Delvenne, Jean-Charles %A Yaliraki, Sophia N. %A Barahona, Mauricio %D 2011 %K community detection dynamics large markov networks %T Markov dynamics as a zooming lens for multiscale community detection: non clique-like communities and the field-of-view limit %U http://arxiv.org/abs/1109.5593 %X Recently, there has been a surge of interest in community detection algorithms for complex networks. The proposed algorithms are based on a variety of heuristics, some with a long history, for the identification of communities or, alternatively, of good graph partitions. In most cases, the algorithms proceed by maximizing a particular objective function, thereby finding the `right' split into communities. Although a thorough comparative analysis of these algorithms is still lacking, there has also been an effort to design random graph models with known community structure against which the performance of different algorithms can be benchmarked. However, such benchmarks normally impose not only a known community structure but also a clique-like random structure for the communities which may differ significantly from those found in real networks. We show here that popular community detection methods are affected by a restricted `field-of-view' limit, an intrinsic upper scale that does not allow them to detect communities with large effective diameters. Such long-range communities are widespread in real networks, specifically in those that emerge from geometric constraints. In consequence, the performance of algorithms on clique-like benchmarks, which are inherently of low diameter, may not be indicative of equally good results in real networks with sparser connectivity. We show that by adopting a dynamical perspective towards community detection (Delvenne et al. (2010) PNAS:107: 12755-12760; Lambiotte et al. (2008) arXiv:0812.1770), in which the evolution of a Markov process acts as a zooming lens over the structure of the graph at all scales, one can detect robust communities without imposing an intrinsic upper scale to the communities. We illustrate our ideas with constructive examples and through the analysis of real-world networks from imaging, protein structure and the power grid.

@misc{Schaub2011, abstract = { Recently, there has been a surge of interest in community detection algorithms for complex networks. The proposed algorithms are based on a variety of heuristics, some with a long history, for the identification of communities or, alternatively, of good graph partitions. In most cases, the algorithms proceed by maximizing a particular objective function, thereby finding the `right' split into communities. Although a thorough comparative analysis of these algorithms is still lacking, there has also been an effort to design random graph models with known community structure against which the performance of different algorithms can be benchmarked. However, such benchmarks normally impose not only a known community structure but also a clique-like random structure for the communities which may differ significantly from those found in real networks. We show here that popular community detection methods are affected by a restricted `field-of-view' limit, an intrinsic upper scale that does not allow them to detect communities with large effective diameters. Such long-range communities are widespread in real networks, specifically in those that emerge from geometric constraints. In consequence, the performance of algorithms on clique-like benchmarks, which are inherently of low diameter, may not be indicative of equally good results in real networks with sparser connectivity. We show that by adopting a dynamical perspective towards community detection (Delvenne et al. (2010) PNAS:107: 12755-12760; Lambiotte et al. (2008) arXiv:0812.1770), in which the evolution of a Markov process acts as a zooming lens over the structure of the graph at all scales, one can detect robust communities without imposing an intrinsic upper scale to the communities. We illustrate our ideas with constructive examples and through the analysis of real-world networks from imaging, protein structure and the power grid. }, added-at = {2011-11-07T21:04:29.000+0100}, author = {Schaub, Michael T. and Delvenne, Jean-Charles and Yaliraki, Sophia N. and Barahona, Mauricio}, biburl = {https://www.bibsonomy.org/bibtex/2123de1d06fa53a676bdff34fb1d39383/nicolasboumal}, description = {[1109.5593] Markov dynamics as a zooming lens for multiscale community detection: non clique-like communities and the field-of-view limit}, interhash = {f0d671570b6ddb9df4f347f8f945a008}, intrahash = {123de1d06fa53a676bdff34fb1d39383}, keywords = {community detection dynamics large markov networks}, note = {cite arxiv:1109.5593 Comment: 19 pages, 6 figures}, timestamp = {2011-11-07T21:04:29.000+0100}, title = {Markov dynamics as a zooming lens for multiscale community detection: non clique-like communities and the field-of-view limit}, url = {http://arxiv.org/abs/1109.5593}, year = 2011 }