Memory in network flows and its effects on spreading dynamics and community detection

Abstract

Random walks on networks is the standard tool for modelling spreading processes in social and biological systems. This first-order Markov approach is used in conventional community detection, ranking, and spreading analysis although it ignores a potentially important feature of the dynamics: where flow moves to may depend on where it comes from. Here we analyse pathways from different systems, and while we only observe marginal consequences for disease spreading, we show that ignoring the effects of second-order Markov dynamics has important consequences for community detection, ranking, and information spreading. For example, capturing dynamics with a second-order Markov model allows us to reveal actual travel patterns in air traffic and to uncover multidisciplinary journals in scientific communication. These findings were achieved only by using more available data and making no additional assumptions, and therefore suggest that accounting for higher-order memory in network flows can help us better understand how real systems are organized and function.

23 pages and 16 figures

References in corpus (13)

• Modularity and community structure in networks
• Understanding individual human mobility patterns
• Uncovering the overlapping community structure of complex networks in nature and society
• Maps of random walks on complex networks reveal community structure
• Comparing community structure identification
• The scaling laws of human travel
• Detecting the overlapping and hierarchical community structure of complex networks
• Finding statistically significant communities in networks
• Reaction-diffusion processes and metapopulation models in heterogeneous networks
• Theory of Rumour Spreading in Complex Social Networks
• Line Graphs, Link Partitions and Overlapping Communities
• Phase transitions in contagion processes mediated by recurrent mobility patterns
• Maximal-entropy random walks in complex networks with limited information

Cited by in corpus (119)

• Community detection in networks: A user guide
• Higher-order organization of complex networks
• Random walks and diffusion on networks
• Modern temporal network theory: A colloquium
• Simplicial Closure and higher-order link prediction
• Fundamental structures of dynamic social networks
• Causality-Driven Slow-Down and Speed-Up of Diffusion in Non-Markovian Temporal Networks
• Random walks on hypergraphs
• Representing higher-order dependencies in networks
• Ranking in evolving complex networks
• Identifying modular flows on multilayer networks reveals highly overlapping organization in social systems
• Network Analysis of Particles and Grains
• Spectral entropies as information-theoretic tools for complex network comparison
• The many facets of community detection in complex networks
• Modeling sequences and temporal networks with dynamic community structures
• Diffusion on networked systems is a question of time or structure
• Brain Network Adaptability Across Task States
• Inference of hyperedges and overlapping communities in hypergraphs
• Higher-order clustering in networks
• Model selection and hypothesis testing for large-scale network models with overlapping groups
• Mapping higher-order network flows in memory and multilayer networks with Infomap
• Tensor Spectral Clustering for Partitioning Higher-order Network Structures
• Non-Markovian Quantum Process Tomography
• How memory generates heterogeneous dynamics in temporal networks
• Growing complex network of citations of scientific papers -- measurements and modeling
• Higher-Order Aggregate Networks in the Analysis of Temporal Networks: Path structures and centralities
• Flow-based network analysis of the Caenorhabditis elegans connectome
• Quantum Markov Order
• Contrasting Effects of Strong Ties on SIR and SIS Processes in Temporal Networks
• Randomized reference models for temporal networks
• Vector Centrality in Hypergraphs
• Mapping flows on hypergraphs
• Diffusion geometry unravels the emergence of functional clusters in collective phenomena
• Magnetic eigenmaps for community detection in directed networks
• Steady state and mean recurrence time for random walks on stochastic temporal networks
• Multiscale dynamical embeddings of complex networks
• Epidemic spreading in localized environments with recurrent mobility patterns
• Efficient modeling of higher-order dependencies in networks: from algorithm to application for anomaly detection
• A Framework for the Construction of Generative Models for Mesoscale Structure in Multilayer Networks
• Using higher-order Markov models to reveal flow-based communities in networks
• Epidemic Spreading and Aging in Temporal Networks with Memory
• Layer-switching cost and optimality in information spreading on multiplex networks
• Dynamics on networks: competition of temporal and topological correlations
• Multilayer Network Science: from Cells to Societies
• Laplacian paths in complex networks: information core emerges from entropic transitions
• Effects of memory on spreading processes in non-Markovian temporal networks
• Assessing reliable human mobility patterns from higher-order memory in mobile communications
• Quantifying efficient information exchange in real network flows
• Epidemic Dynamics in Homes and Destinations under Recurrent Mobility Patterns
• Different approaches to community detection
• Preferential attachment mechanism of complex network growth: "rich-gets-richer" or "fit-gets-richer"?
• Hierarchical networks of scientific journals
• The Mobility Network of Scientists: Analyzing Temporal Correlations in Scientific Careers
• From Relational Data to Graphs: Inferring Significant Links using Generalized Hypergeometric Ensembles
• Randomizing growing networks with a time-respecting null model
• Influencers identification in complex networks through reaction-diffusion dynamics
• The Temporal Event Graph
• HONEM: Learning Embedding for Higher Order Networks
• Anomalous metapopulation dynamics on scale-free networks
• Analysis of node2vec random walks on networks
• HYPA: Efficient Detection of Path Anomalies in Time Series Data on Networks
• Characterization of the community structure in a large-scale production network in Japan
• Mixed random walks with a trap in scale-free networks including nearest-neighbor and next-nearest-neighbor jumps
• Non-Markovian Majority-Vote model
• Effects of reciprocity on random walks in weighted networks
• Burstiness and fractional diffusion on complex networks
• Analysis of heat kernel highlights the strongly modular and heat-preserving structure of proteins
• Effects of Competition and Cooperation Interaction between Agents on Networks in Presence of a "Market Capacity"
• Memory Effects in Quantum Processes
• Understanding Complex Systems: From Networks to Optimal Higher-Order Models
• Classes of random walks on temporal networks with competing timescales
• Higher-order Network Analysis Takes Off, Fueled by Classical Ideas and New Data
• Higher-order models capture changes in controllability of temporal networks
• Wikipedia Reader Navigation: When Synthetic Data Is Enough
• Statistical analysis of the first passage path ensemble of jump processes
• Predicting Sequences of Traversed Nodes in Graphs using Network Models with Multiple Higher Orders
• Motif-Based Spectral Clustering of Weighted Directed Networks
• Multi-scale Laplacian community detection in heterogeneous networks
• Entrograms and coarse graining of dynamics on complex networks
• Structured networks and coarse-grained descriptions: a dynamical perspective
• Locating Community Smells in Software Development Processes Using Higher-Order Network Centralities
• A generalized voter model with time-decaying memory on a multilayer network
• Epidemic dynamics on metapopulation networks with node2vec mobility
• Community Detection with the Map Equation and Infomap: Theory and Applications
• Continuous stochastic processes with non-local memory
• Driving forces in researchers mobility
• Event Graphs: Advances and Applications of Second-Order Time-Unfolded Temporal Network Models
• Engineering Structural Robustness in Power Grid Networks Susceptible to Coherent Swing Instability
• Towards a generalization of information theory for hierarchical partitions
• Metapopulation models imply non-Poissonian statistics of interevent times
• Flow-based Community Detection in Hypergraphs
• Optimal timescale for community detection in growing networks
• The Atlas for the Aspiring Network Scientist
• Memory-dependent noise-induced resonance and diffusion in non-markovian systems
• Diffusion dynamics and synchronizability of hierarchical products of networks
• A method to compute the communicability of nodes through causal paths in temporal networks
• Single-trajectory map equation
• Impact of temporal connectivity patterns on epidemic process
• Learning the Markov order of paths in a network
• Neural Embeddings of Scholarly Periodicals Reveal Complex Disciplinary Organizations
• Counting Causal Paths in Big Times Series Data on Networks
• Memory Order Decomposition of Symbolic Sequences
• Skeleton coupling: a novel interlayer mapping of community evolution in temporal networks
• Meta-plasticity and memory in multi-level recurrent feed-forward networks
• Coarse-graining nonequilibrium diffusions with Markov chains
• Identifying macroscopic features in foreign visitor travel pathways
• On the statistical distributions of substance moving through the nodes of a channel of network
• Discrete-time model for a substance motion in a channel of a network. Application to a human migration channel
• Quantifying the Impact of Scholarly Papers Based on Higher-Order Weighted Citations
• Networks of monetary flow at native resolution
• Adaptive Shrinkage Estimation for Streaming Graphs
• Consensus dynamics on temporal hypergraphs
• Fragility of spectral clustering for networks with an overlapping structure
• Symbolic walk in regular networks
• Human migration and the motion of substance in a channel of a network
• Thematic recommendations on knowledge graphs using multilayer networks
• Exact Partitioning of High-order Models with a Novel Convex Tensor Cone Relaxation
• Citation Cascade and the Evolution of Topic Relevance
• Graph clustering in industrial networks