The stability of a graph partition: A dynamics-based framework for community detection

Abstract

Recent years have seen a surge of interest in the analysis of complex networks, facilitated by the availability of relational data and the increasingly powerful computational resources that can be employed for their analysis. Naturally, the study of real-world systems leads to highly complex networks and a current challenge is to extract intelligible, simplified descriptions from the network in terms of relevant subgraphs, which can provide insight into the structure and function of the overall system. Sparked by seminal work by Newman and Girvan, an interesting line of research has been devoted to investigating modular community structure in networks, revitalising the classic problem of graph partitioning. However, modular or community structure in networks has notoriously evaded rigorous definition. The most accepted notion of community is perhaps that of a group of elements which exhibit a stronger level of interaction within themselves than with the elements outside the community. This concept has resulted in a plethora of computational methods and heuristics for community detection. Nevertheless a firm theoretical understanding of most of these methods, in terms of how they operate and what they are supposed to detect, is still lacking to date. Here, we will develop a dynamical perspective towards community detection enabling us to define a measure named the stability of a graph partition. It will be shown that a number of previously ad-hoc defined heuristics for community detection can be seen as particular cases of our method providing us with a dynamic reinterpretation of those measures. Our dynamics-based approach thus serves as a unifying framework to gain a deeper understanding of different aspects and problems associated with community detection and allows us to propose new dynamically-inspired criteria for community structure.

3 figures; published as book chapter

References in corpus (15)

• Fast unfolding of communities in large networks
• Modularity and community structure in networks
• Finding community structure in networks using the eigenvectors of matrices
• Maps of random walks on complex networks reveal community structure
• Benchmark graphs for testing community detection algorithms
• Statistical Mechanics of Community Detection
• Stochastic blockmodels and community structure in networks
• Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities
• Line Graphs, Link Partitions and Overlapping Communities
• Narrow scope for resolution-limit-free community detection
• Robustness of the European power grids under intentional attack
• Markov dynamics as a zooming lens for multiscale community detection: non clique-like communities and the field-of-view limit
• Encoding dynamics for multiscale community detection: Markov time sweeping for the Map equation
• Protein multi-scale organization through graph partitioning and robustness analysis: Application to the myosin-myosin light chain interaction
• Effect of size heterogeneity on community identification in complex networks

Cited by in corpus (27)

• Random Walks, Markov Processes and the Multiscale Modular Organization of Complex Networks
• The many facets of community detection in complex networks
• A spectrum of routing strategies for brain networks
• Flow-based network analysis of the Caenorhabditis elegans connectome
• Emergence of slow-switching assemblies in structured neuronal networks
• Structure of complex networks: Quantifying edge-to-edge relations by failure-induced flow redistribution
• Graph-based data clustering via multiscale community detection
• Revealing cell assemblies at multiple levels of granularity
• Multiscale dynamical embeddings of complex networks
• The 'who' and 'what' of #diabetes on Twitter
• Using higher-order Markov models to reveal flow-based communities in networks
• Multi-scale Anomaly Detection on Attributed Networks
• From Free Text to Clusters of Content in Health Records: An Unsupervised Graph Partitioning Approach
• Finding role communities in directed networks using Role-Based Similarity, Markov Stability and the Relaxed Minimum Spanning Tree
• Different approaches to community detection
• Is academia becoming more localised? The growth of regional knowledge networks within international research collaboration
• Multiscale mobility patterns and the restriction of human movement
• Dynamics Based Features For Graph Classification
• Integrating sentiment and social structure to determine preference alignments: The Irish Marriage Referendum
• PyGenStability: Multiscale community detection with generalized Markov Stability
• Structured networks and coarse-grained descriptions: a dynamical perspective
• Content-driven, unsupervised clustering of news articles through multiscale graph partitioning
• Tensor clustering with algebraic constraints gives interpretable groups of crosstalk mechanisms in breast cancer
• Flow-based Community Detection in Hypergraphs
• Extracting information from free text through unsupervised graph-based clustering: an application to patient incident records
• Multiscale methods for signal selection in single-cell data
• TAPER: query-aware, partition-enhancement for large, heterogenous, graphs