Laplacian Dynamics and Multiscale Modular Structure in Networks

Abstract

Most methods proposed to uncover communities in complex networks rely on their structural properties. Here we introduce the stability of a network partition, a measure of its quality defined in terms of the statistical properties of a dynamical process taking place on the graph. The time-scale of the process acts as an intrinsic parameter that uncovers community structures at different resolutions. The stability extends and unifies standard notions for community detection: modularity and spectral partitioning can be seen as limiting cases of our dynamic measure. Similarly, recently proposed multi-resolution methods correspond to linearisations of the stability at short times. The connection between community detection and Laplacian dynamics enables us to establish dynamically motivated stability measures linked to distinct null models. We apply our method to find multi-scale partitions for different networks and show that the stability can be computed efficiently for large networks with extended versions of current algorithms.

New discussions on the selection of the most significant scales and the generalisation of stability to directed networks

References in corpus (33)

• Fast unfolding of communities in large 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
• 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