An integrative dynamical perspective for graph theory and the study of complex networks

Abstract

Built upon the shoulders of graph theory, the field of complex networks has become a central tool for studying real systems across various fields of research. Represented as graphs, different systems can be studied using the same analysis methods, which allows for their comparison. Here, we challenge the wide-spread idea that graph theory is a universal analysis tool, uniformly applicable to any kind of network data. Instead, we show that many classical graph metrics (including degree, clustering coefficient and geodesic distance) arise from a common hidden propagation model: the discrete cascade. From this perspective, graph metrics are no longer regarded as combinatorial measures of the graph, but as spatio-temporal properties of the network dynamics unfolded at different temporal scales. Once graph theory is seen as a model-based (and not a purely data-driven) analysis tool, we can freely or intentionally replace the discrete cascade by other canonical propagation models and define new network metrics. This opens the opportunity to design, explicitly and transparently, dedicated analyses for different types of real networks by choosing a propagation model that matches their individual constraints. In this way, we take stand that network topology cannot always be abstracted independently from network dynamics, but shall be jointly studied. Which is key for the interpretability of the analyses. The model-based perspective here proposed serves to integrate into a common context both the classical graph analysis and the more recent network metrics defined in the literature which were, directly or indirectly, inspired by propagation phenomena on networks.

arXiv comment23 pages, 6 figures. Perspective article

References in corpus (28)

• Maps of random walks on complex networks reveal community structure
• The large-scale organization of metabolic networks
• Random graphs with arbitrary degree distributions and their applications
• Synchronization in complex networks
• Synchronization reveals topological scales in complex networks
• Communicability in complex networks
• Random walks and diffusion on networks
• Navigability of Complex Networks
• Random Walks, Markov Processes and the Multiscale Modular Organization of Complex Networks
• Laplacian Dynamics and Multiscale Modular Structure in Networks
• The Physics of Communicability in Complex Networks
• Networks in Cognitive Science
• Distance, dissimilarity index, and network community structure
• Entropy Rate of Diffusion Processes on Complex Networks
• Exploring complex networks by walking on them
• Network Landscape from a Brownian Particle's Perspective
• Functional complexity emerging from anatomical constraints in the brain: the significance of network modularity and rich-clubs
• Encoding dynamics for multiscale community detection: Markov time sweeping for the Map equation
• Finding and testing network communities by lumped Markov chains
• Uncovering the community structure associated with the diffusion dynamics of networks
• Brain architecture: A design for natural computation
• Robust Weak Chimeras in Oscillator Networks with Delayed Linear and Quadratic Interactions
• Successful network inference from time-series data using Mutual Information Rate
• Mapping from Architecture to Dynamics: A Unified View of Dynamical Processes on Networks
• A control analysis perspective on Katz centrality
• Scale-dependent measure of network centrality from diffusion dynamics
• A novel framework to analyze complex network dynamics
• Sizing the length of complex networks