Optimal resilience of modular interacting networks

Liu Y., Sanhedrai H., Dong G., Shekhtman L.M., Wang F., Buldyrev S.V., Havlin S.

Abstract Targeted immunization of centralized nodes in large-scale networks has attracted significant attention. However, in real-world scenarios, knowledge and observations of the network may be limited, thereby precluding a full assessment of the optimal nodes to immunize (or quarantine) in order to avoid epidemic spreading such as that of the current coronavirus disease (COVID-19) epidemic. Here, we study a novel immunization strategy where only n nodes are observed at a time and the most central among these n nodes is immunized. This process can globally immunize a network. We find that even for small n (≈10) there is significant improvement in the immunization (quarantine), which is very close to the levels of immunization with full knowledge. We develop an analytical framework for our method and determine the critical percolation threshold pc and the size of the giant component P∞ for networks with arbitrary degree distributions P(k). In the limit of n → ∞ we recover prior work on targeted immunization, whereas for n = 1 we recover the known case of random immunization. Between these two extremes, we observe that, as n increases, pc increases quickly towards its optimal value under targeted immunization with complete information. In particular, we find a new general scaling relationship between |pc(∞) − pc(n)| and n as |pc(∞) − pc(n)| ∼ n−1exp(−αn). For scale-free (SF) networks, where P(k) ∼ k−γ, 2 < γ < 3, we find that pc has a transition from zero to nonzero when n increases from n = 1 to O(log N) (where N is the size of the network). Thus, for SF networks, having knowledge of  ≈log N nodes and immunizing the most optimal among them can dramatically reduce epidemic spreading. We also demonstrate our limited knowledge immunization strategy on several real-world networks and confirm that in these real networks, pc increases significantly even for small n.

Mariani M.S., Ren Z., Bascompte J., Tessone C.J.

The observed architecture of ecological and socio-economic networks differs significantly from that of random networks. From a network science standpoint, non-random structural patterns observed in real networks call for an explanation of their emergence and an understanding of their potential systemic consequences. This article focuses on one of these patterns: nestedness. Given a network of interacting nodes, nestedness can be described as the tendency for nodes to interact with subsets of the interaction partners of better-connected nodes. Known since more than $80$ years in biogeography, nestedness has been found in systems as diverse as ecological mutualistic organizations, world trade, inter-organizational relations, among many others. This review article focuses on three main pillars: the existing methodologies to observe nestedness in networks; the main theoretical mechanisms conceived to explain the emergence of nestedness in ecological and socio-economic networks; the implications of a nested topology of interactions for the stability and feasibility of a given interacting system. We survey results from variegated disciplines, including statistical physics, graph theory, ecology, and theoretical economics. Nestedness was found to emerge both in bipartite networks and, more recently, in unipartite ones; this review is the first comprehensive attempt to unify both streams of studies, usually disconnected from each other. We believe that the truly interdisciplinary endeavour -- while rooted in a complex systems perspective -- may inspire new models and algorithms whose realm of application will undoubtedly transcend disciplinary boundaries.

Dong G., Xiao H., Wang F., Du R., Shao S., Tian L., Stanley H.E., Havlin S.

Network systems with clustering have been given much attention due to their wide occurrence in the real world. One focus of these studies has been on robustness of single clustered networks and interdependent clustered networks under random attack (RA) or hub-targeted attack. However, infrastructure networks could suffer from a damage that is localized, i.e. a group of neighboring nodes attacked or fail, a topic that was not studied earlier on clustered networks. In this paper, we analytically and via simulations study the robustness under localized attack (LA) of single Erdős–Rényi clustered network and interdependent clustered network. For generating networks with clustering we use two models: (i) double Poisson distribution (DPD) and (ii) fixed degree distribution (FDD). For the LA case, the DPD model shows a second order phase transition behavior for a single clustered network, while for dependent networks, the system undergoes a change of percolation phase transition from a first order (abrupt transition) to a second order (continuous) transition when the coupling strength q decreases below a critical value qc. Our results imply that single networks become significantly more vulnerable with increasing clustering coefficient c with respect to LA. This is in contrast to RA where the robustness is almost independent of c. We obtain similar results when testing different real networks. For LA on dependent networks, we also observe that the system becomes more vulnerable as c increases. This is again in contrast to RA, where for, q 

Gould D.M.

Dong G., Fan J., Shekhtman L.M., Shai S., Du R., Tian L., Chen X., Stanley H.E., Havlin S.

SignificanceMuch work has focused on phase transitions in complex networks in which the system transitions from a resilient to a failed state. Furthermore, many of these networks have a community structure, whose effects on resilience have not yet been fully understood. Here, we show that the community structure can significantly affect the resilience of the system in that it removes the phase transition present in a single module, and the network remains resilient at this transition. In particular, we show that the effect of increasing interconnections is analogous to increasing external magnetic field in spin systems. Our findings provide insight into the resilience of many modular complex systems and clarify the important effects that community structure has on network resilience.

Liao H., Mariani M.S., Medo M., Zhang Y., Zhou M.

Complex networks have emerged as a simple yet powerful framework to represent and analyze a wide range of complex systems. The problem of ranking the nodes and the edges in complex networks is critical for a broad range of real-world problems because it affects how we access online information and products, how success and talent are evaluated in human activities, and how scarce resources are allocated by companies and policymakers, among others. This calls for a deep understanding of how existing ranking algorithms perform, and which are their possible biases that may impair their effectiveness. Well-established ranking algorithms (such as the popular Google's PageRank) are static in nature and, as a consequence, they exhibit important shortcomings when applied to real networks that rapidly evolve in time. The recent advances in the understanding and modeling of evolving networks have enabled the development of a wide and diverse range of ranking algorithms that take the temporal dimension into account. The aim of this review is to survey the existing ranking algorithms, both static and time-aware, and their applications to evolving networks. We emphasize both the impact of network evolution on well-established static algorithms and the benefits from including the temporal dimension for tasks such as prediction of real network traffic, prediction of future links, and identification of highly-significant nodes.

Shekhtman L.M., Danziger M.M., Havlin S.

Until recently, network science has focused on the properties of single isolated networks that do not interact or depend on other networks. However it has now been recognized that many real-networks, such as power grids, transportation systems, and communication infrastructures interact and depend on other networks. Here, we will present a review of the framework developed in recent years for studying the vulnerability and recovery of networks composed of interdependent networks. In interdependent networks, when nodes in one network fail, they cause dependent nodes in other networks to also fail. This is also the case when some nodes, like for example certain people, play a role in two networks, i.e. in a multiplex. Dependency relations may act recursively and can lead to cascades of failures concluding in sudden fragmentation of the system. We review the analytical solutions for the critical threshold and the giant component of a network of n interdependent networks. The general theory and behavior of interdependent networks has many novel features that are not present in classical network theory. Interdependent networks embedded in space are significantly more vulnerable compared to non-embedded networks. In particular, small localized attacks may lead to cascading failures and catastrophic consequences. Finally, when recovery of components is possible, global spontaneous recovery of the networks and hysteresis phenomena occur. The theory developed for this process points to an optimal repairing strategy for a network of networks. Understanding realistic effects present in networks of networks is required in order to move towards determining system vulnerability.

Goswami B., Shekatkar S.M., Rheinwalt A., Ambika G., Kurths J.

We propose a RAndom Interacting Network (RAIN) model to study the interactions between a pair of complex networks. The model involves two major steps: (i) the selection of a pair of nodes, one from each network, based on intra-network node-based characteristics and (ii) the placement of a link between selected nodes based on the similarity of their relative importance in their respective networks. Node selection is based on a selection fitness function and node linkage is based on a linkage probability defined on the linkage scores of nodes. The model allows us to relate within-network characteristics to between-network structure. We apply the model to the interaction between the USA and Schengen airline transportation networks (ATNs). Our results indicate that two mechanisms: degree-based preferential node selection and degree-assortative link placement are necessary to replicate the observed inter-network degree distributions as well as the observed inter-network assortativity. The RAIN model offers the possibility to test multiple hypotheses regarding the mechanisms underlying network interactions. It can also incorporate complex interaction topologies. Furthermore, the framework of the RAIN model is general and can be potentially adapted to various real-world complex systems.

Shekhtman L.M., Shai S., Havlin S.

Many infrastructure networks have a modular structure and are also interdependent. While significant research has explored the resilience of interdependent networks, there has been no analysis of the effects of modularity. Here we develop a theoretical framework for attacks on interdependent modular networks and support our results by simulations. We focus on the case where each network has the same number of communities and the dependency links are restricted to be between pairs of communities of different networks. This is very realistic for infrastructure across cities. Each city has its own infrastructures and different infrastructures are dependent within the city. However, each infrastructure is connected within and between cities. For example, a power grid will connect many cities as will a communication network, yet a power station and communication tower that are interdependent will likely be in the same city. It has been shown that single networks are very susceptible to the failure of the interconnected nodes (between communities) Shai et al. and that attacks on these nodes are more crippling than attacks based on betweenness da Cunha et al. In our example of cities these nodes have long range links which are more likely to fail. For both treelike and looplike interdependent modular networks we find distinct regimes depending on the number of modules, $m$. (i) In the case where there are fewer modules with strong intraconnections, the system first separates into modules in an abrupt first-order transition and then each module undergoes a second percolation transition. (ii) When there are more modules with many interconnections between them, the system undergoes a single transition. Overall, we find that modular structure can influence the type of transitions observed in interdependent networks and should be considered in attempts to make interdependent networks more resilient.

Shai S., Kenett D.Y., Kenett Y.N., Faust M., Dobson S., Havlin S.

Modularity is a key organizing principle in real-world large-scale complex networks. The relatively sparse interactions between modules are critical to the functionality of the system and are often the first to fail. We model such failures as site percolation targeting interconnected nodes, those connecting between modules. We find, using percolation theory and simulations, that they lead to a "tipping point" between two distinct regimes. In one regime, removal of interconnected nodes fragments the modules internally and causes the system to collapse. In contrast, in the other regime, while only attacking a small fraction of nodes, the modules remain but become disconnected, breaking the entire system. We show that networks with broader degree distribution might be highly vulnerable to such attacks since only few nodes are needed to interconnect the modules, consequently putting the entire system at high risk. Our model has the potential to shed light on many real-world phenomena, and we briefly consider its implications on recent advances in the understanding of several neurocognitive processes and diseases.

Gao J., Liu X., Li D., Havlin S.

Li M., Wang B.

Complex network is a useful tool in describing the interactions between different agents of a complex system, and has attracted considerable interest recently. There are various approaches to studying the structure and dynamic of complex networks for the diverse and complicated connectivity structure. One more applicable theoretical approach is the generating function technique, which is useful for the studies of network structure and dynamic, especially for tree-like networks. In this paper, we will give a summary of the basic ideas of this approach, and explore the structure of networks. A cascading failures model we have proposed before will also be presented as an application of this approach.

Boccaletti S., Bianconi G., Criado R., del Genio C.I., Gómez-Gardeñes J., Romance M., Sendiña-Nadal I., Wang Z., Zanin M.

In the past years, network theory has successfully characterized the interaction among the constituents of a variety of complex systems, ranging from biological to technological, and social systems. However, up until recently, attention was almost exclusively given to networks in which all components were treated on equivalent footing, while neglecting all the extra information about the temporal- or context-related properties of the interactions under study. Only in the last years, taking advantage of the enhanced resolution in real data sets, network scientists have directed their interest to the multiplex character of real-world systems, and explicitly considered the time-varying and multilayer nature of networks. We offer here a comprehensive review on both structural and dynamical organization of graphs made of diverse relationships (layers) between its constituents, and cover several relevant issues, from a full redefinition of the basic structural measures, to understanding how the multilayer nature of the network affects processes and dynamics.

Nematzadeh A., Ferrara E., Flammini A., Ahn Y.

We investigate the impact of community structure on information diffusion with the linear threshold model. Our results demonstrate that modular structure may have counter-intuitive effects on information diffusion when social reinforcement is present. We show that strong communities can facilitate global diffusion by enhancing local, intra-community spreading. Using both analytic approaches and numerical simulations, we demonstrate the existence of an optimal network modularity, where global diffusion require the minimal number of early adopters.

Kivela M., Arenas A., Barthelemy M., Gleeson J.P., Moreno Y., Porter M.A.

In most natural and engineered systems, a set of entities interact with each other in complicated patterns that can encompass multiple types of relationships, change in time, and include other types of complications. Such systems include multiple subsystems and layers of connectivity, and it is important to take such “multilayer” features into account to try to improve our understanding of complex systems. Consequently, it is necessary to generalize “traditional” network theory by developing (and validating) a framework and associated tools to study multilayer systems in a comprehensive fashion. The origins of such efforts date back several decades and arose in multiple disciplines, and now the study of multilayer networks has become one of the most important directions in network science. In this paper, we discuss the history of multilayer networks (and related concepts) and review the exploding body of work on such networks. To unify the disparate terminology in the large body of recent work, we discuss a general framework for multilayer networks, construct a dictionary ∗Corresponding author: porterm@maths.ox.ac.uk 1 ar X iv :1 30 9. 72 33 v4 [ ph ys ic s. so cph ] 3 M ar 2 01 4 of terminology to relate the numerous existing concepts to each other, and provide a thorough discussion that compares, contrasts, and translates between related notions such as multilayer networks, multiplex networks, interdependent networks, networks of networks, and many others. We also survey and discuss existing data sets that can be represented as multilayer networks. We review attempts to generalize single-layer-network diagnostics to multilayer networks. We also discuss the rapidly expanding research on multilayer-network models and notions like community structure, connected components, tensor decompositions, and various types of dynamical processes on multilayer networks. We conclude with a summary and an outlook.

Zhong Y., Zhang Y., Zhang J., Wan L.

Xie Y., Sun S., Huang Y., Wang J., Ye P.

Guo Q., Luo Y., Ou Y., Liu M., Liu J.

Wang Y., Zhao X., Shang J.

Lv C., Lei Y., Zhang Y., Duan D., Si S.

Wang F., Smolyak A., Dong G., Tian L., Havlin S., Sela A.

Shi C., Qi J., Zhi J., Zhang C., Chen Q., Na X.

Hu X., Dong G., Christensen K., Sun H., Fan J., Tian Z., Gao J., Havlin S., Lambiotte R., Meng X.

Quantum networks (QNs) exhibit stronger connectivity than predicted by classical percolation, yet the origin of this phenomenon remains unexplored. We apply a statistical physics model—concurrence percolation—to uncover the origin of stronger connectivity on hierarchical scale-free networks, the ( U , V ) flowers. These networks allow full analytical control over path connectivity through two adjustable path-length parameters, ≤ V . This precise control enables us to determine critical exponents well beyond current simulation limits, revealing that classical and concurrence percolations, while both satisfying the hyperscaling relation, fall into distinct universality classes. This distinction arises from how they “superpose” parallel, nonshortest path contributions into overall connectivity. Concurrence percolation, unlike its classical counterpart, is sensitive to nonshortest paths and shows higher resilience to detours as these paths lengthen. This enhanced resilience is also observed in real-world hierarchical, scale-free internet networks. Our findings highlight a crucial principle for QN design: When nonshortest paths are abundant, they notably enhance QN connectivity beyond what is achievable with classical percolation.

Ma F., Yu W., Ma X.

Pei J., Liu Y., Wang J., Wang W.

Understanding the robustness of networks is a key step to design stable networked systems and protect them from being collapsed under small initial failures. In a two-layer multiplex network with flow, where physical quantities such as traffic flow or electricity move, a global cascading failure may be triggered out when edges in one layer fail and their loads are redistributed within the layer and to the other layer. Here we propose an edge pressure index to identify the critical edges which are the most likely to initiate a cascading failure in the network with flow. By reinforcing the critical edges, the robustness of the multiplex networks can be significantly enhanced. Based on large simulations on both synthetic networks and real-world networks, we find that protecting critical edges identified by the edge pressure index outperforms protecting edges with the highest betweenness centrality and the randomly selected edges in enhancing the robustness of the network. Furthermore, preventing the initial cascading failures between layers is critical to reduce the cascading failure size, which is due to the accumulative effects of redistributed loads. When the layer under initial attack is a heterogeneous BA network, which is more robust under flow redistribution, the entire system is more robust because the edge failures in the BA network create less intra- and inter-layer load redistribution.

Kouam W., Hayel Y., DEUGOUÉ G., Kamhoua C.

van Elteren C., Quax R., Sloot P.M.

Complex networks, from neuronal assemblies to social systems, can exhibit abrupt, system-wide transitions without external forcing. These endogenously generated “noise-induced transitions” emerge from the intricate interplay between network structure and local dynamics, yet their underlying mechanisms remain elusive. Our study unveils two critical roles that nodes play in catalyzing these transitions within dynamical networks governed by the Boltzmann–Gibbs distribution. We introduce the concept of “initiator nodes”, which absorb and propagate short-lived fluctuations, temporarily destabilizing their neighbors. This process initiates a domino effect, where the stability of a node inversely correlates with the number of destabilized neighbors required to tip it. As the system approaches a tipping point, we identify “stabilizer nodes” that encode the system’s long-term memory, ultimately reversing the domino effect and settling the network into a new stable attractor. Through targeted interventions, we demonstrate how these roles can be manipulated to either promote or inhibit systemic transitions. Our findings provide a novel framework for understanding and potentially controlling endogenously generated metastable behavior in complex networks. This approach opens new avenues for predicting and managing critical transitions in diverse fields, from neuroscience to social dynamics and beyond.

Wang C., Hu X., Dong G.

Quantum entanglement as a non-local correlation between particles is critical to the transmission of quantum information in quantum networks (QNs); the key challenge lies in establishing long-distance entanglement transmission between distant targets. This issue aligns with percolation theory, and as a result, an entanglement distribution scheme called “Classical Entanglement Percolation” (CEP) has been proposed. While this scheme provides an effective framework, “Quantum Entanglement Percolation” (QEP) indicates a lower percolation threshold through quantum preprocessing strategies, which will modify the network topology. Meanwhile, an emerging statistical theory known as “Concurrence Percolation” reveals the unique advantages of quantum networks, enabling entanglement transmission under lower conditions. It fundamentally belongs to a different universality class from classical percolation. Although these studies have made significant theoretical advancements, most are based on an idealized pure state network model. In practical applications, quantum states are often affected by thermal noise, resulting in mixed states. When these mixed states meet specific conditions, they can be transformed into pure states through quantum operations and further converted into singlets with a certain probability, thereby facilitating entanglement percolation in mixed state networks. This finding greatly broadens the application prospects of quantum networks. This review offers a comprehensive overview of the fundamental theories of quantum percolation and the latest cutting-edge research developments.

Zhou L., Liao H., Tan F., Yin J.

Zhang X., Sun S., Wang L.