# Percolation and Internet Science
## 2 Percolation and Related Models  
Let us consider a network composed by \(N\) nodes \(i=1,\ldots,N\). The links between nodes are defined by means of an adjacency matrix \(a_{ij}\), \(i,j=1,\ldots,N\), and \(a_{ij}=1\) if there is a link from node \(j\) to node \(i\) and zero otherwise. The network needs not to be symmetric, and a node is generally connected to itself. One can also define multiple connection networks among the same nodes (multigraph) with different adjacency matrices \(a_{ij}^{(1)}\), \(a_{ij}^{(2)}\),....  
We denote by \(k_{i}=\sum_{j}a_{ij}\) the input connectivity of node \(i\). The state of the node \(i\) at time \(t\) is denoted \(s_{i}(t)\). It takes a value in a discrete set \(s_{i}(t)\in\{0,1,\ldots,q-1\}\), generally Boolean, \(q=2\). We also denote by  
\[\mathcal{N}_{i}(\boldsymbol{s}(t))=\big{\{}s_{j}(t)\big{\}}_{a_{ij}=1} \tag{1}\]  
the configuration at time \(t\) of input nodes for node \(i\), i.e., its _neighborhood_. The state of the node \(s_{i}(t)\) depends on the previous states of input nodes, and on some random number \(r_{i}(t)\)  
\[s_{i}(t)=f\left(\mathcal{N}_{i}(t-1);r_{i}(t)\right). \tag{2}\]  
For instance, the simple site percolation problem is defined by  
\[s_{i}(t)=s_{i}(t-1)\vee[p<r_{i}]\left[\sum_{j}a_{ij}s_{j}(t-1)>0\right], \tag{3}\]  
where \(\vee\) is the logical OR; \([\cdot]\) is the truth function that takes value \(1\) if \(\cdot\) is true and zero otherwise; \(s_{i}=0\) denotes a healthy/dry node; and \(s_{i}=1\) denotes an infected/wet one. The logic of the previous equation is that an infected node stays infected, while a healthy one can become infected with probability \(p\) if at least one of the connected nodes is infected. Notice that the random numbers do not change in time, thus, for a given value of \(p\) and a given starting configuration (say one infected node), the clusters of infected nodes grows for some time and then freezes. In the following, we neglect to indicate the time/space dependence of the random numbers \(r_{i}(t)\), and the fact that the function \(f\) of Equation (2) may depend on them. Actually, the standard percolation problems [10] do not include the \"time\" dimension, which is instead included in the \"directed\" formulation [41]. As noted, it is however possible to unify the two definitions: if the random numbers are renewed at each time step, it is a directed percolation problem, while, in the contrary case, it is a static percolation one. Let us denote by \(\mathbf{s}(t)=\{s_{i}(t)\}\) the state of the whole configuration at time \(t\), which evolves following a stochastic or deterministic rule. In the case of a stochastic evolution, one needs a certain amount of random numbers \(r(t)=\{r_{i}(t)\}\), uniformly distributed in the interval \([0,1)\). These numbers can also not depend on \(t\), as in the case of standard percolation. They can be seen as a property of the space-time lattice, i.e., a \"quenched\" random field. In general, the time evolution of \(\mathbf{s}\) depends on a certain number of _control_ parameters that we denote with \(p\), as in Equation (3). These control parameters define the local transition probabilities \(\tau(s^{\prime}_{i}|\mathcal{N}_{i}(\mathbf{s});p)\), where \(\mathcal{N}_{i}\) is the state of the neighborhood of site \(i\), Equation (1), and \(s^{\prime}_{i}\) denotes the new state of that site. Clearly, \(\sum_{s^{\prime}}\tau(s^{\prime}_{i}|\mathcal{N}_{i}(\mathbf{s});p)=1\). We restrict our exposition to the Boolean case \(s_{i}\in\{0,1\}\). In this case, the evolution of the system is given by the parallel application of a local rule  
\[s_{i}(t+1)=[r_{i}<\tau(1|\mathcal{N}_{i}(\mathbf{s}(t));p)].\]  
Given the random field \(r_{i}(t)\), the dynamics is deterministic, but the final state depends on the field itself. If all quantities \(\tau\) take the value of either zero or one, the evolution of the system is deterministic and does not depend on the field \(r_{i}(t)\).