Random Walks, Markov Processes and the Multiscale Modular Organization of Complex Networks

Abstract

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.

Extended version of arXiv:0812.1770, 'Laplacian Dynamics and Multiscale Modular Structure in Networks', by the same authors, with new content; published in Transactions on Network Science and Engineering; 16 pages; 11 figs

References in corpus (37)

• Fast unfolding of communities in large networks
• The structure and function of complex networks
• Community structure in social and biological networks
• Finding and evaluating community structure in networks
• Modularity and community structure in networks
• Community detection in graphs
• 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
• Community Structure in Time-Dependent, Multiscale, and Multiplex Networks
• Hierarchical structure and the prediction of missing links in networks
• Statistical Mechanics of Community Detection
• Synchronization in small-world systems
• Community structure in directed networks
• The performance of modularity maximization in practical contexts
• Synchronization in Complex Oscillator Networks and Smart Grids
• Synchronization reveals topological scales in complex networks
• Extracting the hierarchical organization of complex systems
• Analysis of the structure of complex networks at different resolution levels
• Narrow scope for resolution-limit-free community detection
• Robustness of community structure in networks
• Size reduction of complex networks preserving modularity
• Multiresolution community detection for megascale networks by information-based replica correlations
• LinkRank: Finding communities in directed networks
• Spectral centrality measures in complex networks
• Markov dynamics as a zooming lens for multiscale community detection: non clique-like communities and the field-of-view limit
• Majority Model on a network with communities
• Generalized Master Equations for Non-Poisson Dynamics on Networks
• Flow graphs: interweaving dynamics and structure
• Centrality measures and thermodynamic formalism for complex networks
• Synchronization and modularity in complex networks
• The stability of a graph partition: A dynamics-based framework for community detection
• Dynamic communities in multichannel data: An application to the foreign exchange market during the 2007--2008 credit crisis
• Finding and testing network communities by lumped Markov chains
• Protein multi-scale organization through graph partitioning and robustness analysis: Application to the myosin-myosin light chain interaction
• Maximal entropy random walk in community finding
• Modular networks with hierarchical organization: The dynamical implications of complex structure

Cited by in corpus (83)

• Random walks and diffusion on networks
• Community detection in networks: Modularity optimization and maximum likelihood are equivalent
• Collective phenomena emerging from the interactions between dynamical processes in multiplex networks
• Spectral entropies as information-theoretic tools for complex network comparison
• Multilayer Brain Networks
• Multi-body Interactions and Non-Linear Consensus Dynamics on Networked Systems
• The many facets of community detection in complex networks
• Random walk centrality in interconnected multilayer networks
• Understanding the geometry of transport: diffusion maps for Lagrangian trajectory data unravel coherent sets
• Weighted simplicial complexes and their representation power of higher-order network data and topology
• Core-periphery structure requires something else in the network
• Flow-based network analysis of the Caenorhabditis elegans connectome
• Sentiment Correlation in Financial News Networks and Associated Market Movements
• Descriptive vs. inferential community detection in networks: pitfalls, myths, and half-truths
• Efficient community detection of network flows for varying Markov times and bipartite networks
• Diffusion geometry unravels the emergence of functional clusters in collective phenomena
• Graph-based data clustering via multiscale community detection
• Magnetic eigenmaps for community detection in directed networks
• Multiscale dynamical embeddings of complex networks
• A Broader Picture of Random-walk Based Graph Embedding
• A Framework for the Construction of Generative Models for Mesoscale Structure in Multilayer Networks
• The 'who' and 'what' of #diabetes on Twitter
• Using higher-order Markov models to reveal flow-based communities in networks
• Multilayer Network Science: from Cells to Societies
• Hierarchical Graph Clustering using Node Pair Sampling
• Multi-scale Anomaly Detection on Attributed Networks
• From Free Text to Clusters of Content in Health Records: An Unsupervised Graph Partitioning Approach
• Different approaches to community detection
• Synwalk -- Community Detection via Random Walk Modelling
• A generalised significance test for individual communities in networks
• POLE: Polarized Embedding for Signed Networks
• Flow stability for dynamic community detection
• Diffusion geometry of multiplex and interdependent systems
• Extracting Complements and Substitutes from Sales Data: A Network Perspective
• Modularity and the spread of perturbations in complex dynamical systems
• Allostery and cooperativity in multimeric proteins: bond-to-bond propensities in ATCase
• Generalized network density matrices for analysis of multiscale functional diversity
• Scale-dependent measure of network centrality from diffusion dynamics
• Graph Filters and the Z-Laplacian
• Core of communities in bipartite networks
• Mapping flows on sparse networks with missing links
• Interplay between $k$-core and community structure in complex networks
• Quantifying the Alignment of Graph and Features in Deep Learning
• Anger makes fake news viral online
• Random walk on temporal networks with lasting edges
• An integrative dynamical perspective for graph theory and the study of complex networks
• Burstiness and fractional diffusion on complex networks
• Geometric Multiscale Community Detection: Markov Stability and Vector Partitioning
• From spatio-temporal data to chronological networks: An application to wildfire analysis
• Multiscale mobility patterns and the restriction of human movement
• Information transfer in community structured multiplex networks
• Scale-variant topological information for characterizing the structure of complex networks
• Dynamics Based Features For Graph Classification
• Maximal modularity and the optimal size of parliaments
• PyGenStability: Multiscale community detection with generalized Markov Stability
• Multi-hop assortativities for networks classification
• Multi-scale Laplacian community detection in heterogeneous networks
• Explainable, Stable, and Scalable Graph Convolutional Networks for Learning Graph Representation
• Generalized Markov stability of network communities
• Stochastic Distinguishability of Markovian Trajectories
• Geometric graphs from data to aid classification tasks with graph convolutional networks
• Resolution Limits for Detecting Community Changes in Multilayer Networks
• Structured networks and coarse-grained descriptions: a dynamical perspective
• Measuring the effect of node aggregation on community detection
• Self-segregation in heterogeneous metapopulation landscapes
• Content-driven, unsupervised clustering of news articles through multiscale graph partitioning
• Making Communities Show Respect for Order
• Community Detection with the Map Equation and Infomap: Theory and Applications
• Innovative activities of Activision Blizzard: A patent network analysis
• Multilayer Modularity Belief Propagation To Assess Detectability Of Community Structure
• Flow-based Community Detection in Hypergraphs
• Dynamic Community Detection into Analyzing of Wildfires Events
• From Text to Topics in Healthcare Records: An Unsupervised Graph Partitioning Methodology
• An approximation for return time distributions of random walks on sparse networks
• Node Embedding via Word Embedding for Network Community Discovery
• Energy-Aware Stochastic UAV-Assisted Surveillance
• A multilevel network approach to revealing patterns of online political selective exposure
• Testing network clustering algorithms with Natural Language Processing
• Multiscale methods for signal selection in single-cell data
• Learning Graph Representations by Dendrograms
• Graph clustering in industrial networks
• Latent geometry emerging from network-driven processes
• Time-Varying Graph Learning with Constraints on Graph Temporal Variation