The proposed percolation process displays a universal phase transition, characterized by the abrupt and simultaneous disappearance of both the giant connected component and the largest 2-core, across networks with markedly different degree distributions, indicating that the physics of network dismantling is insensitive to a broad range of topological properties.
Abstract
Identifying the smallest set of elements whose removal dismantle a complex network, known as the network dismantling problem, is a fundamental task with many practical applications. Whereas network dismantling has been extensively studied over the past decade, most work has focused on developing efficient algorithms for large but finite networks. By contrast, the physics of the network dismantling process, namely how the network structural connectivity is affected by the removal of nodes or edges, remains largely unexplored in the thermodynamic limit. Here, we shed light on this understudied aspect of network dismantling by introducing an adaptive biased percolation process able to optimally dismantle a network. Through a systematic analysis of synthetic network models, we find that the proposed percolation process displays a universal phase transition, characterized by the abrupt and simultaneous disappearance of both the giant connected component and the largest 2-core, across networks with markedly different degree distributions. Simulations on real networks further support this universality, indicating that the physics of network dismantling is insensitive to a broad range of topological properties. Together, these results suggest that a topology-agnostic theory could be developed to explain the critical behavior of network dismantling.
Strongly connected components (SCCs) characterize modular structure in directed networks but are fragile to single node failures. We study strongly biconnected components (SBCs), which are the set of nodes in which every node pair remains mutually reachable after the removal of any single node, as a more robust notion of connectivity. Using a generating function formalism, we derive the size of the giant SBC and analyze its percolation behavior under random node and link removal. We show that the giant SBC emerges at the same threshold as the giant SCC but grows more slowly due to stricter connectivity requirements. We also applied our theoretical framework to real-world biological networks including gene regulatory networks and neural connectome. Our framework provides insight into the interplay between connectivity, redundancy, and robustness in complex directed systems.
Minsoo Yang, R. Laubenbacher, Byungjoon Min· 0 citations
The results show that smaller clusters are generally more vulnerable to attacks on central nodes, whereas larger and less centralized clusters retain more topological efficiency.
The joint asymptotic distribution of any finite collection of network moments in random graphs sampled from a graphon, which includes both the nondegenerate case as well as the degenerate case, provides the higher-order fluctuation theory for subgraph counts in the graphon model.
Anirban Chatterjee, S. Dan, B. Bhattacharya· Annals of Statistics· 0 citations
Predicting the percolation threshold of highly clustered networks from local statistics remains difficult, because short loops break the independence assumption underlying tree-like message passing. Existing remedies address loopy connectivity either through prescribed local motifs in random-graph ensembles or through a single network's realized topology, leaving an ensemble-level treatment of arbitrary connectivity patterns absent. Here, we develop a loopy message-passing framework for random clustered graph ensembles based on generalized-edge statistics, which characterize overlap patterns among the neighborhoods of different nodes. This yields a progressively refined approximation scheme based on neighborhoods of increasing size around each node. The low-order approximations recover previous equations for random network ensembles, and the new result that yields refined threshold prediction is developed by the second-order approximation. We show that the effectiveness of this framework depends not only on short-cycle density but also on the internal consistency of generalized edges. To diagnose this effectiveness, we introduce the generalized-edge closure coefficient (GECC) to quantify this consistency. Because GECC is computed entirely from local statistics and does not rely on any percolation calculation, it serves as an a priori diagnostic for the reliability of the approximation. Using synthetic and real networks, the threshold is evaluated via the second-order and lower-order approximations. Comparisons with Monte Carlo simulations show that GECC captures key structural features that strongly affect the percolation threshold. These results establish ensemble-based loopy message passing as an efficient route for predicting the percolation threshold in large clustered networks.
In complex network analysis, the identification of influential nodes is a fundamental issue, which is closely related to the structural robustness of the network and the dynamics of propagation processes. Current research primarily focuses on mesoscale features based on the smallest cycles or local features derived from star-shaped structures. However, the role of neighboring nodes that are connected to a given node but do not participate in its smallest cycles remains underexplored in network analysis. To address this issue, this paper proposes a hybrid centrality measure that integrates information from both smallest-cycle structures and non-smallest-cycle structures associated with each target node. The smallest-cycle structures considered in this method are identified only within the imposed local search range and do not necessarily correspond to the true smallest cycles in the full graph. Specifically, the extent of a node’s involvement in mesoscale structures is characterized by the number of the smallest cycles it participates in, while its local structural heterogeneity is represented by the number of neighboring nodes connected to it that do not belong to any smallest cycles. These two aspects are then unified into a single node importance metric through a weighted integration strategy. This paper evaluates node importance from multiple perspectives, including propagation capability analysis based on the SI model, network robustness testing through node attack simulations, and ranking accuracy assessment using Kendall correlation coefficient. The experimental results demonstrate that the proposed method achieves competitive or superior performance compared with the selected baseline methods under the experimental settings considered in this work. The findings indicate that integrating smallest-cycle and non-smallest-cycle features provides a more comprehensive characterization of a node’s role in complex networks. This study offers a novel perspective on the integration of multi-scale structural information in complex networks and presents an effective new approach for the identification of important nodes.
Fu-Rui Tan, Xiao-long Chen, Ruijie Wang et al.· Entropy· 0 citations
This paper empirically evaluates the DAG-ness framework, a four-component measure that quantifies acyclicity, flow alignment, cyclic locality, and pathway complexity across a corpus of 107 networks drawn from twelve structurally diverse domains, and finds that macroscopic acyclicity is pervasive even in feedback-rich systems.
Erik Csikos· arXiv.org· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
