18.4: Mean-Field Approximation of Discrete-State Networks

Last updated
Save as PDF

Page ID: 7881

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

Analyzing the dynamics of discrete-state network models requires a different approach, because the assumption of smooth, continuous state space, on which the linear stability analysis is based on, no longer applies. This difference is similar to the difference between continuous field models and cellular automata (CA). In Section 12.3, we analyzed CA models using mean-field approximation. Since CA are just a special case of discretestate dynamical networks, we should be able to apply the same analysis to dynamical networks as well.

In fact, mean-field approximation works on dynamical networks almost in the same way as on CA. But one important issue we need to consider is how to deal with heterogeneous sizes of the neighborhoods. In CA, every cell has the same number of neighbors, so the mean-field approximation is very easy. But this is no longer the case on networks in which nodes can have any number of neighbors. There are a few different ways to deal with this issue.

In what follows, we will work on a simple binary-state example, the Susceptible-Infected Susceptible (SIS) model, which we discussed in Section 16.2. As you may remember, the state transition rules of this model are fairly simple: A susceptible node can get infected by an infected neighbor node with infection probability \(p_i\) (per infected neighbor), while an infected node can recover to a susceptible node with recovery probability \(p_r\). In the previous chapter, we used asynchronous updating in simulations of the SIS model, but here we assume synchronous, simultaneous updating, in order to make the mean-field approximation more similar to the approximation we applied to CA.

For the mean-field approximation, we need to represent the state of the system by a macroscopic variable, i.e., the probability (= density, fraction) of the infected nodes in the network (say, \(q\)) in this case, and then describe the temporal dynamics of this variable by assuming that this probability applies to everywhere in the network homogeneously (i.e., the “mean field”). In the following sections, we will discuss how to apply the mean field approximation to two different network topologies: random networks and scale-free networks.