Structured networks and coarse-grained descriptions: a dynamical perspective
arXiv:1804.06268 · doi:10.1002/9781119483298.ch12
Abstract
This chapter discusses the interplay between structure and dynamics in complex networks. Given a particular network with an endowed dynamics, our goal is to find partitions aligned with the dynamical process acting on top of the network. We thus aim to gain a reduced description of the system that takes into account both its structure and dynamics. In the first part, we introduce the general mathematical setup for the types of dynamics we consider throughout the chapter. We provide two guiding examples, namely consensus dynamics and diffusion processes (random walks), motivating their connection to social network analysis, and provide a brief discussion on the general dynamical framework and its possible extensions. In the second part, we focus on the influence of graph structure on the dynamics taking place on the network, focusing on three concepts that allow us to gain insight into this notion. First, we describe how time scale separation can appear in the dynamics on a network as a consequence of graph structure. Second, we discuss how the presence of particular symmetries in the network give rise to invariant dynamical subspaces that can be precisely described by graph partitions. Third, we show how this dynamical viewpoint can be extended to study dynamics on networks with signed edges, which allow us to discuss connections to concepts in social network analysis, such as structural balance. In the third part, we discuss how to use dynamical processes unfolding on the network to detect meaningful network substructures. We then show how such dynamical measures can be related to seemingly different algorithm for community detection and coarse-graining proposed in the literature. We conclude with a brief summary and highlight interesting open future directions.
arXiv comment21 pages; 7 figures; To appear as a chapter in "Advances in Network Clustering and Blockmodeling" edited by P. Doreian, V. Batagelj & A. Ferligoj (Wiley, New York, 2018)
References in corpus (44)
- Community detection in graphs
- Cooperative Game Theory Approaches for Network Partitioning
- Multilayer Networks
- The structure and dynamics of multilayer networks
- Temporal Networks
- Community detection in networks: A user guide
- Synchronization in small-world systems
- Multirelational Organization of Large-scale Social Networks in an Online World
- Random walks and diffusion on networks
- Spectral redemption: clustering sparse networks
- Symmetries, Cluster Synchronization, and Isolated Desynchronization in Complex Networks
- A Tutorial on Modeling and Analysis of Dynamic Social Networks. Part I
- Spectral clustering and the high-dimensional stochastic blockmodel
- SEISMIC: A Self-Exciting Point Process Model for Predicting Tweet Popularity
- The ground truth about metadata and community detection in networks
- Random Walks, Markov Processes and the Multiscale Modular Organization of Complex Networks
- Laplacian Dynamics and Multiscale Modular Structure in Networks
- Memory in network flows and its effects on spreading dynamics and community detection
- Phase transition in the detection of modules in sparse networks
- Opinion fluctuations and disagreement in social networks
- Opinion Dynamics in Social Networks with Hostile Camps: Consensus vs. Polarization
- Consistency of spectral clustering in stochastic block models
- Graph spectra and the detectability of community structure in networks
- Dynamics of Social Balance on Networks
- On the Role of Zealotry in the Voter Model
- Analysis of a continuous-time model of structural balance
- Complete Characterization of Stability of Cluster Synchronization in Complex Dynamical Networks
- The Heider balance - a continuous approach
- The many facets of community detection in complex networks
- Markov dynamics as a zooming lens for multiscale community detection: non clique-like communities and the field-of-view limit
- Graph partitions and cluster synchronization in networks of oscillators
- Diffusion on networked systems is a question of time or structure
- Dynamical Models Explaining Social Balance and Evolution of Cooperation
- Generalized Master Equations for Non-Poisson Dynamics on Networks
- Eigenvalue Spectra of Modular Networks
- The stability of a graph partition: A dynamics-based framework for community detection
- Finding and testing network communities by lumped Markov chains
- Emergence of slow-switching assemblies in structured neuronal networks
- Exploiting symmetry in network analysis
- Covariance, correlation matrix and the multi-scale community structure of networks
- Multiscale dynamical embeddings of complex networks
- Spectra of random graphs with community structure and arbitrary degrees
- Using higher-order Markov models to reveal flow-based communities in networks
- Structured Random Matrices