Efficient algorithm to compute mutually connected components in interdependent networks

Mutually connected components (MCCs) play an important role as a measure of resilience in the study of interdependent networks. Despite their importance, an efficient algorithm to obtain the statistics of all MCCs during the removal of links has thus far been absent. Here, using a well-known fully dynamic graph algorithm, we propose an efficient algorithm to accomplish this task. We show that the time complexity of this algorithm is approximately $O\left(N^{1.2}\right)$ for random graphs, which is more efficient than $O\left(N^2\right)$ of the brute-force algorithm. We confirm the correctness of our algorithm by comparing the behavior of the order parameter as links are removed with existing results for three types of double-layer multiplex networks. We anticipate that this algorithm will be used for simulations of large-size systems that have been previously inaccessible.

Figure 1

(a) Initial configurations of A-layer (upper) and B-layer (lower) networks. (b) First, each connected component is maintained in a spanning tree form. Link D-F (gray line) in the A layer is treated as a redundant link. Second, ad hoc links (dashed lines) B-D in the A layer and A-B in the B layer are added between two nodes through random selection from each component to connect the networks. Then there is only one MCC and all links including the ad hoc links are active (thick lines). (c) An ad hoc link B-D is deleted in the A layer. This deletion splits the A network into two components. Subsequently, link A-E in the B layer becomes inactive (thin line) and we identify two MCCs {A,B,C} and {D,E,F}. (d) The other ad hoc link A-B in the B layer is deleted. Subsequently, link A-B in the A layer becomes inactive (thin line) and the component {A,B,C} is split into two components {A,C} and {B}. At this stage, there are no remaining ad hoc links and the MCCs (represented by different node symbols) of the networks in (a) have been retained with identification of active and inactive links. (e) Now we delete links in the original networks one by one in the same manner. Here we show two examples of link deletion that do not cause a cascade of inactivations: (i) link E-D deletion in the A layer and (ii) link A-E deletion in the B layer. For case (i) the redundant link D-F is recovered and maintains the spanning tree. For case (ii), because the link is inactive, nothing occurs.

Figure 2

Plot of $P_{\infty }$ (the size of a giant MCC divided by $N$) vs the mean degree $k=2L/N$, where $L$ is the number of remaining links in the system. The system size $N={10}^6$ and an initial mean degree $k_0=4$ are taken. As links are removed randomly one by one from each layer, $P_{\infty }$ exhibits various discontinuous or continuous transitions depending on the underlying networks.

Figure 3

(a) Plot of $s$ (the number of MCCs divided by the system size $N$) vs the mean degree $k$ under the same conditions as those in Fig. 2. Here $s$ exhibits behavior similar to $m$ but in an upside-down manner for complex networks. (b) However, $s$ exhibits a behavior somewhat different from $m$ for the two-dimensional lattices.

Figure 4

Plot of total computing time $T$ vs system size $N$ for different underlying network structures. Each point is obtained by taking an average over ten samples. The solid and dashed line are guidelines with slopes of $1.2$ and $1.3$, respectively.

Figure 5

(a) The tree we want to represent. (b) Euler tour sequence from node C of the tree. (c) Sequence stored in a balanced tree. The number next to each node of (c) is the size of the subtree from the node.