Generalized network dismantling

Network disruption via continuous batch removal: The case of Sicilian Mafia

Network disruption is pivotal in understanding the robustness and vulnerability of complex networks, which is instrumental in devising strategies for infrastructure protection, epidemic control, cybersecurity, and combating crime. In this paper, with a particular focus on disrupting criminal networks, we proposed to impose a within-the-largest-connected-component constraint in a continuous batch removal disruption process. Through a series of experiments on a recently released Sicilian Mafia network, we revealed that the constraint would enhance degree-based methods while weakening betweenness-based approaches. Moreover, based on the findings from the experiments using various disruption strategies, we propose a structurally-filtered greedy disruption strategy that integrates the effectiveness of greedy-like methods with the efficiency of structural-metric-based approaches. The proposed strategy significantly outperforms the longstanding state-of-the-art method of betweenness centrality while maintaining the same time complexity.

Solving the non-submodular network collapse problems via Decision Transformer

Given a graph G, the network collapse problem (NCP) selects a vertex subset S of minimum cardinality from G such that the difference in the values of a given measure function f(G)-f(G∖S) is greater than a predefined collapse threshold. Many graph analytic applications can be formulated as NCPs with different measure functions, which often pose a significant challenge due to their NP-hard nature. As a result, traditional greedy algorithms, which select the vertex with the highest reward at each step, may not effectively find the optimal solution. In addition, existing learning-based algorithms do not have the ability to model the sequence of actions taken during the decision-making process, making it difficult to capture the combinatorial effect of selected vertices on the final solution. This limits the performance of learning-based approaches in non-submodular NCPs. To address these limitations, we propose a unified framework called DT-NC, which adapts the Decision Transformer to the Network Collapse problems. DT-NC takes into account the historical actions taken during the decision-making process and effectively captures the combinatorial effect of selected vertices. The ability of DT-NC to model the dependency among selected vertices allows it to address the difficulties caused by the non-submodular property of measure functions in some NCPs effectively. Through extensive experiments on various NCPs and graphs of different sizes, we demonstrate that DT-NC outperforms the state-of-the-art methods and exhibits excellent transferability and generalizability.

Energy Formulation for Infinite Structures: Order Parameter for Percolation, Critical Bonds, and Power-Law Scaling of Contact-Based Transport

Investigating heterogeneous materials' microstructure, often simulated using periodic images, is crucial for understanding their physical traits. We propose a generic spring-based representation for periodic two-component structures. The equilibrium energy in this framework serves as an order parameter, offering an analytical expression for wrapping and introducing the concept of critical bonds. We show that these minimum bonds for depercolation can be efficiently detected. The number of critical bonds scales with system size, accurately capturing contact-based transport's scaling. This approach holds potential to analyze functional robustness of networks.

Exploring the landscape of dismantling strategies based on the community structure of networks

Network dismantling is a relevant research area in network science, gathering attention both from a theoretical and an operational point of view. Here, we propose a general framework for dismantling that prioritizes the removal of nodes that bridge together different network communities. The strategies we detect are not unique, as they depend on the specific realization of the community detection algorithm considered. However, when applying the methodology to some synthetic benchmark and real-world networks we find that the dismantling performances are strongly robust, and do not depend on the specific algorithm. Thus, the stochasticity inherently present in many community detection algorithms allows to identify several strategies that have comparable effectiveness but require the removal of distinct subsets of nodes. This feature is highly relevant in operational contexts in which the removal of nodes is costly and allows to identify the least expensive strategy that still holds high effectiveness.

Spectral Clustering With Adaptive Neighbors for Deep Learning

Spectral clustering is a well-known clustering algorithm for unsupervised learning, and its improved algorithms have been successfully adapted for many real-world applications. However, traditional spectral clustering algorithms are still facing many challenges to the task of unsupervised learning for large-scale datasets because of the complexity and cost of affinity matrix construction and the eigen-decomposition of the Laplacian matrix. From this perspective, we are looking forward to finding a more efficient and effective way by adaptive neighbor assignments for affinity matrix construction to address the above limitation of spectral clustering. It tries to learn an affinity matrix from the view of global data distribution. Meanwhile, we propose a deep learning framework with fully connected layers to learn a mapping function for the purpose of replacing the traditional eigen-decomposition of the Laplacian matrix. Extensive experimental results have illustrated the competitiveness of the proposed algorithm. It is significantly superior to the existing clustering algorithms in the experiments of both toy datasets and real-world datasets.

Vital node identification in hypergraphs via gravity model

Hypergraphs that can depict interactions beyond pairwise edges have emerged as an appropriate representation for modeling polyadic relations in complex systems. With the recent surge of interest in researching hypergraphs, the centrality problem has attracted much attention due to the challenge of how to utilize higher-order structure for the definition of centrality metrics. In this paper, we propose a new centrality method (HGC) on the basis of the gravity model as well as a semi-local HGC, which can achieve a balance between accuracy and computational complexity. Meanwhile, two comprehensive evaluation metrics, i.e., a complex contagion model in hypergraphs, which mimics the group influence during the spreading process and network s-efficiency based on the higher-order distance between nodes, are first proposed to evaluate the effectiveness of our methods. The results show that our methods can filter out nodes that have fast spreading ability and are vital in terms of hypergraph connectivity.

Forecasting the evolution of fast-changing transportation networks using machine learning

Transportation networks play a critical role in human mobility and the exchange of goods, but they are also the primary vehicles for the worldwide spread of infections, and account for a significant fraction of CO₂ emissions. We investigate the edge removal dynamics of two mature but fast-changing transportation networks: the Brazilian domestic bus transportation network and the U.S. domestic air transportation network. We use machine learning approaches to predict edge removal on a monthly time scale and find that models trained on data for a given month predict edge removals for the same month with high accuracy. For the air transportation network, we also find that models trained for a given month are still accurate for other months even in the presence of external shocks. We take advantage of this approach to forecast the impact of a hypothetical dramatic reduction in the scale of the U.S. air transportation network as a result of policies to reduce CO₂ emissions. Our forecasting approach could be helpful in building scenarios for planning future infrastructure.

Transportation networks undergo permanent changes influenced by a variety of human-induced and natural factors. The authors propose here a machine learning framework for prediction of connections removal that could be useful in building scenarios for transportation infrastructure needs.

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.

Strategizing COVID-19 lockdowns using mobility patterns

During the COVID-19 pandemic, governments have attempted to control infections within their territories by implementing border controls and lockdowns. While large-scale quarantine has been the most successful short-term policy, the enormous costs exerted by lockdowns over long periods are unsustainable. As such, developing more flexible policies that limit transmission without requiring large-scale quarantine is an urgent priority. Here, the dynamics of dismantled community mobility structures within US society during the COVID-19 outbreak are analysed by applying the Louvain method with modularity optimization to weekly datasets of mobile device locations. Our networks are built based on individuals' movements from February to May 2020. In a multi-scale community detection process using the locations of confirmed cases, natural break points from mobility patterns as well as high risk areas for contagion are identified at three scales. Deviations from administrative boundaries were observed in detected communities, indicating that policies informed by assumptions of disease containment within administrative boundaries do not account for high risk patterns of movement across and through these boundaries. We have designed a multi-level quarantine process that takes these deviations into account based on the heterogeneity in mobility patterns. For communities with high numbers of confirmed cases, contact tracing and associated quarantine policies informed by underlying dismantled community mobility structures is of increasing importance.

Machine learning dismantling and early-warning signals of disintegration in complex systems

From physics to engineering, biology and social science, natural and artificial systems are characterized by interconnected topologies whose features - e.g., heterogeneous connectivity, mesoscale organization, hierarchy - affect their robustness to external perturbations, such as targeted attacks to their units. Identifying the minimal set of units to attack to disintegrate a complex network, i.e. network dismantling, is a computationally challenging (NP-hard) problem which is usually attacked with heuristics. Here, we show that a machine trained to dismantle relatively small systems is able to identify higher-order topological patterns, allowing to disintegrate large-scale social, infrastructural and technological networks more efficiently than human-based heuristics. Remarkably, the machine assesses the probability that next attacks will disintegrate the system, providing a quantitative method to quantify systemic risk and detect early-warning signals of system's collapse. This demonstrates that machine-assisted analysis can be effectively used for policy and decision-making to better quantify the fragility of complex systems and their response to shocks.

Long-loop feedback vertex set and dismantling on bipartite factor graphs

Network dismantling aims at breaking a network into disconnected components and attacking vertices that intersect with many loops has proven to be a most efficient strategy. Yet existing loop-focusing methods do not distinguish the short loops within densely connected local clusters (e.g., cliques) from the long loops connecting different clusters, leading to lowered performance of these algorithms. Here we propose a new solution framework for network dismantling based on a two-scale bipartite factor-graph representation, in which long loops are maintained while local dense clusters are simplistically represented as individual factor nodes. A mean-field spin-glass theory is developed for the corresponding long-loop feedback vertex set problem. The framework allows for the advancement of various existing dismantling algorithms; we developed the new version of two benchmark algorithms BPD (which uses the message-passing equations of the spin-glass theory as the solver) and CoreHD (which is fastest among well-performing algorithms). New solvers outperform current state-of-the-art algorithms by a considerable margin on networks of various sorts. Further improvement in dismantling performance is achievable by opting flexibly the choice of local clusters.

Robustness of Air Transportation as Complex Networks:Systematic Review of 15 Years of Research and Outlook into the Future

Air transportation systems are an important part of the critical infrastructure in our connected world. Accordingly, a better understanding and improvements in the resilience of the overall air transportation system are essential to the well-functioning of our society and overall sustainability of human beings. In the literature, network science is increasingly used to better understand the resilience dynamics of air transportation. Given the wide application of tools for network science and the importance of designing resilient air transportation systems, a rich body of studies has emerged in recent years. This review paper synthesizes the related literature that has been published throughout the last 15 years regarding the robustness of air transportation systems. The contributions of this work consist of two major elements. The first part provides a comprehensive discussion and cross-comparison of the reported results. We cover several major topics, including node importance identification, failure versus attack profiles, recovery and improvement techniques, and networks of networks approaches. The second part of this paper complements the review of aggregated findings by elaborating on a future agenda for robust air transportation research. Our survey-style overview hopefully contributes toward a better understanding of the state of the art in this research area, and, in turn, to the improvement of future air transportation resilience and sustainability.

Disintegrating spatial networks based on region centrality

Finding an optimal strategy at a minimum cost to efficiently disintegrate a harmful network into isolated components is an important and interesting problem, with applications in particular to anti-terrorism measures and epidemic control. This paper focuses on optimal disintegration strategies for spatial networks, aiming to find an appropriate set of nodes or links whose removal would result in maximal network fragmentation. We refer to the sum of the degree of nodes and the number of links in a specific region as region centrality. This metric provides a comprehensive account of both topological properties and geographic structure. Numerical experiments on both synthetic and real-world networks demonstrate that the strategy is significantly superior to conventional methods in terms of both effectiveness and efficiency. Moreover, our strategy tends to cover those nodes close to the average degree of the network rather than concentrating on nodes with higher centrality.

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.

Revisiting the power of reinsertion for optimal targets of network attack

Understanding and improving the robustness of networks has significant applications in various areas, such as bioinformatics, transportation, critical infrastructures, and social networks. Recently, there has been a large amount of work on network dismantling, which focuses on removing an optimal set of nodes to break the network into small components with sub-extensive sizes. However, in our experiments, we found these state-of-the-art methods, although seemingly different, utilize the same refinement technique, namely reinsertion, to improve the performance. Despite being mentioned with understatement, the technique essentially plays the key role in the final performance. Without reinsertion, the current best method would deteriorate worse than the simplest heuristic ones; while with reinsertion, even the random removal strategy achieves on par with the best results. As a consequence, we, for the first time, systematically revisit the power of reinsertion in network dismantling problems. We re-implemented and compared 10 heuristic and approximate competing methods on both synthetic networks generated by four classical network models, and 18 real-world networks which cover seven different domains with varying scales. The comprehensive ablation results show that: i) HBA (High Betweenness Adaption, no reinsertion) is the most effective network dismantling strategy, however, it can only be applicable in small scale networks; ii) HDA (High Degree Adaption, with reinsertion) achieves the best balance between effectiveness and efficiency; iii) The reinsertion techniques help improve the performance for most current methods; iv) The one, which adds back the node based on that it joins the clusters minimizing the multiply of both numbers and sizes, is the most effective reinsertion strategy for most methods. Our results can be a survey reference to help further understand the current methods and thereafter design the better ones.

Mitigation of cascading failures in complex networks

Cascading failures in many systems such as infrastructures or financial networks can lead to catastrophic system collapse. We develop here an intuitive, powerful and simple-to-implement approach for mitigation of cascading failures on complex networks based on local network structure. We offer an algorithm to select critical nodes, the protection of which ensures better survival of the network. We demonstrate the strength of our approach compared to various standard mitigation techniques. We show the efficacy of our method on various network structures and failure mechanisms, and finally demonstrate its merit on an example of a real network of financial holdings.

Geographical fragmentation of the global network of Twitter communications

Understanding the geography of society represents a challenge for social and economic sciences. The recent availability of data from social media enables the observation of societies at a global scale. In this paper, we study the geographical structure of the Twitter communication network at the global scale. We find a complex structure where self-organized patches with clear cultural, historical, and administrative boundaries are manifested and first-world economies centralize information flows. These patches unveil world regions that are socially closer to each other with direct implications for processes of collective learning and identity creation.

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.

Statistical analysis of edges and bredges in configuration model networks

A bredge (bridge-edge) in a network is an edge whose deletion would split the network component on which it resides into two separate components. Bredges are vulnerable links that play an important role in network collapse processes, which may result from node or link failures, attacks, or epidemics. Therefore, the abundance and properties of bredges affect the resilience of the network to these collapse scenarios. We present analytical results for the statistical properties of bredges in configuration model networks. Using a generating function approach based on the cavity method, we calculate the probability P[over ̂](e∈B) that a random edge e in a configuration model network with degree distribution P(k) is a bredge (B). We also calculate the joint degree distribution P[over ̂](k,k^{'}|B) of the end-nodes i and i^{'} of a random bredge. We examine the distinct properties of bredges on the giant component (GC) and on the finite tree components (FC) of the network. On the finite components all the edges are bredges and there are no degree-degree correlations. We calculate the probability P[over ̂](e∈B|GC) that a random edge on the giant component is a bredge. We also calculate the joint degree distribution P[over ̂](k,k^{'}|B,GC) of the end-nodes of bredges and the joint degree distribution P[over ̂](k,k^{'}|NB,GC) of the end-nodes of nonbredge edges on the giant component. Surprisingly, it is found that the degrees k and k^{'} of the end-nodes of bredges are correlated, while the degrees of the end-nodes of nonbredge edges are uncorrelated. We thus conclude that all the degree-degree correlations on the giant component are concentrated on the bredges. We calculate the covariance Γ(B,GC) of the joint degree distribution of end-nodes of bredges and show it is negative, namely bredges tend to connect high degree nodes to low degree nodes. We apply this analysis to ensembles of configuration model networks with degree distributions that follow a Poisson distribution (Erdős-Rényi networks), an exponential distribution and a power-law distribution (scale-free networks). The implications of these results are discussed in the context of common attack scenarios and network dismantling processes.

Power-law distribution of degree-degree distance: A better representation of the scale-free property of complex networks

Whether real-world complex networks are scale free or not has long been controversial. Recently, in Broido and Clauset [A. D. Broido, A. Clauset, Nat. Commun. 10, 1017 (2019)], it was claimed that the degree distributions of real-world networks are rarely power law under statistical tests. Here, we attempt to address this issue by defining a fundamental property possessed by each link, the degree-degree distance, the distribution of which also shows signs of being power law by our empirical study. Surprisingly, although full-range statistical tests show that degree distributions are not often power law in real-world networks, we find that in more than half of the cases the degree-degree distance distributions can still be described by power laws. To explain these findings, we introduce a bidirectional preferential selection model where the link configuration is a randomly weighted, two-way selection process. The model does not always produce solid power-law distributions but predicts that the degree-degree distance distribution exhibits stronger power-law behavior than the degree distribution of a finite-size network, especially when the network is dense. We test the strength of our model and its predictive power by examining how real-world networks evolve into an overly dense stage and how the corresponding distributions change. We propose that being scale free is a property of a complex network that should be determined by its underlying mechanism (e.g., preferential attachment) rather than by apparent distribution statistics of finite size. We thus conclude that the degree-degree distance distribution better represents the scale-free property of a complex network.

Finding key players in complex networks through deep reinforcement learning

Finding an optimal set of nodes, called key players, whose activation (or removal) would maximally enhance (or degrade) certain network functionality, is a fundamental class of problems in network science^1,2. Potential applications include network immunization³, epidemic control⁴, drug design⁵, and viral marketing⁶. Due to their general NP-hard nature, those problems typically cannot be solved by exact algorithms with polynomial time complexity⁷. Many approximate and heuristic strategies have been proposed to deal with specific application scenarios^1,2,8-12. Yet, we still lack a unified framework to efficiently solve this class of problems. Here we introduce a deep reinforcement learning framework FINDER, which can be trained purely on small synthetic networks generated by toy models and then applied to a wide spectrum of influencer finding problems. Extensive experiments under various problem settings demonstrate that FINDER significantly outperforms existing methods in terms of solution quality. Moreover, it is several orders of magnitude faster than existing methods for large networks. The presented framework opens up a new direction of using deep learning techniques to understand the organizing principle of complex networks, which enables us to design more robust networks against both attacks and failures.

Influencer identification in dynamical complex systems

The integrity and functionality of many real-world complex systems hinge on a small set of pivotal nodes, or influencers. In different contexts, these influencers are defined as either structurally important nodes that maintain the connectivity of networks, or dynamically crucial units that can disproportionately impact certain dynamical processes. In practice, identification of the optimal set of influencers in a given system has profound implications in a variety of disciplines. In this review, we survey recent advances in the study of influencer identification developed from different perspectives, and present state-of-the-art solutions designed for different objectives. In particular, we first discuss the problem of finding the minimal number of nodes whose removal would breakdown the network (i.e. the optimal percolation or network dismantle problem), and then survey methods to locate the essential nodes that are capable of shaping global dynamics with either continuous (e.g. independent cascading models) or discontinuous phase transitions (e.g. threshold models). We conclude the review with a summary and an outlook.

Optimal Disintegration Strategy in Multiplex Networks under Layer Node-Based Attack

From social networks to complex infrastructures, many systems could be described by multiplex networks formed by a set of nodes connected via more than one type of links. Network disintegration, which is the problem of identifying a set of nodes or edges whose removal would maximize the network collapse, is significant for dismantling harmful networks. In this article, we consider the optimal disintegration strategy problem in multiplex networks and extend the attack mode to the layer node-based attack. An optimization model is proposed to search the optimal strategy of a multiplex network under layer node-based attack with fix attack length. Two types of strategies based on the information of multiplex nodes and layer nodes, respectively, are also given for comparison. Through experiments in both model networks and real networks, we found that the approximate optimal strategies could be identified by solving the model. The properties of the optimal strategies are also summarized.

Evolutionary dynamics of organised crime and terrorist networks

Crime is pervasive into modern societies, although with different levels of diffusion across regions. Its dynamics are dependent on various socio-economic factors that make the overall picture particularly complex. While several theories have been proposed to account for the establishment of criminal behaviour, from a modelling perspective organised crime and terrorist networks received much less attention. In particular, the dynamics of recruitment into such organisations deserve specific considerations, as recruitment is the mechanism that makes crime and terror proliferate. We propose a framework able to model such processes in both organised crime and terrorist networks from an evolutionary game theoretical perspective. By means of a stylised model, we are able to study a variety of different circumstances and factors influencing the growth or decline of criminal organisations and terrorist networks, and observe the convoluted interplay between agents that decide to get associated to illicit groups, criminals that prefer to act on their own, and the rest of the civil society.

A comparative analysis of approaches to network-dismantling

Estimating, understanding, and improving the robustness of networks has many application areas such as bioinformatics, transportation, or computational linguistics. Accordingly, with the rise of network science for modeling complex systems, many methods for robustness estimation and network dismantling have been developed and applied to real-world problems. The state-of-the-art in this field is quite fuzzy, as results are published in various domain-specific venues and using different datasets. In this study, we report, to the best of our knowledge, on the analysis of the largest benchmark regarding network dismantling. We reimplemented and compared 13 competitors on 12 types of random networks, including ER, BA, and WS, with different network generation parameters. We find that network metrics, proposed more than 20 years ago, are often non-dominating competitors, while many recently proposed techniques perform well only on specific network types. Besides the solution quality, we also investigate the execution time. Moreover, we analyze the similarity of competitors, as induced by their node rankings. We compare and validate our results on real-world networks. Our study is aimed to be a reference for selecting a network dismantling method for a given network, considering accuracy requirements and run time constraints.