Reducing Spreading Processes on Networks to Markov Population Models

Gerrit Großmann, Luca Bortolussi

TL;DR

This paper introduces a novel method to simplify complex spreading processes on networks by transforming them into Markov Population Models (MPMs). This reduction is achieved through a "lumping" technique that groups similar network states, making computational analysis feasible for large, realistic networks where direct simulation is impossible.

What Problem Does This Paper Address?

Analyzing spreading phenomena (like disease outbreaks or information diffusion) on networks is crucial, but computationally challenging. The core issue is the sheer size of the "state space" – all possible configurations of nodes being in different states (e.g., susceptible, infected). For a network with N nodes and S states per node, the state space grows as S^N, quickly becoming intractable for even moderately sized networks. Existing methods often struggle to balance accuracy with computational feasibility, especially when considering the network's topology.

Methods

The paper proposes a "lumping" scheme to reduce the state space of continuous-time Markov chains (CTMCs) that model these spreading processes. The core idea is to partition the network's nodes and then apply a "counting abstraction" to these partitions.

  • Node Partitioning: The network's nodes are divided into several groups (partitions). The paper explores different strategies for this partitioning, including random assignment, degree-based clustering, and spectral embedding.
  • Counting Abstraction: Instead of tracking the exact state of every single node, the method counts the number of nodes in each state within each partition. Two main types of counting are proposed:
  • Node-Based Counting: Counts the number of nodes in each state per partition.
  • Edge-Based Counting: Counts the number of edges between nodes in different states and partitions. This method is more refined and requires a "dummy node" to properly account for node states within partitions.
  • Markov Population Models (MPMs): The lumping process naturally leads to an MPM representation. In an MPM, the state is a vector representing the number of entities (species) in different categories. Here, the "species" are combinations of node states and partitions. This representation allows leveraging a rich set of existing MPM analysis techniques.

Datasets

Not discussed in the paper. The authors use a synthetic toy network with 13 nodes and 2 states for their experiments, generated using the Erdős-Rényi graph model.

Key Insights and Ideas

  • Bridging the Gap: The paper successfully bridges the gap between complex network dynamics and the well-established analytical tools of Markov Population Models.
  • Lumping as a General Tool: The proposed lumping scheme is general and can be applied to various epidemic models (like SIS) and different network structures.
  • Trade-off Management: The core contribution lies in providing a controllable trade-off between the size of the reduced state space and the accuracy of the approximation. By adjusting the number of partitions and the type of counting abstraction, users can tailor the model to their computational resources and desired precision.
  • Edge-Based Abstraction Superiority: The edge-based counting abstraction generally offers a better trade-off between state space size and accuracy compared to node-based counting, especially when adding more partitions.
  • Partitioning Strategy Matters: The choice of node partitioning strategy (degree-based, spectral, random) significantly impacts the accuracy and efficiency of the lumping. Spectral and degree-based partitioning tend to yield similar, good results, while random partitioning is less effective.

Key Results

The paper demonstrates that their lumping method can significantly reduce the state space of epidemic models on networks. For instance, they show that a model with 8192 states can be reduced to a much smaller number of states (e.g., around 2000 states in their experiments) while maintaining a high degree of accuracy. The edge-based counting abstraction consistently showed better performance in terms of the accuracy-state space size trade-off.

Limitations and Future Work

  • Scalability of MPMs: While the lumping reduces the CTMC state space, the resulting MPM can still have a large number of "species" (population variables), which can limit the applicability of some MPM analysis techniques.
  • Determining Optimal Parameters: It's not yet clear which MPM analysis techniques (e.g., moment closure, linear noise approximation) perform best on these lumped models and how they scale with the size of the network and the number of species.
  • Exploring Other Abstractions: The authors suggest exploring other types of counting abstractions, such as neighborhood-based ones.
  • Advanced Partitioning: Further investigation into more sophisticated graph partitioning methods could yield even better results.
  • Direct MPM Construction: The paper outlines a direct construction of MPMs without explicitly building the full CTMC, which is a promising avenue for further research, especially for edge-based abstractions where an approximation is introduced.

Summary updated

Abstract

Stochastic processes on complex networks, where each node is in one of several compartments, and neighboring nodes interact with each other, can be used to describe a variety of real-world spreading phenomena. However, computational analysis of such processes is hindered by the enormous size of their underlying state space. In this work, we demonstrate that lumping can be used to reduce any epidemic model to a Markov Population Model (MPM). Therefore, we propose a novel lumping scheme based on a partitioning of the nodes. By imposing different types of counting abstractions, we obtain coarse-grained Markov models with a natural MPM representation that approximate the original systems. This makes it possible to transfer the rich pool of approximation techniques developed for MPMs to the computational analysis of complex networks' dynamics. We present numerical examples to investigate the relationship between the accuracy of the MPMs, the size of the lumped state space, and the type of counting abstraction.
BibTeX
@inproceedings{gromann2019reducing,
  author = {Gerrit Großmann and Luca Bortolussi},
  title = {{Reducing Spreading Processes on Networks to Markov Population Models}},
  booktitle = {QEST},
  year = {2019},
  doi = {10.1007/978-3-030-30281-8\_17},
}

Loading related content...

Figure