Journal
IEEE TRANSACTIONS ON NETWORK SCIENCE AND ENGINEERING
Volume 1, Issue 2, Pages 76-90Publisher
IEEE COMPUTER SOC
DOI: 10.1109/TNSE.2015.2391998
Keywords
Community detection; partition stability; multiscale structure; random walks; graph theory; centrality; optimization
Funding
- Belgian Programme of Interuniversity Attraction Poles
- Action de Recherche Concertee (ARC) of the French Community of Belgium
- FP7 STREP project EULER of the European Commission
- FNRS
- Optimizr of the European Commission
- UK EPSRC (Engineering and Physical Sciences Research Council) under the Mathematics Underpinning the Digital Economy program [EP/I017267/1]
- EPSRC [EP/I017267/1] Funding Source: UKRI
Ask authors/readers for more resources
Most methods proposed to uncover communities in complex networks rely on combinatorial graph properties. Usually an edge-counting quality function, such as modularity, is optimized over all partitions of the graph compared against a null random graph model. Here we introduce a systematic dynamical framework to design and analyze a wide variety of quality functions for community detection. The quality of a partition is measured by its Markov Stability, a time-parametrized function defined in terms of the statistical properties of a Markov process taking place on the graph. The Markov process provides a dynamical sweeping across all scales in the graph, and the time scale is an intrinsic parameter that uncovers communities at different resolutions. This dynamic-based community detection leads to a compound optimization, which favours communities of comparable centrality (as defined by the stationary distribution), and provides a unifying framework for spectral algorithms, as well as different heuristics for community detection, including versions of modularity and Potts model. Our dynamic framework creates a systematic link between different stochastic dynamics and their corresponding notions of optimal communities under distinct (node and edge) centralities. We show that the Markov Stability can be computed efficiently to find multi-scale community structure in large networks.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available