Reducing Spreading Processes on Networks to Markov Population Models
Gerrit Großmann Luca Bortolussi










G. Großmann and L. Bortolussi



Saarland University, 66123 Saarbrücken, Germany
gerrit.grossmann@uni-saarland.de
University of Trieste, Trieste, Italy 

lbortolussi@units.it


Reducing Spreading Processes on Networks to Markov Population Models
    Gerrit Großmann()10000-0002-4933-447X Luca Bortolussi1,20000-0001-8874-4001 

    
=================================================================================




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.





















§ INTRODUCTION
 
Computational modeling and analysis of dynamic processes on networked systems is a wide-spread and thriving research area. In particular, much effort has been put into the study of spreading phenomena <cit.>. 

Arguably, the most common formalism for spreading processes is the so-called usceptible-nfected-usceptible () model with its variations <cit.>.


In the  model, each node is either infected () or susceptible (). Infected nodes propagate their infection to neighboring susceptible nodes and become susceptible again after a random waiting time. 
Naturally, one can extend the number of possible node states (or compartments) of a node. For instance, the  model introduces an additional recovered state in which nodes are immune to the infection.

-type models are remarkable because—despite their simplicity—they allow the emergence of complex macroscopic phenomena guided by the topological properties of the network.
There exists a wide variety of scenarios which can be described using the -type formalism.
For instance, the  model has been successfully used to study the spread of many different pathogens like influenza <cit.>, dengue fever <cit.>, and SARS <cit.>. 

Likewise, -type models have shown to be extremely useful for analyzing and predicting the spread of opinions <cit.>,

rumors <cit.>, and memes <cit.> in online social networks. Other areas of applications include the modeling of neural activity <cit.>, the spread of computer viruses <cit.> 

as well as blackouts in financial institutions <cit.>.


The semantics of -type processes can be described using a continuous-time Markov chain (CTMC) <cit.> (cf. Chapter <ref> for details). Each possible assignment of nodes to the two node states  and  constitutes an individual state in the CTMC (here referred to as network state to avoid confusion[In the following, we will use the term CTMC state and network state interchangeably.]). Hence, the CTMC state space grows exponentially with the number of nodes, which renders the numeral solution of the CTMC infeasible for most realistic contact networks. 

This work investigates an aggregation scheme that lumps similar network states together and thereby reduces the size of the state space. 
More precisely, we first partition the nodes of the contact network. 
After which, we impose a counting abstraction on each partition. 
We only lump two networks states together when their corresponding counting abstractions coincide on each partition. 

As we will see, the counting abstraction induces a natural representation of the lumped CTMC as a Markov Population Model (MPM). In an MPM, the CTMC states are vectors which, for different types of species, count the number of entities of each species. The dynamics can elegantly be represented as species interactions. More importantly, a very rich pool of approximation techniques has been developed on the basis of MPMs, which can now be applied to the lumped model. These include efficient simulation techniques <cit.>,

dynamic state space truncation <cit.>, moment-closure approximations <cit.>, 

linear noise approximation <cit.>, and hybrid approaches <cit.>.






The remainder of this work is organized as follows: Section <ref> shortly revises related work, Section <ref> formalized -type models and their CTMC semantics. Our lumping scheme is developed in Section <ref>. In Section <ref>, we show that the lumped CTMCs have a natural MPM representation.  
Numerical results are demonstrated in in Section <ref> and some conclusions in Section <ref> complete the paper and identify open research problems.  




§ RELATED WORK


The general idea behind lumping is to reduce the complexity of a system by aggregating (i.e., lumping) individual components of the system together.
Lumping is a popular model reduction technique which has been used to reduce the number of equations in a system of ODEs and the number of states in a Markov chain, in particular in the context of biochemical reaction networks <cit.>. 

Generally speaking, one can distinguish between exact and approximate lumping <cit.>.

Most work on the lumpability of epidemic models has been done in the context of exact lumping <cit.>. The general idea is typically to reduce the state space by identifying symmetries in the CTMC which themselves can be found using symmetries (i.e., automorphisms) in the contact network.
Those methods, however, are limited in scope because these symmetries are infeasible to find in real-world networks and the state space reduction is not sufficient to make realistic models small enough to be solvable. 

This work proposes an approximate lumping scheme.
Approximate lumping has been shown to be useful when applied to mean-field approximation approaches of epidemic models like the degree-based mean-field and pair approximation equations <cit.>, as well as the approximate master equation <cit.>. 
However, mean-field equations are essentially inflexible as they do not take topological properties into account or make unrealistic independence assumptions between neighboring nodes. 

Moreover, <cit.> proposed using local symmetries in the contact network instead of automorphisms to construct a lumped Markov chain.
This scheme seems promising, in particular on larger graphs where automorphisms often do not even exist, however, the limitations for real-world networks due to a limited amount of state space reduction and high computational costs seem to persist.

Conceptually similar to this work is also the unified mean-field framework (UMFF) proposed by Devriendt et al. in <cit.>. Devriendt et al. also partition the nodes of the contact network but directly derive a mean-field equation from it. In contrast, this work focuses on the analysis of the lumped CTMC and its relation to MPMs. Moreover, we investigate different types of counting abstractions, not only node based ones. 




§ SPREADING PROCESSES






Let 𝒢=(𝒩, ℰ) be a an undirected graph without self-loops.
At each time point t ∈ℝ_≥ 0 each node occupies one of m different node states, denoted by 𝒮 = {s_1, s_2, …, s_m} (typically, 𝒮={𝚂,𝙸} ).
Consequently, the network state is given by a labeling x: 𝒩→𝒮.
We use 

    𝒳 = {x | x: 𝒩→𝒮}

to denote all possible labelings. 𝒳 is also the state space of the underlying CTMC. As each of the |𝒩| nodes occupies one of m states, we find that |𝒳| = |𝒮|^|𝒩|.

A set of stochastic rules determines the particular way in which nodes change their corresponding node states. Whether a rule can be applied to a node depends on the state of the node and of its immediate neighborhood.


The neighborhood of a node is modeled as a vector 𝐦∈ℤ_≥0^|𝒮| where 𝐦[s] denotes the number of neighbors in state s ∈𝒮 (we assume an implicit enumeration of states).
Thus, the degree (number of neighbors, denoted by k) of a node is equal to the sum over its associated neighborhood vector, that is, k=∑_s ∈𝒮𝐦[s].

The set of possible neighborhood vectors is denoted as 

    ={∈^|𝒮||∑_s∈𝒮[s] ≤} ,

where  denotes the maximal degree in a given network. 

Each rule is a triplet s_1  s_2 (s_1,s_2 ∈𝒮, s_1 ≠ s_2), which can be applied to each node in state s_1.
When the rule fires it transforms the node from s_1 into s_2. The rate at which a rule fires is specified by the rate function f: ℳ→ℝ_≥ 0 and depends on the node's neighborhood vector. 
The time delay until the rule is applied to the network state is drawn from an exponential distribution with rate f(). Hence, higher rates correspond to shorter waiting times.
For the sake of simplicity and without loss of generality, we assume that for each pair of states s_1, s_2 there exists at most one rule that transforms s_1 to s_2.

In  the  well-known  model,  infected  nodes propagate their infection to susceptible neighbors. Thus, the rate at which a susceptible node becomes infected is proportional to its number of infected neighbors:

    XXXX𝚂𝙸XXwithX f() = λ·[𝙸]  ,

where λ∈ℝ_≥ 0 is a rule-specific rate constant (called infection rate) and [𝙸] denotes the number of infected neighbors. 
Furthermore, a recovery rule transforms infected nodes back to being susceptible:

    XXXX𝙸𝚂XXwithX f() = μ , ·[𝙸]

where μ∈ℝ_≥ 0 is a rule-specific rate constant called recovery rate.

A variation of the  model is the  model where no curing rule exists and all nodes (that are reachable from an infected node) will eventually end up being infected.  
Intuitively, each rule tries to fire at each position n∈𝒩 where it can be applied. The rule and node that have the shortest waiting time win and the rule is applied there. This process is repeated until some stopping criterion is fulfilled. 








 §.§ CTMC Semantics




Formally, the semantics of the -type processes can be given in terms of continuous-time Markov Chains (CTMCs). The state space is the set of possible network states 𝒳. The CTMC has a transition from state x to x' (x,x' ∈𝒳, x≠ x') if there exists a node n ∈𝒩 and a rule s_1  s_2 such that the application of the rule to n transforms the network state from x to x'. The rate of the transition is exactly the rate f() of the rule when applied to n. 


We use q(x,x') ∈ℝ_≥ 0 to denote the transition rate between two network states. Fig. <ref> illustrates the CTMC corresponding to an  process on a small toy network. 





Explicitly computing the evolution of the probability of x ∈𝒳 over time with an ODE solver, using numerical integration, is only possible for very small contact networks, since the state space grows exponentially with the number of nodes.
Alternative approaches include sampling the CTMC, which can be done reasonably efficiently even for comparably large networks <cit.> but is subject to statistical inaccuracies and is mostly used to estimate global properties.



§ APPROXIMATE LUMPING

Our lumping scheme is composed of three basic ingredients:


Node Partitioning: 
The partitioning over the nodes 𝒩 that is explicitly provided. 

Counting Pattern: The type of features we are counting, i.e., nodes or edges. 

Implicit State Space Partitioning:  The CTMC state space is implicitly partitioned by counting the nodes or edges on each node partition.



We will start our presentation discussing the partitioning of the state space, then showing how to obtain it from a given node partitioning and counting pattern. To this end, we use 𝒴 to denote the new lumped state space and assume that there is a surjective[If ℒ is not surjective, we consider only the image of ℒ to be the lumped state space. ] lumping function 

    ℒ: 𝒳→𝒴

that defines which network states will be lumped together. Note that the lumped state space is the image of the lumping function and that all network states x ∈𝒳 which are mapped to the same y ∈𝒴 will be aggregated.

Later in this section, we will discuss concrete realizations of ℒ. 
In particular, we will construct ℒ based on a node partitioning and a counting abstraction of our choice.
Next, we define the the transition rates q(y,y') (where y,y' ∈𝒴, y ≠ y') between the states of the lumped Markov chain:

    q(y,y') = 1/|ℒ^-1(y)|.x ∈ℒ^-1(y).x' ∈ℒ^-1(y') q(x,x') .

This is simply the mean transition rate at which an original state from x goes to some x'∈ℒ^-1(y').
Technically, Eq. (<ref>) corresponds to the following lumping assumption: we assume that at each point in time all network states belonging to a lumped state y are equally likely. 





 §.§ Partition-Based Lumping









Next, we construct the lumping function ℒ. Because we want to make our lumping aware of the contact network's topology, we assume a given partitioning 𝒫 over the nodes 𝒩 of the contact network.
That is,  𝒫⊂ 2^𝒩 and ⋃_P ∈𝒫P = 𝒩 and all P ∈𝒫 are disjoint and non-empty. 
Based on the node partitioning, we can now impose different kinds of counting abstractions on the network state. This work considers two types: counting nodes and counting edges.

The counting abstractions are visualized in Fig. <ref>. A full example of how a lumped CTMC of an 𝚂𝙸 model is constructed using the node-based counting abstraction is given in Fig. <ref>.

































  §.§.§ Node-Based Counting Abstraction

We count the number of nodes in each state and partition. Thus, for a given network state x ∈𝒳, we use y(s,P) to denote the number of nodes in state s ∈𝒮 in partition P∈𝒫. The lumping function ℒ projects x to the corresponding counting abstraction. Formally: 

    𝒴 = {y | y: 𝒮×𝒫→ℤ_≥ 0}
    (   ℒ(x) = y   
    with:   y(s,P) = |{ n ∈𝒩| X(n) = s, n ∈ P }|  .




  §.§.§ Edge-Based Counting Abstraction

Again, we assume that a network state x and a node partitioning 𝒫 are given.
Now we count the edges, that is for each pair of states s,s' ∈𝒮 and each pair of partitions P,P' ∈𝒫, we count y(s,P,s',P') which is the number of edges (n,n') ∈ℰ
where x(n)=s, n ∈ P, x(n')=s', n' ∈ P'. Note that this includes cases where P=P' and s=s'. However, only counting the edges does not determine how many nodes there are in each state (see Fig. <ref> for an example). 

In order to still have this information encoded in each lumped state, we slightly modify the network structure by adding a new dummy node n_⋆ and connecting each node to it . The dummy node has a dummy state denoted by ⋆ which never changes, and it can be assigned to a new dummy partition P_⋆. Formally,

    𝒩 := 𝒩∪{n_⋆}𝒮 := 𝒮∪{⋆}  
    L(n_⋆) = ⋆𝒫 := 𝒫∪{P_⋆}
       ℰ := ℰ∪{(n,n_⋆) | n ∈𝒩, n ≠ n_⋆} .

Note that the rate function f ignores the dummy node.
The lumped representation is then given as:

    𝒴 = {y |  y: 𝒮×𝒫×𝒮×𝒫→ℤ_≥ 0}
       ℒ(x) = y (
    with:   y(s,P,s',P') = |{ (n,n') ∈ℰ| x(n) = s, n ∈ P,  x(n')=s', n' ∈ P' }|





  §.§.§ Neighborhood-Based Counting Abstraction

The neighborhood-based abstraction is a further refinement of the edge-based abstraction and inspired by the work of James P. Gleeson <cit.>.
We define 

    𝒴 = {y | y: 𝒮×𝒫×𝒱→ℤ_≥ 0} ,

to gain an abstraction that counts the number of nodes in each state s, in each partition P with each possible partition-neighborhood 𝐯. 



  §.§.§ Coarse-Grained Counting

Instead of exactly counting the patterns in the network we can also project to a more coarse-grain abstraction. That is, we only store of the number of patterns lies in a certain range of values. Formally, we define the image of the counting function y to be a partition over ℤ_≥ 0.





  §.§.§ Example

Fig. <ref> illustrates how a given partitioning and the node-based counting approach induces a lumped CTMC. 
The partitions induced by the edge-based counting abstracting are also shown. In this example, the edge-based lumping aggregates only isomorphic network states.









 §.§ Graph Partitioning

Broadly speaking, we have three options to partition the nodes based on local features (e.g., its degree) or global features (e.g.,  communities in the graph) or randomly.    
As a baseline, we use a random node partitioning. Therefore, we fix the number of partitions and randomly assign each node to a partition while enforcing that all partitions have, as far as possible, the same number of elements.

Moreover, we investigate a degree-based partitioning, where we define the distance between to nodes n,n' as their relative degree difference (similar to <cit.>):

    d_k(n,n') = | k_n - k_n'|/max(k_n,k_n') .

We can then use any reasonable clustering algorithm and build partitions (i.e., clusters) with the distance function. In this work, we focus on bottom-up hierarchical clustering as it provides the most principled way of precisely controlling the number of partitions.
Note that, for the sake of simplicity (in particular, to avoid infinite distances), we only consider contact networks where each node is reachable from every other node. We break ties arbitrarily. 

To get a clustering considering global features we use a spectral embedding of the contract network. Specifically, we use the <spectral_layout> function from the <NetworkX> Python-package <cit.> with three dimensions and perform hierarchical clustering on the embedding.
In future research, it would be interesting to compute node distances based on more sophisticated graph embedding as the ones proposed in <cit.>.
Note that in the border cases |𝒫|=1 and |𝒫|=|𝒩| all methods yield the same partitioning.



§ MARKOV POPULATION MODELS

Markov Population Models (MPMs) are a special form of CTMCs where each CTMC state is a population vector over a set of species. We use 𝒵 to denote the finite set of species (again, with an implicit enumeration) and 𝐲∈ℤ_≥ 0^|𝒵| to denote the population vector. Hence, 𝐲[z] identifies the number of entities of species z.
The stochastic dynamics of MPMs is typically expressed as a set of reactions ℛ, each reaction, (α, 𝐛) ∈ℛ, is comprised of a propensity function α: ℤ_≥ 0^|𝒵|→ℝ_≥ 0 and a change vector 𝐛∈ℤ^|𝒵|. When reaction (α, 𝐛) is applied, the system moves from state 𝐲 to state 𝐲+𝐛. The corresponding rate is given by the propensity function. Therefore, we can rewrite the transition matrix of the CTMC as[Without loss of generality, we assume that different reactions have different change vectors. If this is not the case, we can merge reactions with the same update by summing their corresponding rate functions.]:

    q(𝐲,𝐲') = 
    α(𝐲)     if ∃ (α,𝐛) ∈ℛ, 𝐲' =  𝐲+𝐛
    
    0           otherwise
     .



Next, we show that our counting abstractions have a natural interpretation as MPMs.





 §.§ Node-Based Abstraction

First, we define the set of species 𝒵. Conceptually, species are node states which are aware of their partition:

    𝒵 = { (s,P) | s ∈𝒮, P ∈𝒫} .

Again, we assume an implicit enumeration of 𝒵. We use z.s and z.P to denote the components of a give species z. 

We can now represent the lumped CTMC state as a single population vector 𝐲∈ℤ_≥ 0^|𝒵|, where 𝐲[z] the number of nodes belonging to species z (i.e., which are in state z.s and partition z.P). 
The image of the lumping function ℒ, i.e. the lumped state space 𝒴, is now a subset of
non-negative integer vectors: 𝒴⊂ℤ_≥ 0^|𝒵|.

Next, we express the dynamics by a set of reactions.
For each rule r = s_1  s_2 and each partition P ∈𝒫, we define a reaction (α_r,P,𝐛_r,P) with propensity function as:

    α_r,P:   𝒴→ℝ_≥ 0
    α_r,P(𝐲) =   1/ℒ^-1(𝐲)x ∈ℒ^-1(𝐲)n ∈ P 
     f(_x,n) 1_x(n)=s_1 ,

where _x,n denotes the neighborhood vector of n in network state x. Note that this is just the instantiation of Equation <ref> to the MPM framework.


The change vector 𝐛_r,P∈ℤ^|𝒵| 

is defined element-wise as:

    𝐛_r,P[z] = 
    
    1     if z.s=s_2,P = z.P
    
    -1            if z.s=s_1,P = z.P
    
    0           otherwise
     .

Note that s_1, s_2 refer to the current rule and z.s to the entry of 𝐛_r,P.













 §.§ Edge-Based Counting Abstraction

We start by defining a species neighborhood.
The species neighborhood of a node n is a vector 𝐯∈ℤ_≥ 0^|𝒵|, where 𝐯[z] denotes the number of neighbors of species z. We define 𝒱_n to be the set of possible species neighborhoods for a node n, given a fixed contact network and partitioning. 
Note that we still assume that a dummy node is used to encode the number of states in each partition.


Assuming an arbitrary ordering of pairs of states and partitions, we define




    𝒵 = { (s_source,P_source,s_target,P_target) |    s_source,s_target∈𝒮, P_source,P_target∈𝒫, 
        
    (s_source,P_source) ≤ (s_target,P_target)  } .


Let us define 𝒱_𝒫 to be the set of partition neighborhoods all nodes in P can have:

    𝒱_P = ⋃_n ∈ P𝒱_n  .

For each rule r = s_1  s_2, and each partition P ∈𝒫, and each 𝐯∈𝒱_P, we define a propensity function α_r,P,𝐯 with:


    α_r,P,𝐯:   𝒴→ℝ_≥ 0
    α_r,P,𝐯(𝐲) =   1/ℒ^-1(𝐲)x ∈ℒ^-1(𝐲)  n ∈ P 
     f(_x,n) 1_x(n)=s_1, V(n)=𝐯 .

Note that the propensity does not actually depend on 𝐯, it is simply individually defined for each 𝐯. The reason for this is that the change vector depends on the a node's species neighborhood. To see this, consider a species z = (s_source,P_source,s_target,P_target), corresponding to edges connecting a node in state s_source and partition P_source to a node in state s_target and partition P_target. There are two scenarios in which the corresponding counting variable has to change: (a) when the node changing state due to an application of rule r is the source node, and (b) when it is the target node. Consider case (a); we need to know how many edges are connecting the updated node (which was in state s_1 and partition P) to a node in state  s_target and partition P_target. This information is stored in the vector  𝐯, specifically in position [s_target,P_target]. The case in which the updated node is the target one is treated symmetrically. This gives rise to the following definition: 

    𝐛_r,P,𝐯[z] = 
    [z.s_target,z.P_target]            if s_2 = z.s_source, P=z.P_source
    
    -[z.s_target,z.P_target]            if s_1 = z.s_source, P=z.P_source
    [z.s_source,z.P_source]            if s_2 = z.s_target, P=z.P_target
    
    -[z.s_source,z.P_source]            if s_1 = z.s_target, P=z.P_target
    
    0           otherwise
     .



The first two lines of the definition handle cases in which the node changing state is the source node, while the following two lines deal with the case in which the node changing state appears as target.












Fig. <ref> illustrates how a lumped network state is influenced by the application of an infection rule.





 §.§ Direct Construction of the MPM

Approximating the solution of an 𝚂𝙸𝚂-type process on a contact network by lumping the CTMC first, already reduces the computational costs by many orders of magnitude. However, this scheme is still only applicable when it is possible to construct the full CTMC in the first place. Recall that the number of network states is exponential in the number of nodes of the contact network, that is,
|𝒳| = |𝒮|^|𝒩|.


However, in recent years, substantial effort was dedicated to the analysis of very small networks <cit.>. One reason is that when the size of a network increases, the (macro-scale) dynamics becomes more deterministic because stochastic effects tend to cancel out. For small contact networks, however, methods which capture the full stochastic dynamics of the system, and not only the mean behavior, are of particular importance.

A substantial advantage of the reduction to MPM is the possibility of constructing the lumped CTMC without building the full CTMC first. In particular, this can be done exactly for the node counting abstraction. On the other hand, for the edge counting we need to introduce an extra approximation in the definition of the rate function, roughly speaking introducing an approximate probability distribution over neighboring vectors, as knowing how many nodes have a specific neighboring vector requires us full knowledge of the original CTMC. 
We present full details of such direct construction in Appendix <ref>.



 §.§ Complexity of the MPM



The size of the lumped MPM is critical for our method, as it determines which solution techniques are computationally tractable and provides guidelines on how many partitions to choose. There are two notions of size to consider:
(a) the number of population variables and (b) the number of states of the underlying CTMC. While the latter governs the applicability of numerical solutions for CTMCs, the former controls the complexity of a large number of approximate techniques for MPMs, like mean field or moment closure. 




  
Node-based abstraction.
In this abstraction, the population vector is of length |𝒮|· |𝒫|, i.e. there is a variable for each node state and each partition. 

Note that the sum of the population variables for each partition P is |P|, the number of nodes in the partition. This allows us to count easily the number of states of the CTMC of the population model: for each partition, we need to subdivide |P| different nodes into |𝒮| different classes, which can be done in  |P|+|𝒮|-1|𝒮|-1ways, giving a number of CTMC states exponential in the number |𝒮| of node states and |𝒫| of partitions, but polynomial in the number of nodes:

    |𝒴| = 1.2∏_P ∈𝒫|P|+|𝒮|-1|𝒮|-1 .






  
Edge-based abstraction.
The number of population variables, in this case, is one for each edge connecting two different partitions, plus those counting the number of nodes in each partition and each node state, due to the presence of the dummy state. In total, we have q(q-1)/2 + q population variables, with q=|𝒮| · |𝒫|. 










In order to count the number of states of the CTMC in this abstraction, we start by observing that  the sum of all variables for a given pair of partitions P', P” is  the number of edges  connecting such partitions in the graph. 
We use ϵ(P',P”) to denote the number of edges between P', P” (resp. the number of edges inside P' if P'=P”). Thus, 













    |𝒴| ≤1.1∏_P',P”∈𝒫^2 
     P' ≤ P”ϵ(P',P”)+𝒮^2 -1𝒮^2-1·1.1∏_P ∈𝒫|P|+||-1||-1 .

This is an over-approximation, because not all combinations are consistent with the graph topology. For example, a high number of infected nodes in a partition might not be consistent with a small number of --edges inside the partition. Note that also this upper bound is exponential in  || and |𝒫| but still polynomial in the number of nodes N, differently from the original network model, whose state space is exponential in N. 


The exponential dependency on the  number of species (i.e., dimensions of the population vector) makes the explicit construction of the lumped state space viable only for very small networks with a small number of node states. However, this is typically the case for spreading models like   or . Yet, also the number of partitions has to be kept small, particularly in realistic models. We expect that the partitioning is especially useful for networks showing a small number of large-scale homogeneous structures, as happens in  many real-world networks <cit.>.









An alternative strategy for analysis is to derive mean-field <cit.> or moment closure equations <cit.> for  MPMs, which can be done without explicitly constructing the lumped (and the original) state space. These are sets of ordinary differential equation (ODE) describing the evolution of (moments of) the population variables.  We refer the reader to <cit.> for a similar approach regarding the node-based abstraction. 















§ NUMERICAL RESULTS























In this section, we compare the numerical solution of the original model—referred to as baseline model—with different lumped MPMs.
The goal of this comparison is to provide evidence supporting the claim that the lumping preserves the dynamics of the original system, with an accuracy increasing with the resolution of the MPM.  
We will perform the comparison by solving numerically the ground and the lumped system, thus comparing the the probability of each state in each point in time.
In practical applications of our method, exact transient or steady state solutions may not be feasible, but in this case we can still rely to approximation methods for MPM <cit.>. Determining which of those techniques performs best in this context is a direction of future exploration. 




A limit of the comparison based on numerical solution of the CTMC is that the state space of the original model has  |𝒮|^|𝒩| states,  which limits the size of the contact network strongly[Code is available at <github.com/gerritgr/Reducing-Spreading-Processes>].

Let P(X(t)=x) denote the probability that the baseline CTMC occupies network state x∈𝒳 at time t≥ 0. 
Furthermore, let P(Y(t)=y) for t≥ 0 and y ∈𝒴 denote the same probability for a lumped MPM (corresponding to a specific partitioning and counting abstraction). To measure their difference, we first approximate the probability distribution of the original model using the lumped solution, invoking the lumping assumption which states that all network states which are lumped together have the same probability mass. We use P_L to denote the lifted probability distribution over the original state space given a lumped solution. Formally,

    P_L (Y(t)=x)=P(Y(t)=y)/|ℒ^-1(y)|where y is s.t. L(x)=y.


We measure the difference between the baseline and a lumped solution at a specific time point by summing up the difference in probability mass of each state, then take the maximum error in time:

    d(P,P_L) = max_t  ∑_x ∈𝒳|P_L (Y(t)=x)-P(X(t)=x ) |  .




In our experiments, we used a small toy network with 13 nodes and 2 states (2^13 = 8192 network states). 
We generated a synthetic contact network following the Erdős–Rényi graph model with a connection probability of 0.5. We use a  model with an infection rate of λ=1.0 and a recovery rate of μ=1.3. Initially, we assign an equal amount of probability mass to all network states.

Fig. <ref> shows the relationship between the error of the lumped MPM, the type of counting abstraction and the method used for node partitioning. We also report the mean difference together with the maximal difference over time.





From our results, we conclude that the edge-based counting abstraction yields a significantly better trade-off between state space size and accuracy. However, it generates larger MPM models than the node-based abstraction when adding a new partition.


We also find that spectral and degree-based partitioning yield similar results for the same number of CTMC states and that random partitioning performed noticeably worse, for both edge-based and node-based counting abstractions. 









§ CONCLUSIONS AND FUTURE WORK

This work developed first steps in a unification of the analysis of stochastic spreading processes on networks and Markov population models. 
Since the so obtained MPM can become very large in terms of species, it is important to be able to control the trade-off between state space size and accuracy.

However, there are still many open research problems ahead. 
Most evidently, it remains to be determined which of the many techniques developed for the analysis of MPMs (e.g. linear noise, moment closure) work best on our proposed epidemic-type MPMs and how they scale with increasing size of the contact network. 
We expect also that these reduction methods can provide a  good starting point for deriving advanced mean-field equations, similar to ones in <cit.>.
Moreover, literature is very rich in proposed moment-closure-based approximation techniques for MPMs, which can now be utilized <cit.>.
We also plan to investigate the relationship between lumped mean-field equations <cit.> and coarse-grained counting abstractions further. 

Future work can additionally explore counting abstraction of different types, for instance, a neighborhood-based abstraction like the one proposed by James P. Gleeson in <cit.>.


Finally, we expect that there are many more possibilities of partitioning the contact network that remain to be investigated and which might have a significant impact on the final accuracy of the abstraction. 



  §.§.§ Acknowledgements

This research has been partially funded by the German Research Council (DFG)
as part of the  Collaborative Research Center
Methods and Tools for Understanding and Controlling Privacy.
We thank Verena Wolf for helpful discussions and provision of expertise. 

abbrv











§ APPENDIX

tocsectionAppendix



§ DIRECT CONSTRUCTION OF MPMS

Here, we prosper a way of directly deriving the lumped MPMs from the contact network without building the original CTMC first. We start with the node-based counting abstraction.



 §.§ Node-Based Abstraction with General Rate Functions

Our general strategy is to iterate over the nodes in the contact network and to compute the mean rate attributed to that node over all x∈𝒳. Therefore, we consider the possible states of each node together with all possible species neighborhoods. The probability of a node n being in state s and having species neighborhood 𝐯 is denoted as (X(n)=s,V(n)=).

For a specific rule r=s_1  s_2 and partition P, we can then describe α_r,P as:

    α_r,P(𝐲) = 
    n ∈ P.∈_n  f(_)  (X(n)=s_1,V(n)=)  ,

where _ is the neighborhood vector induced by , which we receive by grouping all partitions together. 
Note that it is not computationally necessary to actually iterate over all nodes in the partition. Instead we can group all nodes with the same partition neighborhood together, that is, all nodes n',n”∈ P with V_n' = V_n” as the probability only depends on .

Computing the probability is the interesting part, we start by establishing that 

    (X(n)=s_1,V(n)=) 
    
       =     (X(n)=s_1 ) · (V(n)=| X(n)=s_1 )   .

The first term in the product can be described by simply dividing the number of s_1-nodes in P with the total number of nodes in P.

    (X(n)=s_1 ) = 𝐲[s_1, P]/|P|where: n ∈ P  .

The latter probability can be computed for each partition independently. This is because we know the number of nodes in each state in each partition. 




We also know that in partition P the current node n is already in state s_1, which we have to take into account. First, we define 𝐲_P ∈ℤ_≥ 0^|𝒮| to the the projection from y to P. Thus, each entry is defined by:

    𝐲_P[s] = 𝐲[s,P]  .

Likewise, we define 𝐯_P ∈ℤ_≥ 0^|𝒮|, such that 
𝐯_P[s] = 𝐯[s,P]. We also define V(n)_P ∈ℤ_≥ 0^|𝒮| to be the number of neighbors of node n in partition P for each state.
Finally, we define 𝐲_P^s_1^- to be the same vector as 𝐲_P except that the entry corresponding to state s_1 is subtracted by one (and truncated at zero). 
We can now rewrite the probability as:

    (V(n)=| X(n)=s_1 ) 
    
      =   ∏_P' ∈𝒫(V(n)_P'=𝐯_P'| X(n)=s_1 )  
    
       =   (V(n)_P=𝐯_P| X(n)=s_1 )
       ∏_P' ∈𝒫∖{P }(V(n)_P'=𝐯_P'| X(n)=s_1 )  
    
     =    p_h (𝐯_P ; 𝐲_P^s_1^-)  
     ·∏_P' ∈𝒫∖{P } p_h (𝐯_P' ; 𝐲_P')  .


We use p_h(𝐤 ; 𝐊) to denote the probability mass function of the the multivariate hypergeometric distribution, where 𝐤, 𝐊 denote to vectors over non-negative integers of the same length. That is, if 𝐊 denotes the number of nodes in each state in a partition (resp., the number of marbles in an urn with different colors), then, p_h(𝐤 ; 𝐊) denotes the probability of drawing exactly 𝐤[s] nodes (resp. marbles) of each state (resp. color).



 §.§ Reaction Networks and Linear Models

A special case of MPMs are biochemical reaction networks, where the species represent different types of molecules. The change vectors and corresponding propensity functions can elegantly be expressed as monomolecular (→) and bimolecular (+→+) reaction rules (,,,∈𝒵). 



  §.§.§ Reduction to Biochemical Reaction Networks

Most classical models in computational epidemiology are solely comprised of node-based rules (like the curing rule) and edge-based rules (like the infecting propagation rule). We call these linear models.
Node-based rules, also referred to as spontaneous or independent rules, have a constant rate function, i.e., f()=μ. Edge-based rules, also referred to as contact rules, are linear in exactly one dimension, i.e., they have the form f()=λ[s]. 

Linear models are special because not the whole neighborhood is important for the rate of a rule but only the expected number of neighbors in a certain state. This makes the rule very similar to monomolecular and bimolecular reaction rates in MPMs. In fact, we can model the whole dynamics as a set of reaction over the species 𝒵.

Chemical reaction networks are a special case of Markov population models.
In a chemical reaction network the state space is given by population vectors over species and molecular reactions have the form  or ++, where  denote species and a,b ∈ℝ_≥ 0 are reaction rate constants.


For each node-based rule s_1  s_2, we construct the reactions

    (s_1,P)  (s_2,P) ∀ P ∈𝒫

For each edge-based rule s_1  s_1, f()=λ[s'], we construct the reactions

    (s_1,P) + (s',P')   (s_2,P) + (s',P') ∀ P,P' ∈𝒫


where w_P,P' denotes the mean number of edges of a random node in P with nodes in P', that is[Note that, despite the duple notation, we only count edges once]:

    w_P,P' = 
    ϵ(P,P)/|P|1/|P|-1    if P=P'
    ϵ(P,P')/|P|1/|P'|    otherwise
     .

with

    ϵ(P,P') = | {(n_1,n_2) ∈ℰ| n_1 ∈ P, n_2 ∈ P' } |  .




 §.§ Edge-Based Counting Abstraction

For each rule r = s_1  s_2, and each partition P ∈𝒫, and each 𝐯∈𝒱_P, we define a propensity function α_r,P, with:

    α_r,P,𝐯(𝐲) = 
    n ∈ P  f(_)  (X(n)=s_1,V(n)=)  .

Again, we use 

    (X(n)=s_1,V(n)=)
       =  (X(n)=s_1 ) · (V(n)=| X(n)=s_1 )

to compute this probability, where we can solve (X(n)=s_1 ) exactly as before. 

Since we have now information about the edges, we can derive the probability of neighborhoods more precisely. In fact, we can directly construct the set of candidate neighbors from 𝐲. Therefore, we define a vector 𝐲_s,P,P'∈ℤ_≥ 0^|𝒮|, where entry 𝐲_s,P,P'[s'] specifies the number of neighbors of a random node in state s and partition P, which lie in partition P' and occupy state s'.
Formally:





    𝐲_s,P,P'[s'] =
        𝐲[s,P,s',P']     if (s,P) ≤ (s',P')
    𝐲[s',P',s,P]            otherwise
         .
















This gives rise to the final approximation of the probability of neighborhood species: 

    (V(n)=|  X(n)=s_1 ) ≈∏_P' ∈𝒫 p_h (_P ; 𝐲_s_1,P,P')      (where  n ∈ P.)













§ MEAN-FIELD EQUATIONS ((REMOVE))

Typically, the most interesting global property of the network dynamics is the number of nodes in each given state in each partition. Our goal is now to develop an efficient approximation of the element-wise mean of y (and z). Therefore, we propose a system of ordinary differential equations (ODEs), one ODE for each entry in  y (and z) which can be solved without considering the whole Markov model.
We start with the node-based abstraction



 §.§ Node-Based Counting Abstraction

For a given distribution over states Y ∈𝒴, denoted by (𝒴(t)=Y), we can define the element-wise mean of y at time t as:

    ỹ_t(s,P) = Y ∈𝒴(𝒴(t)=Y ) y(s,P)  .

Our goal is now to define a system of ODEs which approximate the evolution of ỹ. 
Assuming the probability distribution over network states is known at each point in time, we can write the time derivative of ỹ as:

    ∂/∂ tỹ_t(s,P) = Y,Y' ∈𝒴^2( y'(s,P)-y(s,P) )(𝒴(t)=Y ) t(Y,Y')   .

We have two problems here, firstly, we do not know (𝒴(t)=Y ) instead, we need to assume a reasonable distribution which is consistent with the current mean ỹ and secondly, we do not want to iterate over the whole CTMC state space. 

Like before, we consider each node, partition neighborhood, and rule individually:

    ∂/∂ tỹ_t(s,P) = s_1  s_2n ∈ P∈𝒱_n(in(s,s_1  s_2, n, ) -  out(s,s_1  s_2, n, ) )

with

    in(s,s_1  s_2, n, ) =   1_s_2 = s· 
     f(_)· (X(n)=s_2,V(n)=)  
      ·y̅_t(s_2,P) 
    out(s,s_1  s_2, n, ) =   1_s_1 = s· 
     f(_)· (X(n) =s,V(n)=) ·y̅_t(s_1,P)    .

We know still nothing about the probability (X(n)=s_2,V(n)=) except that it admits the mean y̅. However, we can assume that ỹ_t(s,P) corresponds to the (unnormalized) probability that a random node n ∈ P is in state s, the natural choice is a partition-wise multinomial distribution:

We start by defining 𝐩(y̅,P) ∈ℝ_≥ 0^|𝒮| for a given ỹ and partition P, such that 𝐩(y̅,P)[s] identifies the probability that a random node in P is in state s. That is, 

    𝐩(y̅,P)[s] = ỹ(s,P)/s' ∈𝒮ỹ_t(s',P) .


The neighborhood and state probability are then given by:

    (X(n)=s,V(n)=)   
    
        =     (X(n)=s) ·( V(n)=)  
    
        =   𝐩(ỹ,P_n)[s] ·∏_P ∈𝒫 f ([P] ; 𝐩(ỹ,P) )

where f(𝐱;𝐩) denotes the probability mass function of the multinomial distribution and P_n is the partition such that n ∈ P_n. Note that [P] and 𝐩(ỹ,P) both are vectors of length |𝒮|, 𝐩(ỹ,P) containing the probabilities and [P] identifies how often each element is drawn form the distribution.


Note that we can simplify the computation by not iterating over each node n but by grouping nodes together which are in the same partition and have the same number of neighbors in each partition. The inflow and outflow corresponding to these nodes will be the same. 




 §.§ Edge-Based Counting Abstraction

In the edge-based abstraction, each lumped network state is a tuple (z,y). 
Similarly to before, we use z̃ to denote the element-wise mean of z. Moreover, we define for a given z̃ and partition P the vector 𝐩(z̃,s,P,P') ∈ℝ_≥ 0^|𝒮| such that
𝐩(z̃,s,P,P')[s']
identifies the probability that a random neighbor n' of a node n is in state s'—given that n is in state s, n ∈ P, and n' ∈ P'.
To formally define 𝐩(z̃,P) we need to remember to count edges that have the same state and the same partition at both ends twice.

    𝐩(z̃,s,P,P')[s']  = z̃^*(s,P,s',P')/s_1,s_2 ∈𝒮^2z̃^*(s,P,s',P') ,

with 

    z̃^*(s,P,s',P') = 
        
       2 z̃(s,P,s',P')      if s=s',P=P'
    z̃(s,P,s',P')            otherwise
         .


The evolution of ỹ has the same form as before, but the computation of the neighborhood probabilities take the edges into account.

    (X(n)=s,V(n)=)  
    
        =   𝐩(ỹ,P_n)[s]  ·∏_P ∈𝒫 f ([P] ; 𝐩(z̃,s,P_n,P))  .


We define the evolution of z̃ as:

    ∂/∂ tz̃_t(s,P,s',P') 
     =   s_1  s_2n ∈ P∈𝒱_n(in(s,s',s_1  s_2, n, ) -  out(s,s',s_1  s_2, n, ) )  ,

where the inflow and outflow depend on the partition neighborhood:

    in(s,s',s_1  s_2, n, ) 
      
    =   1_s_2 = s·[s',P'] · (X(n) =s,V(n)=) ·z̃_t(s,P,s',P') · f(_)
    
       out(s,s',s_1  s_2, n, ) 
      
    =   1_s_1 = s·[s',P'] · (X(n) =s,V(n)=) ·z̃_t(s,P,s',P') · f(_)  .

Note that (X(n)=s,V(n)=) can be computed as before.









 §.§ Node-Based Abstraction

We assume an arbitrary enumeration over the set ℛ×𝒫.
For each rule and for each partition (i.e., for the i-th rule and partition), we define a propensity function α_i: 𝒴→ℝ_≥ 0 and a change function b_i: 𝒮×𝒫→ℤ.


    α(y) = x ∈ℒ^-1(y)n ∈𝒫1/ℒ^-1(y) f(_x,n) 1_x(n)=s_1 ,

where _x,n denotes the neighborhood vector of n in network state x.
The corresponding change function is defined by

    b(s,P) = 
    
    1     if s=s_2,n ∈ P
    
    -1            if s=s_1,n ∈ P
    
    0           otherwise
     .


Moreover, we define 

    q(y,y') = 
    α_i(y)     if ∃ i: y' =  y+b_i
    
    0           otherwise
     .

Note that if there is a fitting i, it is unique. 
Again, the interesting part is the direct construction of α.

    α(y) = 
    n ∈ P.∈_n  f(_)  (X(n)=s_1,V(n)=)  ,


with:

    (X(n)=s_1,V(n)=) 
    
       =     (X(n)=s_1 ) · (V(n)=| X(n)=s_1 )  
    
       =    y(s_1, P_n)/|P_n|·∏_P ∈𝒫(V(n)[P]=[P] | X(n)=s_1 ) 
    
       =    y(s_1, P_n)/|P_n|· p_h ([P_n] ; y^s_1^-(P_n) )  
     ·∏_P ∈𝒫∖{P_n } p_h ([P_n] ; y(P_n) )  .

where we use p_h(𝐤 ; 𝐊) to denote the probability mass function of the the multivariate hyper-geometric distribution, where 𝐤, 𝐊 denote to vectors over non-negative integers of the same length. That is, if 𝐊 denotes the number of nodes in each state in a partition (resp., the number of marbles in an urn with different colors), then, p_h(𝐤 ; 𝐊) denotes the probability of drawing exactly 𝐤[s] nodes (marbles) of each state (color).

Note that for partition P_n we already know that one of the s_1-counts is already assigned to n. Therefore, we define y^s_1^-(P) to be the same vector as y^s_1^-(P) except that the entry corresponding to state s_1 is subtracted by one (and truncated at zero). 
















§ DIRECT CONSTRUCTION OF LUMPED MARKOV MODELS (REMOVE)

Approximating the solution of an 𝚂𝙸𝚂-type process on a contact network by lumping the CTMC first, already reduces the computational costs by many orders of magnitude. However, this scheme is still only applicable when it is possible to construct the full CTMC in the first place. Recall that the number of network states is exponential in the number of nodes of the contact network, rendering the explicit construction of the original state space unfeasible for most realistic contact networks. 

However, on recent years, substantial effort was dedicated to the analysis of very small networks <cit.>. One reason is that when the size of a network increases the (macro-scale) dynamics becomes more deterministic because stochastic effects tend to cancel out. For small contact networks, however, methods which capture the full stochastic dynamics of the system, and not only the mean behavior, are of particular importance.

In this section, we want to discuss the limitations and possibilities in directly deriving the lumped CTMC from the contact network to extend the scope of our method to larger contact networks.



 §.§ General Scheme

We specify the lumped Markov model by specifying the transition rates t(Y,Y').
First, we rewrite the transition rates as:

    t(Y,Y') 
    
      =    s_1  s_2n ∈𝒩X ∈ℒ^-1(Y)
       f(_n) 
       1_X(n)=s_1 ∧ℒ(X')=Y'1/|ℒ^-1(Y)| .

Here, _n denotes the neighborhood vector of n and X' denotes the successor network state of X when the rule s_1  s_2 is applied at n.
Eq. (<ref>) considers each rule, node, and network state individually. We use an indicator function 1_X(n)=s_1 ∧ℒ(X')=Y' which sets those rates to zero which do not correspond to the currently considered successor state Y', we also need to make sure that node n is in state s_1, otherwise the rule would not be applicable. 


To have a better formalism to talk about successor states, we define them first.


  §.§.§ Successor Function

For a given lumped state Y, rule s_1  s_2 and node n, and partition neighborhood , we define the successor state of Y as S(Y,s_1  s_2,n,). That is the lumped network that is reached when the rule is applied to n in any of the X ∈ℒ^-1(Y), where X(n)=s_1 and V(n)=. Note that Y' is uniquely defined in the node-based and edge-based abstraction.
In the neighborhood-based abstracting S maps to a set lumped states. However, for now, we only consider the first two abstractions. 

In the node-based counting abstraction, we have that 

    S(y,s_1  s_2,n,) = y_succ
    with:       y_succ(s,P) = 
        
        y(s,P)+1     if s=s_2,n ∈ P
    
        y(s,P)-1            if s=s_1,n ∈ P
    
         y(s,P)            otherwise
         .

Note that the immediate neighborhood  is irrelevant here.
In the edge-based counting abstraction, we have that 

    S ((z,y),s_1  s_2,n,) = (z_succ,y_succ) 
    with:       z_succ(s,P,s',P') = 
        
        z(s,P,s',P')+[s',P']     if s=s_2,n ∈ P
    
         z(s,P,s',P')-[s',P']     if s=s_1,n ∈ P
    
         z(s,P,s',P')            otherwise

and y being defined as before.


TODO: do this for neighborhood abstraction



  §.§.§ Lumped Transition Rate

Our goal is not to avoid the costly iteration over all X ∈ℒ^-1(Y). Instead, we consider each node in the contact network individually and derive a probability distribution over all possible partition neighborhoods ∈. Therefore, we evaluate the rate function at each node for all neighborhoods, and weight it with the respective probability of each neighborhood.
We can now approximate the transition rate between two lumped states as follows:

    t(Y,Y') 
    ≈   s_1  s_2n ∈𝒩∈_n 
       f(_) 
        (X(n)=s_1,V(n)=)
       1_Y' =  S(Y,s_1  s_2,n,) .

Here, 1_Y' =  S(Y,s_1  s_2,n,) is simply an indicator function which is zero when Y' is not the successor state corresponding to the rule and node currently under consideration. It is also zero when  is not a possible neighborhood of n.

The rate f(_) is averaged over all possible assignments of states to the neighbors of n.
The probability (X(n)=s_1,V(n)=) corresponds to the likelihood that the neighboring nodes are in specific states and that node n is currently in state s_1 (otherwise the rule would not be applicable).

The specifics on how to define (X(n)=s_1,V(n)=) depends on the counting abstraction. Different counting abstractions reveal different information about the current network state which causes different assignments of neighboring nodes to be more or less likely. 
For the ease of presentation, we split
We can write this probability this to

    (X(n)=s_1,V(n)=) 
    
       =     (X(n)=s_1 ) · (V(n)=| X(n)=s_1 )   .





 §.§ Node-Based Counting

In the node-based abstraction the information we have in the current network state is y(s,P), i.e., the number of nodes in each state and each partition. 
Again, we use y(P) ∈ℤ_≥ 0^|𝒮| to denote the number of nodes for each state in a specific partition P. 

Computing the probability that the current node n is in state s_1 is simple, as we know the partition of n and the fraction of s_1-nodes in that partition:

    (X(n)=s_1 ) = y(s_1, P_n)/|P_n|  where  P_n  is s.t.  n ∈ P_n  .

Similarly, we can compute the probability of a partition neighborhood. Note that they are independent between partitions. For instance, the probability of having 2 infected neighbors in partition P_1 is independent from the neighbors in any other neighboring partition.  


    (V(n)=|  X(n)=s_1 ) 
    
     =   ∏_P ∈𝒫(V(n)[P]=[P] | X(n)=s_1 )    .


Here, the probability mass function follows a hyper-geometric distribution, in the general case (|𝒮|>2) a multivariate hyper-geometric distribution. 
We use p_h(𝐤 ; 𝐊) to denote the probability mass function of the the multivariate hyper-geometric distribution, where 𝐤, 𝐊 denote to vectors over non-negative integers of the same length. That is, if 𝐊 denotes the number of nodes in each state in a partition (resp., the number of marbles in an urn with different colors), then, p_h(𝐤 ; 𝐊) denotes the probability of drawing exactly 𝐤[s] nodes (marbles) of each state (color).

Note that for partition P_n we already know that one of the s_1-counts is already assigned to n. Therefore, we define y^s_1^-(P) to be the same vector as y^s_1^-(P) except that the entry corresponding to state s_1 is subtracted by one (and truncated at zero). 
We conclude that:


    (V(n)=|  X(n)=s_1 ) 
    
     =   ∏_P ∈𝒫(V(n)[P]=[P] | X(n)=s_1 )    
     
     =    p_h ([P_n] ; y^s_1^-(P_n) )  
     ·∏_P ∈𝒫∖{P_n } p_h ([P_n] ; y(P_n) )  .





 §.§ Edge-Based Counting

In the edge-based counting abstraction, the lumped network state is a tuple (z,y).
We can use y to compute (X(n)=s_1 ) exactly as before. 
Since we now have information about the edges, we can derive the probability of neighborhoods more precisely. 

Therefor, we define the vector 𝐳^*(s,P,P') ∈ℤ_≥ 0^|𝒮| such that 

    𝐳^*(s,P,P')[s'] = 
        
          2 z(s,P,s',P')      if s=s',P=P'
    
         z(s,P,s',P')            otherwise

and then 

    (V(n)=|  X(n)=s_1 ) = ∏_P ∈𝒫 p_h ([P_n] ; 𝐳^*(s_1,P_n,P) )




 §.§ Neighborhood-Based Counting

In the neighborhood-based abstraction the difficulty arises from the ambiguity of successor states. Recall that S(Y,s_1  s_2,n,) is now a set of possible successor states. We therefore rewrite 

    t(Y,Y') 
    ≈   s_1  s_2n ∈𝒩∈_n
       f(_) 
        (X(n)=s_1,V(n)=)
       w_Y' =  S(Y,s_1  s_2,n,) ,

where the weigh w distributes the outflow of Y uniformly over all successor states.
Formally, we define 

    w_Y' =  S(Y,s_1  s_2,n,)  =
    1/| S(Y,s_1  s_2,n,) |    if Y' ∈ S(Y,s_1  s_2,n,)
    
      0            otherwise


Computing the probability of a node having a particular neighborhood is easy, as this is exactly the information we store in the lumped states:

    (V(n)= ,  X(n)=s_1 ) 
     = y(s_1, P_n, )/s' ∈𝒮' ∈𝒱_ny(s', P_n, ')   }




    
