# Percolation and Internet Science
## 2 Percolation and Related Models
We introduce also a set of observables \(A(\mathbf{s})\), for instance the \"density\" or \"magnetization\" \(m(\mathbf{s})=(1/N)\sum_{i}s_{i}\). The time average of an observable is  
\[\overline{A}=\frac{1}{T}\sum_{t=t_{0}}^{t_{0}+T}A(\mathbf{s}(t)),\]  
where \(t_{0}\) denotes the transient interval. In principle, this quantity depends on the initial configuration and on the random field. In practice, in many cases, after a long enough transient \(t_{0}\) (which depends on the system size \(N\)) and for a long enough average time \(T\), the average values does not depend on \(t_{0}\), \(T\) or the field. In such cases, the system is said to be \"self-averaging\". This is not the case, for instance, for spin-glasses, introduced below. Averaging over the \"disorder\" \(\mathbf{r}(t)\), one can define a probability distribution \(P(\mathbf{s},t)\), whose time evolution is  
\[P(\mathbf{s},t+1)=\sum_{\mathbf{s}^{\prime}}M(\mathbf{s}|\mathbf{s}^{\prime})P(\mathbf{s},t), \tag{4}\]  
where \(M\) defines a Markov chain, and is given by  
\[M(\mathbf{s}^{\prime}|\mathbf{s})=\prod_{i}\tau(s^{\prime}_{i}|\mathcal{N}_{i}(\mathbf{s} );p). \tag{5}\]  
Notice that \(P(\mathbf{s},t)\) depends in principle on the initial distribution \(P(\mathbf{s},0)\), which can be a delta function centered on some configuration \(\mathbf{s}_{0}\). The ensemble average value of an observable can be computed over the probability distribution  
\[\langle A\rangle=\sum_{\mathbf{s}}A(\mathbf{s})P(\mathbf{s}).\]  
For self-averaging systems, \(\overline{A}\) coincides with \(\langle A\rangle\). If the asymptotic probability distribution for any given initial state coincide, the system is said to be ergodic. In a phase transition, one has the breaking of ergodicity, so that the probability distribution depends on the initial state of the system. For the standard percolation and infection problems, one assumes that the spreading process occurs independently on each link and/or on each node. We can generalize the problem by formulating it as a cellular automaton model [42; 43], in which the function \(f\) of Equation (2) can be arbitrary. In this way, we can \"include\" into the same formulation many other interesting problems. One of the first generalizations is that of \"diluting\" the application of any rule, i.e., replacing Equation (2) with  
\[s_{i}(t)=[q<r]f\left(\mathcal{N}_{i}(t-1)\right)+(1-[q<r])s_{i}(t-1).\]  
or, equivalently  
\[\tau(s|\mathcal{N})= \begin{cases}f\left(\mathcal{N}_{i}(t-1)\right)&\text{ with probability }q\\ s&\text{otherwise}\end{cases} \]  
The previous equation implies that, on average, only a fraction \(q\) of nodes are updated, while the others keep their values. In the limit \(q\to 0\), one or none of nodes are updated, and therefore one gets time-continuous dynamics. Another extension is that of getting the transition probabilities from the Monte Carlo realization of an equilibrium model, i.e., from an Hamiltonian (energy) term. Let us illustrate this concept using the famous Ising model [44; 45]. In this model, each node is associated to a spin \(\sigma_{i}=-1,1\) and the energy of a configuration \(\sigma\) is given by  
\[\mathcal{H}(\sigma)=-\sum_{i}J\sigma_{i}h_{i},\]  
where \(J\) denotes the coupling and \(h_{i}\) is the local magnetic field, due to neighbors  
\[h_{i}=\sum_{\sigma_{j}\in\mathcal{N}_{i}(\sigma)}\sigma_{j}=\sum_{j}a_{ij} \sigma_{j}. \tag{6}\]  
The maximum entropy condition gives the equilibrium (asymptotic) distribution  
\[P(\sigma)=\frac{1}{\mathcal{Z}}\exp\left(-\frac{\mathcal{H}(\sigma)}{T}\right),\]  
where \(T\) is the temperature in energy units and \(\mathcal{Z}\) is the normalization constant (partition function). The actual control parameter is the ratio \(J/T\). The idea is that, for strong coupling \(J\) or low temperature \(T\), the probability is peaked over configurations with many aligned spins (if \(J>0\), counter-aligned of \(J<0\)) and average magnetization \(|m|>0\), while on the contrary the distribution is almost flat and \(m\simeq 0\).