# Percolation and Internet Science
## 1 Introduction  
The Internet is naturally linked to the network concept, i.e., a set of nodes connected by links [1; 2; 3; 4]. Clearly, this model is ubiquitous and intensively studied: how a structured network arises and grows, how it can be crossed, cut or made more robust, it can be explored and measured, and how processes are affected by the network structure. However, the Internet should not be seen only at the interconnection level. As pointed out in [5], we can put into evidence at least two aspects related to networks: the physical/infrastructural one, related to protocols and transferring of information, and the social/human one, which uses the infrastructural level to communicate, create and elaborate information (see, for instance, the proceedings of the _Internet Science_ conference for some examples of multi-disciplinary approaches [6; 7; 8; 9]). According to this, Internet science can be considered a research field that investigates the aspect of the communication among actors and resources as processes that can shape the information relay and transformations on the Internet [5]. This field brings together, among others, contributions from networks and complexity sciences. One of the crucial contributions of the network science to Internet investigations is the study of the diffusion or \"flow\" of something on the network itself, which can be broadly associated to theword \"percolation\" [10; 11; 12; 13; 14]. A simple definition of a percolation problem is the one referring to the porosity of some material, and the possibility for a fluid to pass through it, if there is at least a path connecting two opposite sides. However, one does not need to have a pre-defined network. One can examine the problem of joining sites with links, and ask whether the resulting pattern is composed by many isolated sub-networks or if most of nodes belongs to the same cluster. The percolation problem is a cornerstone of statistical mechanics and stochastic processes. In this review, we illustrate some of the ideas coming from the investigations about percolation and cellular automata, which can be of interest for Internet science. A lattice or graph is a set of \(N\) nodes with links between some nodes. The nodes can be visualized as pores and the links as pipes on a substrate or material. All channels are open, but pores may be open with probability \(p\) and closed with probability \(1-p\). One asks if there exists an open path connecting any two sides of the material. Clearly, for \(p=0\), there is no open path, while, for \(p=1\), all paths are open, and therefore there is a critical value \(p_{c}\) marking the transition between the existence or absence of such a path. All results are considered in the limit \(N\to\infty\). Let us define a computational model for such a problem. We assign to each node \(i\) of a lattice a random number \(r_{i}\) uniformly distributed between zero and one. Then, we mark all sites with \(r_{i}<p\). All marked points connected by one link are said to belong to a cluster, and the number \(s\) of connected nodes define the size of such cluster. For each value of \(p\), we have a certain distribution \(P(s)\) of clusters (\(P(s)\) is proportional to the number of clusters of size \(s\) present on the graph). Since the numbers \(r_{i}\) do not change (they are said to form a _quenched_ random field), the clusters can only grow and merge when increasing \(p\). For small \(p\), we have an exponential distribution \(P(s)\) peaked on a small value of \(s\). For large values of \(p\), we have a large cluster (giant component), spanning over almost all the lattice and including almost all the sites in the graph/lattice, with a tail of small clusters. Excluding the giant component, the distribution of clusters is again exponential. The state corresponding to the critical values of \(p\), \(p_{c}\), is characterized by the appearance of the giant component.