We propose an interdependent random geometric graph (RGG) model for interdependent networks. Based on this model, we study the robustness of two interdependent spatially embedded networks where interdependence exists between geographically nearby nodes in the two networks. We study the emergence of the giant mutual component in two interdependent RGGs as node densities increase, and define the percolation threshold as a pair of node densities above which the mutual giant component first appears. In contrast to the case for a single RGG, where the percolation threshold is a unique scalar for a given connection distance, for two interdependent RGGs, multiple pairs of percolation thresholds may exist, given that a smaller node density in one RGG may increase the minimum node density in the other RGG in order for a giant mutual component to exist. We derive analytical upper bounds on the percolation thresholds of two interdependent RGGs by discretization, and obtain 99 confidence intervals for the percolation thresholds by simulation. Based on these results, we derive conditions for the interdependent RGGs to be robust under random failures and geographical attacks.
In the interdependent networks literature, the model which is closest to ours is the interdependent lattice model, first proposed in @cite_4 and further studied in @cite_5 @cite_2 . In the lattice model, nodes in a network are represented by the open sites (nodes) of a square lattice, where every site is open independently with probability @math . Network links are represented by the bonds (edges) between adjacent open sites. Every node in one lattice is interdependent with one randomly chosen node within distance @math in the other lattice. The distance @math indicates the geographical proximity of the interdependence. The percolation threshold of the interdependent lattice model is characterized as a function of @math , assuming the same @math in both lattices @cite_4 . Percolation of the model where some nodes do not need to have supply nodes was studied in @cite_5 . The analysis relies on quantities estimated by simulation and extrapolation, such as the fraction of nodes in the infinite component of a lattice for any fixed @math , which cannot be computed rigorously. In contrast, we study the percolation of the interdependent RGG model using a mathematically rigorous approach.
@cite_5 @cite_4 @cite_2
2106569518 2963328260
We study the cascading failures in a system composed of two interdependent square lattice networks A and B placed on the same Cartesian plane, where each node in network A depends on a node in network B randomly chosen within a certain distance r from the corresponding node in network A and vice versa. Our results suggest that percolation for small r below rmax ! 8 (lattice units) is a second-order transition, and for larger r is a first-order transition. For r < rmax, the critical threshold increases linearly with r from 0.593 at r 1⁄4 0 and reaches a maximum, 0.738 for r 1⁄4 rmax, and then gradually decreases to 0.683 for r 1⁄4 1. Our analytical considerations are in good agreement with simulations. Our study suggests that interdependent infrastructures embedded in Euclidean space become most vulnerable when the distance between interdependent nodes is in the intermediate range, which is much smaller than the size of the system. We consider critical site percolation on the triangular lattice, that is, we choose @math or 1 with probability 1 2 each, independently for all vertices @math of the triangular lattice. We say that a word @math is seen in the percolation configuration if there exists a selfavoiding path @math on the triangular lattice with @math . We prove that with probability 1 "almost all" words, as well as all periodic words, except the two words @math and @math , are seen. "Almost all" words here means almost all with respect to the measure @math under which the @math are i.i.d. with @math (for an arbitrary @math ). A new percolation problem is posed which can exhibit a first-order transition. In bootstrap percolation, sites on an empty lattice are first randomly occupied, and then all occupied sites with less than a given number m of occupied neighbours are successively removed until a stable configuration is reached. On any lattice for sufficiently large m, the ensuing clusters can only be infinite. On a Bethe lattice for m>or=3, the fraction of the lattice occupied by infinite clusters discontinuously jumps from zero at the percolation threshold. From an analysis of stable and metastable ground states of the dilute Blume-Capel model (1966), it is concluded that effects like bootstrap percolation may occur in some real magnets. The planted partition model (also known as the stochastic blockmodel) is a classical cluster-exhibiting random graph model that has been extensively studied in statistics, physics, and computer science. In its simplest form, the planted partition model is a model for random graphs on @math nodes with two equal-sized clusters, with an between-class edge probability of @math and a within-class edge probability of @math . Although most of the literature on this model has focused on the case of increasing degrees (ie. @math as @math ), the sparse case @math is interesting both from a mathematical and an applied point of view. A striking conjecture of Decelle, Krzkala, Moore and Zdeborov 'a based on deep, non-rigorous ideas from statistical physics gave a precise prediction for the algorithmic threshold of clustering in the sparse planted partition model. In particular, if @math and @math , then conjectured that it is possible to cluster in a way correlated with the true partition if @math , and impossible if @math for some sufficiently large @math . We prove half of their prediction, showing that it is indeed impossible to cluster if @math . Following , our work establishes a rigorous connection between the clustering problem, spin-glass models on the Bethe lattice and the so called reconstruction problem. This connection points to fascinating applications and open problems.