Search

While abrupt regime shifts between different metastable states have occurred in natural systems from many areas including ecology, biology, and climate, evidence for this phenomenon in transportation systems has been rarely observed so far. This limitation might be rooted in the fact that we lack methods to identify and analyze possible multiple states that could emerge at scales of the entire traffic network. Here, using percolation approaches, we observe such a metastable regime in traffic systems. In particular, we find multiple metastable network states, corresponding to varying levels of traffic performance, which recur over different days. Based on high-resolution global positioning system (GPS) datasets of urban traffic in the megacities of Beijing and Shanghai (each with over 50,000 road segments), we find evidence supporting the existence of tipping points separating three regimes: a global functional regime and a metastable hysteresis-like regime, followed by a global collapsed regime. We can determine the intrinsic critical points where the metastable hysteresis-like regime begins and ends and show that these critical points are very similar across different days. Our findings provide a better understanding of traffic resilience patterns and could be useful for designing early warning signals for traffic resilience management and, potentially, other complex systems.

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 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 an 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 non-zero when n increases from n = 1 to O(log N) (where N is the size of network). Thus, for SF networks, having knowledge of ≈log N nodes and immunizing 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., A novel network immunization strategy is proposed and studied to provide a theoretical framework for understanding and carrying out efficient immunization with limited knowledge.

Cascading failure is a potentially devastating process that spreads on real-world complex networks and can impact the integrity of wide-ranging infrastructures, natural systems, and societal cohesiveness. One of the essential features that create complex network vulnerability to failure propagation is the dependency among their components, exposing entire systems to significant risks from destabilizing hazards such as human attacks, natural disasters or internal breakdowns. Developing realistic models for cascading failures as well as strategies to halt and mitigate the failure propagation can point to new approaches to restoring and strengthening real-world networks. In this review, we summarize recent progress on models developed based on physics and complex network science to understand the mechanisms, dynamics and overall impact of cascading failures. We present models for cascading failures in single networks and interdependent networks and explain how different dynamic propagation mechanisms can lead to an abrupt collapse and a rich dynamic behavior. Finally, we close the review with novel emerging strategies for containing cascades of failures and discuss open questions that remain to be addressed., Comment: This review has been accepted for publication in the Journal of Complex Networks Published by Oxford University Press

Over the past few decades the world underwent several major economic and financial bubbles, such as the dot-com bubble of early 2000s and the global crisis following the collapse of the US housing market in 2008. Here we review the progress made in network theory as applied to economics and highlight some important insights complex networks allow into the highly interconnected economic system. Richness of phenomena that appears once we increase our complexity beyond a single network is explored and main results, as well as future research are discussed.

Detecting and characterizing community structure plays a crucial role in the study of networked systems. However, there is still a lack of understanding of how community structure affects the systems' resilience and stability. Here, we develop a framework to study the resilience of networks with community structure based on percolation theory. We find both analytically and numerically that the interlinks (connections between the communities) affect the percolation phase transition in a manner similar to an external field in a ferromagnetic-paramagnetic spin system. We also study the universality class by defining the analogous critical exponents $\delta$ and $\gamma$, and find that their values for various models and in real-world co-authors networks follow fundamental scaling relations as in physical phase transitions. The methodology and results presented here not only facilitate the study of resilience of networks but also brings a fresh perspective to the understanding of phase transitions under external fields., Comment: 15 pages,4 figures

We study a greedy forager who consumes food throughout a region. If the forager does not eat any food for S time steps it dies. We assume that the forager moves preferentially in the direction of greatest smell of food. Each food item in a given direction contributes towards the total smell of food in that direction, however the smell of any individual food item decays with its distance from the forager. We study both power-law decay and exponential decay of the smell with the distance of the food from the forager. For power-law decay, we vary the exponent α governing this decay, while for exponential decay we vary λ also governing the rate of the decay. For power-law decay we find, both analytically and through simulations, that for a forager living in one dimension, there is a critical value of α , namely , where for the forager will die in finite time, however for the forager has a nonzero probability to live infinite time. We calculate analytically the critical value, , separating these two behaviors and find that depends on S as . We find analytically that at the system has an essential singularity. For exponential decay we find analytically that for all λ , the forager has a finite probability to live for infinite time. We also study, using simulations, a forager with long-range decaying smell in two dimensions (2D) and find that for this case the forager always dies within finite time. However, in 2D we observe indications of an optimal α (and λ ) for which the forager has the longest lifetime.

Many interdependent, real-world infrastructures involve interconnections between different communities or cities. Here we study if and how the effects of such interconnections can be described as an external field for interdependent networks experiencing first-order percolation transitions. We find that the critical exponents $\gamma$ and $\delta$, related to the external field can also be defined for first-order transitions but that they have different values than those found for second-order transitions. Surprisingly, we find that both sets of different exponents can be found even within a single model of interdependent networks, depending on the dependency coupling strength. Specifically, the exponent $\gamma$ in the first-order regime (high coupling) does not obey the fluctuation dissipation theorem, whereas in the continuous regime (for low coupling) it does. Nevertheless, in both cases they satisfy Widom's identity, $\delta - 1 = \gamma / \beta$ which further supports the validity of their definitions. Our results provide physical intuition into the nature of the phase transition in interdependent networks and explain the underlying reasons for two distinct sets of exponents., Comment: 6 pages and 4 figures

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.

Much work has been devoted to studying percolation of networks and interdependent networks under varying levels of failures. Researchers have considered many different realistic network structures such as scale-free networks, spatial networks, and more. However, thus far no study has analyzed a system of hierarchical community structure of many networks. For example, infrastructure across cities is likely distributed with nodes tightly connected within small neighborhoods, somewhat less connected across the whole city, and even fewer connections between cities. Furthermore, while previous work identified interconnected nodes, those nodes with links outside their neighborhood, to be more likely to be attacked or to fail, in a hierarchical structure nodes can be interconnected in different layers (between neighborhoods, between cities, etc.). We consider here the case where the nodes with interconnections at the highest level of the hierarchy are most likely to fail, followed by those with interconnections at the next level, etc. This is because nodes at higher levels of the hierarchy have the longest links as well as having more flow passing through them. We develop an analytic solution for percolation of both single and interdependent networks of this structure and verify our theory through simulations. We find that, depending on the number of levels in the hierarchy, there may be multiple transitions in the giant component (fraction of connected nodes), as the network separates at the various levels. Our results show that these multiple jumps are a feature of hierarchical networks and can affect the vulnerability of infrastructure networks.

Earthquakes are one of the most devastating natural disasters that plague society. Skilled, reliable earthquake forecasting remains the ultimate goal for seismologists. Using the detrended fluctuation analysis (DFA) and conditional probability (CP) methods, we find that memory exists not only in interoccurrence seismic records but also in released energy as well as in the series of the number of events per unit time. Analysis of a standard epidemic-type aftershock sequences (ETAS) earthquake model indicates that the empirically observed earthquake memory can be reproduced only for a narrow range of the model's parameters. This finding therefore provides tight constraints on the model's parameters and can serve as a testbed for existing earthquake forecasting models. Furthermore, we show that by implementing DFA and CP results, the ETAS model can significantly improve the short-term forecasting rate for the real (Italian) earthquake catalog.

We study secure message-passing in the presence of multiple adversaries in modular networks. We assume a dominant fraction of nodes in each module have the same vulnerability, i.e., the same entity spying on them. We find both analytically and via simulations that the links between the modules (interlinks) have effects analogous to a magnetic field in a spin system in that for any amount of interlinks the system no longer undergoes a phase transition. We then define the exponents $\delta$, which relates the order parameter (the size of the giant secure component) at the critical point to the field strength (average number of interlinks per node), and $\gamma$, which describes the susceptibility near criticality. These are found to be $\delta=2$ and $\gamma=1$ (with the scaling of the order parameter near the critical point given by $\beta=1$). When two or more vulnerabilities are equally present in a module we find $\delta=1$ and $\gamma=0$ (with $\beta\geq2$). Apart from defining a previously unidentified universality class, these exponents show that increasing connections between modules is more beneficial for security than increasing connections within modules. We also measure the correlation critical exponent $\nu$, and the upper critical dimension $d_c$, finding that $\nu d_c=3$ as for ordinary percolation, suggesting that for secure message-passing $d_c =6$. These results provide an interesting analogy between secure message-passing in modular networks and the physics of magnetic spin-systems.

Networks interact with one another in a variety of ways. Even though increased connectivity between networks would tend to make the system more robust, if dependencies exist between networks, these systems are highly vulnerable to random failure or attack. Damage in one network causes damage in another. This leads to cascading failures which amplify the original damage and can rapidly lead to complete system collapse.

Many real systems such as, roads, shipping routes, and infrastructure systems can be modeled based on spatially embedded networks. The inter-links between two distant spatial networks, such as those formed by transcontinental airline flights, play a crucial role in optimizing communication and transportation over such long distances. Still, little is known about how inter-links affect the structural resilience of such systems. Here, we develop a framework to study the structural resilience of interlinked spatially embedded networks based on percolation theory. We find that the inter-links can be regarded as an external field near the percolation phase transition, analogous to a magnetic field in a ferromagnetic–paramagnetic spin system. By defining the analogous critical exponents δ and γ, we find that their values for various inter-links structures follow Widom's scaling relations. Furthermore, we study the optimal robustness of our model and compare it with the analysis of real-world networks. The framework presented here not only facilitates the understanding of phase transitions with external fields in complex networks but also provides insight into optimizing real-world infrastructure networks.

We present analytic and numeric results for percolation in a network formed of interdependent spatially embedded networks. We show results for a treelike and a random regular network of networks each with (i) unconstrained dependency links and (ii) dependency links restricted to a maximum Euclidean length $r$. Analytic results are given for each network of networks with spatially unconstrained dependency links and compared to simulations. For the case of two fully interdependent spatially embedded networks it was found [Li et al., Phys. Rev. Lett. 108, 228702 (2012)] that the system undergoes a first-order phase transition only for $rg{r}_{c}\ensuremath{\approx}8$. We find here that for treelike networks of networks (composed of $n$ networks) ${r}_{c}$ significantly decreases as $n$ increases and rapidly $(n\ensuremath{\ge}11)$ reaches its limiting value of 1. For cases where the dependencies form loops, such as in random regular networks, we show analytically and confirm through simulations that there is a certain fraction of dependent nodes, ${q}_{\mathrm{max}}$, above which the entire network structure collapses even if a single node is removed. The value of ${q}_{\mathrm{max}}$ decreases quickly with $m$, the degree of the random regular network of networks. Our results show the extreme sensitivity of coupled spatial networks and emphasize the susceptibility of these networks to sudden collapse. The theory proposed here requires only numerical knowledge about the percolation behavior of a single network and therefore can be used to find the robustness of any network of networks where the profile of percolation of a singe network is known numerically.

Many multiplex networks are embedded in space, with links more likely to exist between nearby nodes than distant nodes. For example, interdependent infrastructure networks can be represented as multiplex networks, where each layer has links among nearby nodes. Here, we model the effect of spatiality on the robustness of a multiplex network embedded in 2-dimensional space, where links in each layer are of variable but constrained length. Based on empirical measurements of real-world networks, we adopt exponentially distributed link lengths with characteristic length ζ. By changing ζ, we modulate the strength of the spatial embedding. When ζ → ∞, all link lengths are equally likely, and the spatiality does not affect the topology. However, when only short links are allowed, and the topology is overwhelmingly determined by the spatial embedding. We find that, though longer links strengthen a single-layer network, they make a multi-layer network more vulnerable. We further find that when ζ is longer than a certain critical value, , abrupt, discontinuous transitions take place, while for the transition is continuous, indicating that the risk of abrupt collapse can be eliminated if the typical link length is shorter than .

Many studies have explored spreading and diffusion through complex networks. The following study examines a specific case of spreading of opinions in modern society through two spreading schemes —defined as being either through "word of mouth" (WOM), or through online search engines (WEB). We apply both modelling and real experimental results and compare the opinions people adopt through an exposure to their friend's opinions, as opposed to the opinions they adopt when using a search engine based on the PageRank algorithm. A simulated study shows that when members in a population adopt decisions through the use of the WEB scheme, the population ends up with a few dominant views, while other views are barely expressed. In contrast, when members adopt decisions based on the WOM scheme, there is a far more diverse distribution of opinions in that population. The simulative results are further supported by an online experiment which finds that people searching information through a search engine end up with far more homogenous opinions as compared to those asking their friends.

Many infrastructure networks have a modular structure and are also interdependent with other infrastructures. 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 through simulations. We focus, for simplicity, 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 particularly realistic for modeling infrastructure across cities. Each city has its own infrastructures and different infrastructures are dependent only 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 previously been shown that single networks are very susceptible to the failure of the interconnected nodes (between communities) (Shai et al 2014 arXiv:1404.4748) and that attacks on these nodes are even more crippling than attacks based on betweenness (da Cunha et al 2015 arXiv:1502.00353). 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 significantly influence the type of transitions observed in interdependent networks and should be considered in attempts to make interdependent networks more resilient.