Multiscale dynamical embeddings of complex networks
arXiv:1804.03733 · doi:10.1103/PhysRevE.99.062308
Abstract
Complex systems and relational data are often abstracted as dynamical processes on networks. To understand, predict and control their behavior, a crucial step is to extract reduced descriptions of such networks. Inspired by notions from Control Theory, we propose a time-dependent dynamical similarity measure between nodes, which quantifies the effect a node-input has on the network. This dynamical similarity induces an embedding that can be employed for several analysis tasks. Here we focus on (i)~dimensionality reduction, i.e., projecting nodes onto a low dimensional space that captures dynamic similarity at different time scales, and (ii)~how to exploit our embeddings to uncover functional modules. We exemplify our ideas through case studies focusing on directed networks without strong connectivity, and signed networks. We further highlight how certain ideas from community detection can be generalized and linked to Control Theory, by using the here developed dynamical perspective.
arXiv comment13 pages; 7 pages SI; 8 Figures
References in corpus (40)
- Fast unfolding of communities in large networks
- Finding and evaluating community structure in networks
- Community detection in graphs
- Maps of random walks on complex networks reveal community structure
- Synchronization in complex networks
- Resolution limit in community detection
- Link Prediction in Complex Networks: A Survey
- Community Structure in Time-Dependent, Multiscale, and Multiplex Networks
- Statistical Mechanics of Community Detection
- Vertex similarity in networks
- Symmetries, Cluster Synchronization, and Isolated Desynchronization in Complex Networks
- Detecting fuzzy community structures in complex networks with a Potts model
- Limits of modularity maximization in community detection
- Community detection in networks with positive and negative links
- Analysis of the structure of complex networks at different resolution levels
- 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
- Structure and inference in annotated networks
- Narrow scope for resolution-limit-free community detection
- Complete Characterization of Stability of Cluster Synchronization in Complex Dynamical Networks
- Parsimonious module inference in large networks
- Markov dynamics as a zooming lens for multiscale community detection: non clique-like communities and the field-of-view limit
- The many facets of community detection in complex networks
- Graph partitions and cluster synchronization in networks of oscillators
- Community detection for correlation matrices
- Diffusion on networked systems is a question of time or structure
- Ranking and clustering of nodes in networks with smart teleportation
- Encoding dynamics for multiscale community detection: Markov time sweeping for the Map equation
- The stability of a graph partition: A dynamics-based framework for community detection
- Emergence of slow-switching assemblies in structured neuronal networks
- Exploiting symmetry in network analysis
- Diffusion geometry unravels the emergence of functional clusters in collective phenomena
- Protein multi-scale organization through graph partitioning and robustness analysis: Application to the myosin-myosin light chain interaction
- Modularity and the spread of perturbations in complex dynamical systems
- A Generalized and Adaptive Method for Community Detection
- Role-based similarity in directed networks
- Cycle flow based module detection in directed recurrence networks
- Entrograms and coarse graining of dynamics on complex networks
- Role-similarity based comparison of directed networks
Cited by in corpus (14)
- Graph-based data clustering via multiscale community detection
- A Broader Picture of Random-walk Based Graph Embedding
- POLE: Polarized Embedding for Signed Networks
- Flow stability for dynamic community detection
- Sensitivity and spectral control of network lasers
- Extracting Complements and Substitutes from Sales Data: A Network Perspective
- Scale-dependent measure of network centrality from diffusion dynamics
- Multiscale mobility patterns and the restriction of human movement
- State aggregations in Markov chains and block models of networks
- Zoo Guide to Network Embedding
- PyGenStability: Multiscale community detection with generalized Markov Stability
- Measuring dynamical systems on directed hyper-graphs
- Structured networks and coarse-grained descriptions: a dynamical perspective
- Guided Graph Spectral Embedding: Application to the C. elegans Connectome