Scaling of percolation transitions on Erdös-Rényi networks under centrality-based attacks

A statistical analysis method for probability distributions in Erdös-Rényi random networks with preferential cutting-rewiring operation

The study of specific physiological processes from the perspective of network physiology has gained recent attention. Modeling the global information integration among the separated functionalized modules in structural and functional brain networks is a central problem. In this article, the preferentially cutting-rewiring operation (PCRO) is introduced to approximatively describe the above physiological process, which consists of the cutting procedure and the rewiring procedure with specific preferential constraints. By applying the PCRO on the classical Erdös-Rényi random network (ERRN), three types of isolated nodes are generated, based on which the common leaves (CLs) are formed between the two hubs. This makes the initially homogeneous ERRN experience drastic changes and become heterogeneous. Importantly, a statistical analysis method is proposed to theoretically analyze the statistical properties of an ERRN with a PCRO. Specifically, the probability distributions of these three types of isolated nodes are derived, based on which the probability distribution of the CLs can be obtained easily. Furthermore, the validity and universality of our statistical analysis method have been confirmed in numerical experiments. Our contributions may shed light on a new perspective in the interdisciplinary field of complexity science and biological science and would be of great and general interest to network physiology.

Shortest-Path Percolation on Random Networks

We propose a bond-percolation model intended to describe the consumption, and eventual exhaustion, of resources in transport networks. Edges forming minimum-length paths connecting demanded origin-destination nodes are removed if below a certain budget. As pairs of nodes are demanded and edges are removed, the macroscopic connected component of the graph disappears, i.e., the graph undergoes a percolation transition. Here, we study such a shortest-path-percolation transition in homogeneous random graphs where pairs of demanded origin-destination nodes are randomly generated, and fully characterize it by means of finite-size scaling analysis. If budget is finite, the transition is identical to the one of ordinary percolation, where a single giant cluster shrinks as edges are removed from the graph; for infinite budget, the transition becomes more abrupt than the one of ordinary percolation, being characterized by the sudden fragmentation of the giant connected component into a multitude of clusters of similar size.

Anti-modularization for both high robustness and efficiency including the optimal case

Although robustness of connectivity and modular structures in networks have been attracted much attentions in complex networks, most researches have focused on those two features in Erdos-Renyi random graphs and Scale-Free networks whose degree distributions follow Poisson and power-law, respectively. This paper investigates the effect of modularity on robustness in a modular d-regular graphs. Our results reveal that high modularity reduces the robustness even from the optimal robustness of a random d-regular graph in the pure effect of degree distributions. Moreover, we find that a low modular d-regular graph exhibits small-world property that average path length is O(logN). These results indicate that low modularity on modular structures leads to coexistence of both high robustness and efficiency of paths.

Universal dynamics of mitochondrial networks: a finite-size scaling analysis

Evidence from models and experiments suggests that the networked structure observed in mitochondria emerges at the critical point of a phase transition controlled by fission and fusion rates. If mitochondria are poised at criticality, the relevant network quantities should scale with the system's size. However, whether or not the expected finite-size effects take place has not been demonstrated yet. Here, we first provide a theoretical framework to interpret the scaling behavior of mitochondrial network quantities by analyzing two conceptually different models of mitochondrial dynamics. Then, we perform a finite-size scaling analysis of real mitochondrial networks extracted from microscopy images and obtain scaling exponents comparable with critical exponents from models and theory. Overall, we provide a universal description of the structural phase transition in mammalian mitochondria.

Neural extraction of multiscale essential structure for network dismantling

Diverse real world systems can be abstracted as complex networks consisting of nodes and edges as functional components. Percolation theory has shown that the failure of a few of nodes could lead to the collapse of a whole network, which brings up the network dismantling problem: How to select the least number of nodes to decompose a network into disconnected components each smaller than a predefined threshold? For its NP-hardness, many heuristic approaches have been proposed to measure and rank each node according to its importance to network structural stability. However, these measures are from a uniscale viewpoint by regarding one complex network as a flatted topology. In this article, we argue that nodes' structural importance can be measured in different scales of network topologies. Built upon recent deep learning techniques, we propose a self-supervised learning based network dismantling framework (NEES), which can hierarchically merge some compact substructures to convert a network into a coarser one with fewer nodes and edges. During the merging process, we design neural models to extract essential structures and utilize self-attention mechanisms to learn nodes' importance hierarchy in each scale. Experiments on real world networks and synthetic model networks show that the proposed NEES outperforms the state-of-the-art schemes in most cases in terms of removing the least number of target nodes to dismantle a network. The dismantling effectiveness of our neural extraction framework also highlights the emerging role of multi-scale essential structures.

Percolation on feature-enriched interconnected systems

Percolation is an emblematic model to assess the robustness of interconnected systems when some of their components are corrupted. It is usually investigated in simple scenarios, such as the removal of the system's units in random order, or sequentially ordered by specific topological descriptors. However, in the vast majority of empirical applications, it is required to dismantle the network following more sophisticated protocols, for instance, by combining topological properties and non-topological node metadata. We propose a novel mathematical framework to fill this gap: networks are enriched with features and their nodes are removed according to the importance in the feature space. We consider features of different nature, from ones related to the network construction to ones related to dynamical processes such as epidemic spreading. Our framework not only provides a natural generalization of percolation but, more importantly, offers an accurate way to test the robustness of networks in realistic scenarios.

Percolation of attack with tunable limited knowledge

Percolation models shed a light on network integrity and functionality and have numerous applications in network theory. This paper studies a targeted percolation (α model) with incomplete knowledge where the highest degree node in a randomly selected set of n nodes is removed at each step, and the model features a tunable probability that the removed node is instead a random one. A "mirror image" process (β model) in which the target is the lowest degree node is also investigated. We analytically calculate the giant component size, the critical occupation probability, and the scaling law for the percolation threshold with respect to the knowledge level n under both models. We also derive self-consistency equations to analyze the k-core organization including the size of the k core and its corona in the context of attacks under tunable limited knowledge. These percolation models are characterized by some interesting critical phenomena and reveal profound quantitative structure discrepancies between Erdős-Rényi networks and power-law networks.

Critical behaviors of high-degree adaptive and collective-influence percolation

How the giant component of a network disappears under attacking nodes or links addresses a key aspect of network robustness, which can be framed into percolation problems. Various strategies to select the node to be deactivated have been studied in the literature, for instance, a simple random failure or high-degree adaptive (HDA) percolation. Recently, a new attack strategy based on a quantity called collective-influence (CI) has been proposed from the perspective of optimal percolation. By successively deactivating the node having the largest CI-centrality value, it was shown to be able to dismantle a network more quickly and abruptly than many of the existing methods. In this paper, we focus on the critical behaviors of the percolation processes following degree-based attack and CI-based attack on random networks. Through extensive Monte Carlo simulations assisted by numerical solutions, we estimate various critical exponents of the HDA percolation and those of the CI percolations. Our results show that these attack-type percolation processes, despite displaying apparently more abrupt collapse, nevertheless exhibit standard mean-field critical behaviors at the percolation transition point. We further discover an extensive degeneracy in top-centrality nodes in both processes, which may provide a hint for understanding the observed results.