Multiscale dynamical embeddings of complex networks

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.

13 pages; 7 pages SI; 8 Figures

References in corpus (17)

• Fast unfolding of communities in large networks
• Maps of random walks on complex networks reveal community structure
• Synchronization in complex networks
• Resolution limit in community detection
• Statistical Mechanics of 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
• Narrow scope for resolution-limit-free community detection
• Parsimonious module inference in large networks
• The many facets of community detection in complex networks
• Exploiting symmetry in network analysis
• Diffusion geometry unravels the emergence of functional clusters in collective phenomena
• A Generalized and Adaptive Method for Community Detection
• Role-based similarity in directed 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