Lumping the Approximate Master Equation for Multistate Processes on Complex Networks

Gerrit Großmann, Charalampos Kyriakopoulos, Luca Bortolussi, Verena Wolf

Abstract

Complex networks play an important role in human society and in nature. Stochastic multistate processes provide a powerful framework to model a variety of emerging phenomena such as the dynamics of an epidemic or the spreading of information on complex networks. In recent years, mean-field type approximations gained widespread attention as a tool to analyze and understand complex network dynamics. They reduce the model's complexity by assuming that all nodes with a similar local structure behave identically. Among these methods the approximate master equation (AME) provides the most accurate description of complex networks' dynamics by considering the whole neighborhood of a node. The size of a typical network though renders the numerical solution of multistate AME infeasible. Here, we propose an efficient approach for the numerical solution of the AME that exploits similarities between the differential equations of structurally similar groups of nodes. We cluster a large number of similar equations together and solve only a single lumped equation per cluster. Our method allows the application of the AME to real-world networks, while preserving its accuracy in computing estimates of global network properties, such as the fraction of nodes in a state at a given time.

Introduction

Understanding the spread of epidemics or information across complex networks requires sophisticated stochastic models. The Approximate Master Equation (AME) is widely considered the "gold standard" for accuracy in this field because it accounts for the full neighborhood state of a node. However, the AME faces a significant "curse of dimensionality." The number of required differential equations grows combinatorially with the number of possible node states and the maximum node degree ($k_{max}$). For large-scale networks with high-degree hubs, solving the original AME becomes computationally impossible. This research introduces a "lumping" technique to make AME tractable for massive, heterogeneous networks without sacrificing its signature accuracy.

Methodology: The Lumping Approach

The core of the proposed method is a model reduction technique called "lumping." It operates on the principle that nodes with statistically similar local structures—defined by their degree and neighborhood composition—will exhibit similar dynamical behavior.

A node in state $s$ with a neighborhood configuration $(3, 1)$, representing three neighbors in state $s$ and one in state $s'$.

Instead of solving a unique equation for every possible neighborhood configuration, the method groups these configurations into clusters and solves one "lumped" equation per cluster. The process involves several key components:

  • Two-Stage Clustering: Decoupling a node's neighborhood into its degree (number of neighbors) and its proportionality (the mix of states among those neighbors).
  • Hierarchical Degree Clustering: Merging rare high-degree nodes into single clusters while maintaining higher resolution for more common low-degree nodes, which is particularly effective for real-world power-law networks.
  • Proportionality Clustering: Partitioning the "unit simplex"—a geometric representation of neighborhood state distributions—into sub-intervals.
Illustration of transitions between neighborhood configurations, which the lumping method simplifies by clustering similar states.

For networks with extremely high degrees, the authors utilize "approximative generation," where cluster centers are used to generate equations, bypassing the need to iterate over billions of potential neighborhood vectors.

Results and Performance

The method was validated using synthetic networks of 100,000 nodes across various dynamical models, including SIR (epidemic), Rumor Spreading, and Competing Pathogens.

Key findings include:

  • Significant Speedups: In the SIR model, the lumped AME achieved a ~33x speedup, running in 235 seconds compared to 7,848 seconds for the original version.
  • Extreme Compression: High accuracy was maintained while using less than 5% of the original number of equations. In a scenario with $k_{max} = 500$, the lumped AME reduced a system of 21 million equations to just 8,500 clusters.
  • High Fidelity: The results from the lumped AME were nearly indistinguishable from the original AME and aligned closely with computationally expensive Monte-Carlo simulations.

Discussion and Future Directions

While the lumping technique provides a massive leap in computational efficiency, some limitations remain. The current clustering is static; the authors suggest that "on-the-fly" adaptive clustering could further optimize performance by adjusting clusters as dynamics evolve. Additionally, while the method excels at approximating the AME, the AME itself can struggle with highly competitive processes (like competing pathogens), indicating that the underlying mean-field assumptions may require further refinement for specific complex scenarios. Future work will also explore applying these techniques to adaptive networks where the topology changes alongside the node states.

Summary updated

Abstract

Complex networks play an important role in human society and in nature. Stochastic multistate processes provide a powerful framework to model a variety of emerging phenomena such as the dynamics of an epidemic or the spreading of information on complex networks. In recent years, mean-field type approximations gained widespread attention as a tool to analyze and understand complex network dynamics. They reduce the model's complexity by assuming that all nodes with a similar local structure behave identically. Among these methods the approximate master equation (AME) provides the most accurate description of complex networks' dynamics by considering the whole neighborhood of a node. The size of a typical network though renders the numerical solution of multistate AME infeasible. Here, we propose an efficient approach for the numerical solution of the AME that exploits similarities between the differential equations of structurally similar groups of nodes. We cluster a large number of similar equations together and solve only a single lumped equation per cluster. Our method allows the application of the AME to real-world networks, while preserving its accuracy in computing estimates of global network properties, such as the fraction of nodes in a state at a given time.
BibTeX
@inproceedings{gromann2018lumping,
  author = {Gerrit Großmann and Charalampos Kyriakopoulos and Luca Bortolussi and Verena Wolf},
  title = {{Lumping the Approximate Master Equation for Multistate Processes on Complex Networks}},
  booktitle = {QEST},
  year = {2018},
  url = {https://openreview.net/forum?id=aoW-ZpK0_Jp},
}

Loading related content...

Figure