Percolation under noise: Detecting explosive percolation using the second-largest component

We consider the problem of distinguishing between different rates of percolation under noise. A statistical model of percolation is constructed allowing for the birth and death of edges as well as the presence of noise in the observations. This graph-valued stochastic process is composed of a latent and an observed nonstationary process, where the observed graph process is corrupted by type-I and type-II errors. This produces a hidden Markov graph model. We show that for certain choices of parameters controlling the noise, the classical (Erdős-Rényi) percolation is visually indistinguishable from a more rapid form of percolation. In this setting, we compare two different criteria for discriminating between these two percolation models, based on the interquartile range (IQR) of the first component's size, and on the maximal size of the second-largest component. We show through data simulations that this second criterion outperforms the IQR of the first component's size, in terms of discriminatory power. The maximal size of the second component therefore provides a useful statistic for distinguishing between different rates of percolation, under physically motivated conditions for the birth and death of edges, and under noise. The potential application of the proposed criteria for the detection of clinically relevant percolation in the context of applied neuroscience is also discussed.

Figure 1

Proportion of nodes in the largest component as a function of time for a functional network deduced from the electrocorticogram of a single patient with epilepsy during a seizure (see [27] for details). The weighted functional networks have been binarized by conducting independent hypothesis tests on the maximum absolute values of the cross correlations over $0.5\text{-s}$ windows with 50% overlap and after correcting for multiple comparisons. The black trace is a smoothed version of this process. Seizure onset was clinically estimated to occur at the vertical dotted line.

Figure 2

Birth and death steps for the product rule (PR) in the Achlioptas' model of percolation. In this example, edge $e_2$ was born before edge $e_1$, since $|C_{11}\left|\right|C_{12}|>|C_{21}\left|\right|C_{22}|$. Therefore, when $e_1$ and $e_2$ are selected during a death step, $e_2$ is discarded after $e_1$. This death step specification ensures that births and deaths constitute genuine reverse PR operations.

Figure 3

Directed acyclic graph (DAG) representation of the hidden Markov process combining a latent stochastic graph process in the first row denoted by $G_t$, with an observed stochastic graph process contaminated by noise in the second row, denoted by $G_t^{*}$. Directed arrows indicate probabilistic dependence, such that the distribution of the observed $G_t^{*}$ depends on the value taken by the latent graph $G_t$.

Figure 4

Percentage of vertices in the giant connected component (GCC) in the main window, and the corresponding sizes of the second-largest component (SLC) in inset, for a birth rate of $p=1$ and death rate of $q=0$, for the ER (black) and PR (gray) percolation models, for $N_v=100$; in which the $x$ axis denotes the number of steps in the process divided by $N_v$. In bold, these results are reported for a noise-free model, whereas the thin lines represent noisy simulations with type-I and type-II error rates of $\alpha =0.0075, \beta =0$. The details of the algebraic relationship between the type-I and type-II error rates and the graph process is described in Appendix, for the case of the ER model. Observe that the ER and PR models are nearly indistinguishable once a small amount of noise is added to these percolation processes.

Figure 5

Densities of the IQR of the GCC in the main windows, and densities of the maximal size of the SLC in the insets, are reported for networks of sizes 100 and 1000 vertices in panels (a) and (b), respectively, for the ER (black) and PR (gray) percolation models, and based on 1000 realizations from the distributions of these two (noise-free) models, specifying a birth rate of $p=1$ and death rate of $q=0$, in which the $x$ axis denotes the number of steps in the process divided by $N_v$. The IQR criterion has been described in Eq. (2). Note that the difference in scales of the density values of the $y$ axes in these two figures is due to the difference in scales of the $x$ axes, which represent the number of steps scaled by network sizes, $t/N_v$.

Figure 6

Percentage of vertices in the giant connected component (GCC) in the main window, and the corresponding sizes of the second-largest component (SLC) in inset, for a birth rate of $p=1$ and death rate of $q=0$, for the ER (black) and the PR (gray) percolation models, for $N_v=1000$, in which the $x$ axis denotes the number of steps in the process divided by $N_v$. In bold, these results are reported for a noise-free model, whereas the thin lines represent noisy simulations with type-I and type-II error rates of $\alpha =0.0075, \beta =0$. Observe that the ER and PR models are nearly indistinguishable once noise is added to these percolation processes.

Figure 7

Percentage of vertices in giant connected component (GCC), and in second largest component (SLC), in (a) and (b), respectively; with respect to scaled time ($t/N_v$), for $N_v=1000$ in which the $x$ axis denotes the number of steps in the process divided by $N_v$. These results are reported for both the ER and PR models, in black and gray, respectively; and for different choices of the birth rate $p$. Each curve represents the mean of 1000 independent simulations.

Figure 8

Receiver operating characteristic (ROC) curves for tests based on the IQR and SLC statistics for networks of size $N_v=100$ and $N_v=1000$, in (a) and (b), respectively, for different choices of birth rate $p$.

Figure 9

Percentage of vertices in giant connected component (GCC), and in second largest component (SLC), in (a) and (b), respectively, with respect to scaled time ($t/N_v$), for $N_v=1000$; in which the $x$ axis denotes the number of steps in the process divided by $N_v$. These results are reported for both the ER and PR models, in black and gray, respectively, and for different choices of the error rate $\alpha$. Each curve represents the mean of 1000 independent simulations.

Figure 10

Receiver operating characteristic (ROC) curves for tests based on the IQR and SLC statistics for networks of size $N_v=100$ and $N_v=1000$, in (a) and (b), respectively, for different choices of error rate $\alpha$.

Figure 11

Percentage of vertices in giant connected component (GCC), and in second largest component (SLC), in panels (a) and (b), respectively; with respect to scaled time ($t/N_v$), with $N_v=100$; in which the $x$-axis denotes the number of steps in the process divided by $N_v$. These results are reported both the ER and PR models, in black and gray, respectively; for different choices of birth rates, $p$. Each curve represents the mean of 1,000 independent simulations.

Figure 12

Area under the curve (AUC) surface plot for the receiver operating characteristic (ROC) curves of the IQR of the GCC, and of the maximal size of the SLC, for different choices of the error rates $\alpha$ and $\beta$, and with $p=1$ and $q=0$, under the simulation settings of Fig. 13, and with $N_v=100$.

Figure 13

Percentage of vertices in giant connected component (GCC), and in second largest component (SLC), in (a) and (b), respectively, with respect to scaled time ($t/N_v$), for $N_v=100$, in which the $x$ axis denotes the number of steps in the process divided by $N_v$. These results are reported for both the ER and PR models, in black and gray, respectively, and for different choices of the error rate $\alpha$. Each curve represents the mean of 1000 independent simulations.