Source-linked AI summary
Memory in network flows and its effects on spreading dynamics and community detection
Martin Rosvall, Alcides V. Esquivel, Andrea Lancichinetti, Jevin D. West, Renaud Lambiotte
TL;DR
The paper asks whether first-order network models miss flow dependence on prior locations, and develops second-order Markov models from empirical pathways across diverse systems. These models reveal return and within-community constraints that alter community detection, ranking, and information spreading, while disease attack rates are largely unaffected in the meta-population setting.
Problem
First-order Markov network models ignore the possibility that the next destination depends on where flow came from, limiting pathway representation across integrated systems.
Method
The authors generalize community detection, ranking, and spreading analyses to second-order Markov models using empirical pathways represented as memory networks.
Results
Second-order dynamics reveal return flow, smaller and overlapping modules, altered journal rankings, and slower information spreading, while disease attack rates are negligibly affected in the meta-population model.
Takeaways & Limitations
Using pathway data with memory can reveal actual travel patterns and scholarly organization without adding assumptions, and can make journal rankings more robust to manipulation.
Takeaways & Limitations
The JSTOR corpus excludes Nature and underrepresents physics, engineering, and computer science, although it provides article- and journal-level data needed for memory networks.
Abstract
from arXiv · showhide
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.
Results
Second-order Markov dynamics model flow as depending on both the current and previously visited nodes, revealing statistically significant memory constraints across diverse real-world networks. Accounting for this memory changes detected communities, node rankings, and spreading behavior by preserving return and within-community flow.
- Method: Second-order Markov dynamics represent each state using the currently visited node and the previous step, rather than the current node alone.Memory networks use memory nodes corresponding to directed transitions between physical nodes.
- Empirical evidence: Entropy rates decrease by one to two bits under second-order dynamics, corresponding to a 200%–400% overestimate of effective neighbours in an unweighted interpretation.The entropy decrease indicates that first-order models obscure constraints on flow.
- Empirical evidence: Second-order constraints are statistically significant across most analyzed summary statistics and influential nodes, based on bootstrap resampling and surrogate-data tests.Patients and email networks were exceptions among influential-node analyses.
- Community detection: Second-order dynamics improve community compression and reveal smaller, more informative modules with greater overlap by capturing return flow.In air traffic, Las Vegas separates into eight major modules while Atlanta remains in one; their two-step return rates are 67% and 15%, respectively.
- Ranking: Second-order dynamics reallocate 10% of citation flow and favor journals receiving internal or return flow over multidisciplinary journals dependent on cross-field leakage.Ecology gains flow through high-quality, internal, and returning pathways, whereas multidisciplinary journals such as Science lose flow relative to first-order rankings.
Methods
The methods convert pathway data into networks with and without memory, then evaluate memory-aware community detection using synthetic benchmarks and ergodic dynamics.
- Network construction: Pathways are transformed from weighted itineraries into aggregated bigram and trigram links, yielding standard and memory networks.The standard network represents physical-node transitions, whereas the memory network represents transitions between memory nodes.
- Community detection: Community detection uses a flow-based map equation on memory networks while changing dynamics rather than the compression algorithm.Each memory node is assigned to one module, enabling a modified Infomap search over hard partitions.
- Community detection: Second-order memory reveals overlapping modules in air-travel pathways that first-order dynamics obscure.Out-and-back travel through Las Vegas is represented as two overlapping modules under second-order dynamics.
- Benchmark validation: Infomap for memory networks recovers planted partitions almost perfectly across substantial overlap, whereas first-order dynamics succeed only without overlap.The benchmark evaluates recovery using normalized mutual information and compares memory-aware and standard Infomap variants.
- Ergodicity: Ergodicity is supported by assigning physical-node out-links to dangling memory nodes and allowing random teleportation.These modifications provide fallback transition information when second-order data are insufficient or the memory network is not strongly connected.
1. Data acquisition and processing
The data-processing pipeline represents pathway histories as memory-network transitions, while preserving standard-network aggregates and system-specific preprocessing choices.
- Memory-network representation: Second-order memory networks count length-three pathway segments as trigram transitions between memory nodes.A memory node encodes the current and previously visited physical nodes, and transition probabilities are normalized trigram weights.
- Memory-network representation: Standard networks aggregate pathway occurrences into weighted physical-node links, whereas memory networks retain the preceding node in each transition.The memory representation distinguishes transitions such as #ij → #jk that standard aggregation merges.
- Scope and preprocessing: Most empirical pathways are only three to six steps long, so boundary effects and non-ergodic memory networks require methodological adjustments.The analysis introduces a small teleportation probability for processes that are rarely ergodic without it.
- Memory-network representation: Self-memory nodes encode pathway starts and support initialization, link-weight construction, and teleportation data rather than regular memory-network steps.They are formed by repeating the first physical node and are used differently across datasets.
- Air traffic: Airline data contain 19,415,369 itineraries across 464 US airports, with average pathlength 3.3 and predominantly short routes.The city analysis aggregates airports within 50 kilometres and includes the passenger’s home city to capture return traffic.
- Journal data: The journal network uses article-level JSTOR citations to construct journal trigrams from citing and cited articles.The corpus contains 2,227 journals, 8,227,537 citations, and 1,787,351 unique articles.
- Journal data: JSTOR provides the required article- and journal-level data but does not represent the full universe of scholarly content.Physics, engineering, and computer science are not well represented, and Nature is absent.
- Taxi data: Taxi trajectories are mapped onto a 20 x 20 hexagonal grid, and consecutive hexagon triplets are weighted by their observed frequency.The dataset contains 25,000 taxi trajectories, with hexagons approximately 375 metres across.
2. Significance analysis with resampling
Resampling and surrogate tests assess whether observed memory effects are statistically supported and whether second-order dynamics adequately capture typical pathway memory.
- Statistical validation: The analysis uses bootstrap resampling for summary statistics and surrogate data testing to estimate Markov order.These procedures validate results against sampling variation and a first-order Markov null hypothesis.
- Bootstrap analysis: Each dataset receives 100 bootstrap replicas generated by resampling pathway weights with replacement.For journal data, replicas instead repeat the article-citation chaining procedure because the network is not directly built from pathways.
- Bootstrap analysis: The reported bootstrap interval retains the middle 80 of 100 estimates after removing the ten smallest and ten largest.This produces a 90% bootstrap percentile confidence interval.
- Surrogate testing: Surrogate testing randomizes predecessor-successor pairings to destroy memory while preserving the relevant marginal structure.The first-order Markov hypothesis is rejected when the p-value is below 0.10.
- Air-traffic memory: Air traffic shows significant memory through Markov order four, but 73% of itineraries have length three or shorter, making second order representative of typical dynamics.Conditional entropy is used to measure destination uncertainty given previously visited airports.
- Model order: Entropy drops by 1.1 bits from first to second order but only 0.3 bits from second to third order.Both changes are statistically significant, supporting second order as a balance between model complexity and accuracy.
- Cross-system results: Bootstrap analysis finds a significant second-order effect in all examined systems, although patient estimates vary more because many pathways are sparsely observed.Airports and cities have sufficiently rich data for more than two significant digits in reported statistics.
3. Community detection of memory networks
Community detection compares first- and second-order flow structure with the map equation, using memory nodes to represent dynamics while constraining the module search.
- Empirical illustration: Second-order dynamics expose two overlapping modules in the San Francisco–Las Vegas–New York example, whereas first-order dynamics favor one module.The distinction follows from the strong out-and-back travel pattern involving Las Vegas.
- Map equation: The map equation selects node assignments that minimize the random walk’s description length within and between modules.Its entropy terms quantify movement between modules and within individual modules.
- Method: Memory-aware community detection applies the map-equation search to memory networks so first- and second-order comparisons alter dynamics, not the underlying compression mechanics.Memory nodes are assigned to modules while the walker’s description reflects movements between physical nodes.
M2 NLN +w
The analysis interprets link clustering and clique percolation as imposing second-order flow constraints that increase persistence within overlapping modules. Empirical and methodological results indicate that second-order dynamics produce smaller, more overlapping modules than first-order dynamics.
- Link clustering: Link clustering reduces switching between modules by lowering a transition rate from 1/2 to 1/7 at a shared keystone node.The reduction follows from similarity-weighted links between memory nodes.
- Clique percolation: Clique percolation identifies modules as maximal sets of nodes participating in percolations of adjacent cliques.For triangles, adjacency means sharing one side.
- Flow interpretation: Both link clustering and clique percolation can be interpreted as inferring second-order Markov constraints from standard network structure.These constraints increase module persistence and support efficient flow compression.
- Community detection: Second-order Markov dynamics confine flow to smaller and more overlapping modules than first-order dynamics.Bootstrap analysis found a significant structural difference between the two dynamics.
- Results: The community-detection analysis and related ranking results are summarized in Supplementary Table S3.The table also reports bootstrap 10th and 90th percentiles.
4. Modelling second-order Markov effects
The paper develops a fitted network memory model to represent second-order flow through return, triangular, and exploratory transitions. It uses KL-divergence optimization and applies the model to explain effects on ranking, finding that memory parameters improve empirical pathway modelling and that return behavior is especially important.
- Memory model: The memory model coarse-grains second-order Markov data into return, triangular, and exploratory transitions.Their prevalences are controlled by parameters r2, r3, and r3<.
- Fitting: The model is fitted by minimizing KL divergence between observed trigram transition probabilities and model transition probabilities.The normalization r2+r3+r3< = 1 removes r3< as an independent optimization variable.
- Fitting results: Including memory through r2, r3, and r3< significantly improves modelling accuracy in most analysed networks.The relative KL reduction compares the optimized model with an unbiased first-order Markov model.
- Fitting results: The reduction from relaxing r3 = r3< tends to be small, making return-step prevalence the most important ingredient for realistic pathways.The fitted parameters are summarized in Supplementary Table S4.
- Robustness: The optimization has a unique extremum and bootstrap analysis indicates that the optimal parameters are robust.The KL-divergence landscape is described as smooth under variation of r2 and r3.
- Ranking: Higher r2 tends to favor reciprocated links and links belonging to many triangles in ranking analyses.The effect reflects the model’s bias toward return steps and related higher-order paths.