Entrainment Competition in Complex Networks

Dynamics of overlapping structures in modular networks

Maximizing Entropy Yields Spatial Scaling in Social Networks Entrainment Competition in Complex Networks

Dimension of spatially embedded networks

Dynamical overlap of protein interaction networks: A method to predict protein functions

Percolation of spatially constraint networks

Possible Origin of Efficient Navigation in Small Worlds

Unveiling Protein Functions through the Dynamics of the Interaction Network

Complex networks embedded in space: Dimension and scaling relations between mass, topological distance and Euclidean distance

Reliability Analysis of Interdependent Networks Using Percolation Theory

Reliability Modelling and Simulation of Complex Systems

Abstract: The efficiency of complex technological systems requires the guarantee on their reliability against underlying catastrophes. The complexity encoded in their structure and functions makes cascading failures the main failure mode in complex systems. The development of complex systems' reliability technology relies on the modelling and simulation of the cascading failure. For the complex system, it is difficult to perform macroscopic analysis with tools based on robability theory because of their numerous system states. Meanwhile, it is also difficult to analyse it completely by microscopic system details due to their nonlinear coupling characteristics. The properties of complex systems require systematic analysis in multilevel. As the network science becomes available to model and study the complex system, its underlying concept of statistical physics is suitable to understand the complex system from the relationship between macroscopic properties and microscopic activities. We will review the progress made by network science recently including latest formalism of interdependent network theory, which can be used to understand and study the reliability problem of complex system.

Review of the Interdependent Networks

Spatially localized attacks on interdependent networks: the existence of a finite critical attack size

The resilience of interdependent transportation networks under targeted attack

The robustness of interdependent transportation networks under targeted attack

A Modeling Framework for System Restoration from Cascading Failures

CYBER 2014 Organizing Committees

Epidemics on interconnected lattices

Fault Propagation Model in Mobile Ad Hoc Network Based on Random Walk Model

Framework design for reliability engineering of complex systems

From a single network to a network of networks

Modeling of self-healing against cascading overload failures in complex networks

Reliability Assessment Method of SOA Architecture Software System Based on Complex Network

Robustness of networks with topologies of dependency links

Spatial correlation analysis of cascading failures: Congestions and Blackouts

Epidemics in Interconnected Small-World Networks

Localized attacks on spatially embedded networks with dependencies

Abstract: Many real world complex systems such as critical infrastructure networks are embedded in space and their components may depend on one another to function. They are also susceptible to geographically localized damage caused by malicious attacks or natural disasters. Here, we study a general model of spatially embedded networks with dependencies under localized attacks. We develop a theoretical and numerical approach to describe and predict the effects of localized attacks on spatially embedded systems with dependencies. Surprisingly, we find that a localized attack can cause substantially more damage than an equivalentrandom attack. Furthermore, we find that for a broad range of parameters, systems which appear stable are in fact metastable. Though robust to random failures—even of finite fraction—if subjected to a localized attack larger than a critical size which is independent of the system size (i.e., a zero fraction), a cascading failure emerges which leads to complete system collapse. Our results demonstrate the potential high risk of localized attacks on spatially embedded network systems with dependencies and may be useful for designing more resilient systems.

Network reliability analysis based on percolation theory

Abstract: In this paper, we propose a new way of looking at the reliability of a network using percolation theory. In this new view, a network failure can be regarded as a percolation process and the critical threshold of percolation can be used as network failure criterion linked to the operational settings under control. To demonstrate our approach, we consider both random network models and real networks with different nodes and/or edges lifetime distributions. We study numerically and theoretically the network reliability and find that the network reliability can be solved as a voting system with threshold given by percolation theory. Then we find that the average lifetime of random network increases linearly with the average lifetime of its nodes with uniform life distributions. Furthermore, the average lifetime of the network becomes saturated when system size is increased. Finally, we demonstrate our method on the transmission network system of IEEE 14 bus.

Percolation properties in a traffic model

Abstract: As a dynamical complex system, traffic is characterized by a transition from free flow to congestions, which is mostly studied in highways. However, despite its importance in developing congestion mitigation strategies, the understanding of this common traffic phenomenon in a city-scale is still missing. An open question is how the traffic in the network collapses from a global efficient traffic to isolated local flows in small clusters, i.e. the question of traffic percolation. Here we study the traffic percolation properties on a lattice by simulation of an agent-based model for traffic. A critical traffic volume in this model distinguishes the free-state from congested state of traffic. Our results show that the threshold of traffic percolation decreases with increasing traffic volume and reaches a minimum value at the critical traffic volume. We show that this minimal threshold is the result of longest spatial correlation between traffic flows at the critical traffic volume. These findings may help to develop congestion mitigation strategies in a network view.

Percolation transition in dynamical traffic network with evolving critical bottlenecks

Abstract: A critical phenomenon is an intrinsic feature of traffic dynamics, during which transition between isolated local flows and global flows occurs. However, very little attention has been given to the question of how the local flows in the roads are organized collectively into a global city flow. Here we characterize this organization process of traffic as “traffic percolation,” where the giant cluster of local flows disintegrates when the second largest cluster reaches its maximum. We find in real-time data of city road traffic that global traffic is dynamically composed of clusters of local flows, which are connected by bottleneck links. This organization evolves during a day with different bottleneck links appearing in different hours, but similar in the same hours in different days. A small improvement of critical bottleneck roads is found to benefit significantly the global traffic, providing a method to improve city traffic with low cost. Our results may provide insights on the relation between traffic dynamics and percolation, which can be useful for efficient transportation, epidemic control, and emergency evacuation.

Recent Progress on the Resilience of Complex Networks

Abstract: Many complex systems in the real world can be modeled as complex networks, which has captured in recent years enormous attention from researchers of diverse fields ranging from natural sciences to engineering. The extinction of species in ecosystems and the blackouts of power girds in engineering exhibit the vulnerability of complex networks, investigated by empirical data and analyzed by theoretical models. For studying the resilience of complex networks, three main factors should be focused on: the network structure, the network dynamics and the failure mechanism. In this review, we will introduce recent progress on the resilience of complex networks based on these three aspects. For the network structure, increasing evidence shows that biological and ecological networks are coupled with each other and that diverse critical infrastructures interact with each other, triggering a new research hotspot of “networks of networks” (NON), where a network is formed by interdependent or interconnected networks. The resilience of complex networks is deeply influenced by its interdependence with other networks, which can be analyzed and predicted by percolation theory. This review paper shows that the analytic framework for NON yields novel percolation laws for  interdependent networks and also shows that the percolation theory of a single network studied extensively in physics and mathematics in the last 60 years is a specific limited case of the more general case of  interacting networks. Due to spatial constraints inherent in critical infrastructures, including the power gird, we also review the progress on the study of spatially-embedded interdependent networks, exhibiting extreme vulnerabilities compared to their non-embedded counterparts, especially in the case of localized attack. For the network dynamics, we illustrate the percolation framework and methods using an example of a real transportation system, where the analysis based on network dynamics is significantly different from the structural static analysis. For the failure mechanism, we here review recent progress on the spontaneous recovery after network collapse. These findings can help us to understand, realize and hopefully mitigate the increasing risk in the resilience of complex networks.

Gravitational scaling in Beijing Subway Network

Abstract: Recently, with the availability of various traffic datasets, human mobility has been studied in different contexts. Researchers attempt to understand the collective behaviors of human movement with respect to the spatio-temporal distribution in traffic dynamics, from which a gravitational scaling law characterizing the relation between the traffic flow, population and distance has been found. However, most studies focus on the integrated properties of gravitational scaling, neglecting its dynamical evolution during different hours of a day. Investigating the hourly traffic flow data of Beijing subway network, based on the hop-count distance of passengers, we find that the scaling exponent of the gravitational law is smaller in Beijing subway system compared to that reported in Seoul subway system. This means that traffic demand in Beijing is much stronger and less sensitive to the travel distance. Furthermore, we analyzed the temporal evolution of the scaling exponents in weekdays and weekends. Our findings may help to understand and improve the traffic congestion control in different subway systems.

Observability Transitions in Networks with Betweenness Preference

Abstract: A network is considered observable if its current state can be determined in finite time from knowledge of the observed states. The observability transitions in networks based on random or degree-correlated sensor placement have recently been studied. However, these placement strategies are predominantly based on local information regarding the network. In this paper, to understand the phase transition process of network observability, we analyze the network observability transition for a betweenness-based sensor placement strategy, in which sensors are placed on nodes according to their betweenness. Using numerical simulations, we compute the size of the network’s largest observable component (LOC) and compare the observability transitions for different sensor placements. We find that betweenness-based sensor placement can generate a larger LOC in the observability transition than the random or degree-based placement strategy in both model and real networks. This finding may help to understand the relationship between network observability and the topological properties of the network.

Reliability analysis of interdependent lattices

Abstract: Network reliability analysis has drawn much attention recently due to the risks of catastrophic damage in networked infrastructures. These infrastructures are dependent on each other as a result of various interactions. However, most of the reliability analyses of these interdependent networks do not consider spatial constraints, which are found important for robustness of infrastructures including power grid and transport systems. Here we study the reliability properties of interdependent lattices with different ranges of spatial constraints. Our study shows that interdependent lattices with strong spatial constraints are more resilient than interdependent Erdös–Rényi networks. There exists an intermediate range of spatial constraints, at which the interdependent lattices have minimal resilience.

Resilience of Epidemics on Networks

Abstract: Epidemic propagation on complex networks has been widely investigated, mostly with invariant parameters. However, the process of epidemic propagation is not always constant. Epidemics can be affected by various perturbations, and may bounce back to its original state, which is considered resilient. Here, we study the resilience of epidemics on networks, by introducing a different infection rate λ_2 during SIS (susceptible-infected-susceptible) epidemic propagation to model perturbations (control state), whereas the infection rate is λ_1 in the rest of time. Through simulations and theoretical analysis, we find that even for λ_2>λ_c, epidemics eventually could bounce back if control duration is below a threshold. This critical control time for epidemic resilience, i.e., cd_max can be predicted by the diameter (d) of the underlying network, with the quantitative relation cd_max~d^α. Our findings can help to design a better mitigation strategy for epidemics.

Complex Systems and Networks

Spatio-temporal propagation of cascading overload failures in spatially embedded networks

Abstract: Different from the direct contact in epidemics spread, overload failures propagate through hidden functional dependencies. Many studies focused on the critical conditions and catastrophic consequences of cascading failures. However, to understand the network vulnerability and mitigate the cascading overload failures, the knowledge of how the failures propagate in time and space is essential but still missing. Here we study the spatio-temporal propagation behaviour of cascading overload failures analytically and numerically on spatially embedded networks. The cascading overload failures are found to spread radially from the centre of the initial failure with an approximately constant velocity. The propagation velocity decreases with increasing tolerance, and can be well predicted by our theoretical framework with one single correction for all the tolerance values. This propagation velocity is found similar in various model networks and real network structures. Our findings may help to predict the dynamics of cascading overload failures in realistic systems.

Abrupt transitions in collaborative social networks

Abstract: Despite the wide use of networks as a versatile tool for exploring complex social systems, little is known about how to detect and forecast abrupt changes in social systems. In this report, we develop an early warning approach based on network properties to detect such changes. By analysing three collaborative social networks—one co-stardom, one patent and one scientific collaborative network, we discover that abrupt transitions inherent in these networks can serve as a good early warning signal, indicating, respectively, the dissolution of the Soviet Union, the emergence of the “soft matter” research field, and the merging of two scientific communities. We then develop a clique growth model that explains the universal properties of these real networks and find that they belong to a new universality class, described by the Gumbel distribution.

Comparison of traffic reliability index with real traffic data

Abstract: Existing studies have developed different indices based on various approaches including network connectivity, delay time and flow capacity, estimating the traffic reliability states from different angles. However, these indices mainly estimate traffic reliability from single view and rarely consider the combined effect of city traffic dynamics and underlying network structure. Based on percolation theory, Li et al. has developed a traffic reliability index to address this issue (Proc. Natl. Acad. Sci. USA 112(3):669-672, 2015) [1]. Here we compare this percolation-based index with one of the well-known index - congestion delay index (CDI). Using real traffic data of Beijing and Shenzhen (two large cities in China), we compare the two indices in the macroscopic trends and microscopic extreme values. The two indices are found to indicate the state of real-time traffic reliability in different consideration. Our results can be used for better evaluation of traffic system reliability and mitigation measures of traffic jams.

Epidemic mitigation via awareness propagation in communication networks: the role of time scales

Abstract: The participation of individuals in multi-layer networks allows for feedback between network layers, opening new possibilities to mitigate epidemic spreading. For instance, the spread of a biological disease such as Ebola in a physical contact network may trigger the propagation of the information related to this disease in a communication network, e.g. an online social network. The information propagated in the communication network may increase the awareness of some individuals, resulting in them avoiding contact with their infected neighbors in the physical contact network, which might protect the population from the infection. In this work, we aim to understand how the time scale γ of the information propagation (speed that information is spread and forgotten)in the communication network relative to that of the epidemic spread (speed that an epidemic is spread and cured)in the physical contact network influences such mitigation using awareness information. We begin by proposing a model of the interaction between information propagation and epidemic spread, taking into account the relative time scale γ. We analytically derive the average fraction of infected nodes in the meta-stable state for this model (i) by developing an individual-based mean-field approximation (IBMFA) method and (ii) by extending the microscopic Markov chain approach (MMCA). We show that when the time scale γ of the information spread relative to the epidemic spread is large, our IBMFA approximation is better compared to MMCA near the epidemic threshold, whereas MMCA performs better when the prevalence of the epidemic is high. Furthermore, we find that an optimal mitigation exists that leads to a minimal fraction of infected nodes. The optimal mitigation is achieved at a non-trivial relative time scale γ, which depends on the rate at which an infected individual becomes aware. Contrary to our intuition, information spread too fast in the communication network could reduce the mitigation effect. Finally, our finding has been validated in the real-world two-layer network obtained from the location-based social network Brightkite.

Improvement of Traffic Percolation Based on Bottlenecks

Abstract: The formation process of global traffic flow from isolated local traffic flows can be considered as a percolation process. During this transition, the critical traffic bottleneck plays an important role in maintaining the global functional connectivity of the whole system. However, little attention has been paid to how the traffic percolation will be benefited from the improvements of traffic percolation bottlenecks. Here, we study the improvement of traffic bottlenecks in a traffic model and find that the traffic bottlenecks can greatly affect the organization efficiency of traffic flow. We propose a method of traffic bottlenecks load-reducing, which shows a significant improvement of traffic percolation on the network scale under different traffic conditions. Comparing with different methods, we demonstrate the advantage of the method of traffic bottlenecks load-reducing in the improvement of traffic percolation. Our findings may provide new insights for the research of bottlenecks and develop effective measures to improve the traffic reliability in real traffic.

Mitigation of cascading failure with dynamical flux removal

Abstract: Exploring cascading failure mitigation strategies to protect the complex networked systems is of both research interest and engineering significance. Progress on defense strategies such as removing permanently flux after the initial failure has been made. This paper proposes a new method considering the dynamical flux removal at each time step to mitigate the cascading failure. Results on both scale-free network model and real transportation networks such as Oldenburg road network and California road network reveal that the dynamical flux removal is superior to the static flux removal strategy, where there exists an optimal removal fraction. This method may be helpful for designing the self-healing mechanism for the future intelligent transportation systems.

Optimal cost for strengthening or destroying a given network

Abstract: Strengthening or destroying a network is a very important issue in designing resilient networks or in planning attacks against networks including planning strategies to immunize a network against diseases, viruses etc.. Here we develop a method for strengthening or destroying a random network with a minimum cost. We assume a correlation between the cost required to strengthen or destroy a node and the degree of the node. Accordingly, we define a cost function c(k), which is the cost of strengthening or destroying a node with degree k. Using the degrees k in a network and the cost function c(k), we develop a method for defining a list of priorities of degrees, and for choosing the right group of degrees to be strengthened or destroyed that minimizes the total price of strengthening or destroying the entire network. We find that the list of priorities of degrees is universal and independent of the network’s degree distribution, for all kinds of random networks. The list of priorities is the same for both strengthening a network and for destroying a network with minimum cost. However, in spite of this similarity there is a difference between their p_c - the critical fraction of nodes that has to be functional, to guarantee the existence of a giant component in the network.

Resilience of epidemics for SIS model on networks

Abstract: Recently, the dynamic modeling of complex networks has become an important means for the analysis of epidemic propagation. However, in the field of epidemiology, most studies of epidemic spreading mainly focus on the phase of epidemic outbreak on networks with nearly invariant parameters. Epidemics can be affected by various perturbations and may bounce back to its original state, presenting corresponding resilient behaviors, which have hardly been studied. In this paper, we perform studies on the resilience of epidemics on networks by lowering the infection rate during control state. After adding the “control” stage, the simulation results on different types of networks show that the epidemic can restore to the original steady state in the finite network size under certain conditions. We find that the resilience of epidemic propagation depends on the infection rate λ_2 with duration cd of control stage. In addition, the threshold, cd_max, is strongly related to the network structure, which appears to scale with network diameters. The discovery of cd_max can provide advanced indicator for the resilience of epidemics, which can help to design protection strategy keeping systems from a secondary epidemic outbreaks.

Robustness of networks with dependency topology

Abstract: The robustness of complex networks with dependency links has been studied in recent years. However, previous studies focused mostly on the robustness of networks with dependency relations having local and simple structures, not considering the general cases where global network topology is formed by dependency links. Here, we analyze the percolation properties of network models composed of both connectivity and dependency links, where in addition to the usual connectivity links, dependency links also follow a certain network topology. We perform theoretical analysis and numerical simulations to understand the critical effects of dependency topology on the network robustness. Our results suggest that for a given network topology of connectivity, dependency topology can influence the network robustness, leading to different percolation types. Furthermore, we also give the theoretical analysis and simulation results on different combinations of connectivity topology and dependency topology. Our results may help to design and optimize the network robustness considering the underlying complicated dependency relationships.

Spatio-temporal propagation of traffic jams in urban traffic networks

Abstract: Since the first reported traffic jam about a century ago, traffic congestion has been intensively studied with various methods ranging from macroscopic to microscopic viewpoint. However, due to the population growth and fast civilization, traffic congestion has become significantly worse not only leading to economic losses, but also causes environment damages. Without understanding of jams spatio-temporal propagation behavior in a city, it is impossible to develop efficient mitigation strategies to control and improve city traffic. Although some progress has been made in recent studies based on available traffic data regarding general features of traffic, the understanding of the spatio-temporal propagation of traffic jams in urban traffic is still unclear. Here we study the spatio-temporal propagation behavior of traffic jams based on collected empirical traffic data in big cities. We developed a method to identify influential jam centers and find that jams spread radially from multiple jam centers with a range of valor ties. Our findings may help to predict and even control the traffic jam propagation, which could be helpful for the development of future autonomous driving technology and intelligent transportation system.

Switch between critical percolation modes in city traffic dynamics

Abstract: Percolation transition is widely observed in networks ranging from biology to engineering. While much attention has been paid to network topologies, studies rarely focus on critical percolation phenomena driven by network dynamics. Using extensive real data, we study the critical percolation properties in city traffic dynamics. Our results suggest that two modes of different critical percolation behaviors are switching in the same network topology under different traffic dynamics. One mode of city traffic (during nonrush hours or days off) has similar critical percolation characteristics as small world networks, while the other mode (during rush hours on working days) tends to behave as a 2D lattice. This switching behavior can be understood by the fact that the high-speed urban roads during nonrush hours or days off (that are congested during rush hours) represent effective long-range connections, like in small world networks. Our results might be useful for understanding and improving traffic resilience.

Design of endurable networks in the presence of aging

Abstract: Networks are designed to satisfy given objectives under specific requirements. While the static connectivity of networks is normally analyzed and corresponding design principles for static robustness are proposed, the challenge still remains of how to design endurable networks that maintain the required level of connectivity during its whole lifespan, against component aging. We introduce network endurance as a new concept to evaluate networks overall performance during its whole lifespan, considering both network connectivity and network duration. We develop a framework for designing an endurable network by allocating the expected lifetimes of its components, given a limited budget. Based on percolation theory and simulation, we find that the maximal network endurance can be achieved with a quantitative balance between network duration and connectivity. For different endurance requirements, we find that the optimal design can be separated into two categories: strong dependence of lifetime on node’s degree leads to larger network lifetime, while weak dependence generates stronger network connectivity. Our findings could help network design, by providing a quantitative prediction of network endurance based on network topology.

Fake news propagate differently from real news even at early stages of spreading

Abstract: Social media can be a double-edged sword for society, either as a convenient channel exchanging ideas or as an unexpected conduit circulating fake news through a large population. While existing studies of fake news focus on theoretical modeling of propagation or identification methods based on machine learning, it is important to understand the realistic mechanisms between theoretical models and black-box methods. Here we track large databases of fake news and real news in both, Weibo in China and Twitter in Japan from different culture, which include their complete traces of re-postings. We find in both online social networks that fake news spreads distinctively from real news even at early stages of propagation, e.g. five hours after the first re-postings. Our finding demonstrates collective structural signals that help to understand the different propagation evolution of fake news and real news. Different from earlier studies, identifying the topological properties of the information propagation at early stages may offer novel features for early detection of fake news in social media.

Identification of key roads with minimal resilience in city traffic

Abstract: As the lifeline system for city, transportation systems may be degraded for various reasons leading to the uncertainty on the reliability of traffic operation. While different reliability measures have been proposed for city traffic, it still remains challenging how congested roads are recovered in daily traffic operation. Based on the concept of resilience and the use of real-time traffic data, we study the resilience of roads during the daily traffic. Through the comparison of different roads, we can identify the worst resilient roads that cannot recover soon from the congestion during the rush hours. These identified roads with minimal resilience can be the targets of traffic improvement in the corresponding reliability management.

Is city traffic damaged by torrential rain?

Abstract: Extreme weather, such as torrential rain, could lead to severe damage to transportation. Many studies have been proposed focusing on the influence of extreme weather on the traffic flow properties. However, the robustness of whole dynamic traffic networks under extreme weather is rarely addressed. Particularly, little attention has been paid to the question whether and how the local destruction of roads is aggregated into a degradation of global traffic operation. Based on real-time traffic data, here we apply percolation analysis on traffic networks and find that the torrential rain can lead to different effects on different levels: on the network scale, the traffic percolation threshold as an indicator for city traffic reliability is stable against weather perturbation, while a portion of roads at the microscopic level is significantly influenced and forming local cluster isolated from the main functional network. This may be due to the fact that torrential rain and other extreme weather condition will not only generate the damaged roads in the supply end, but also reduce the traffic demand correspondingly. Our research suggests the traffic percolation may reflect the nature of relation between local flow and global flow, which can help to design corresponding management strategies.

Optimizing random searches on three-dimensional lattices

Abstract: Search is a universal behavior related to many types of intelligent individuals. While most studies have focused on search in two or infinite-dimensional space, it is still missing how search can be optimized in three-dimensional space. Here we study random searches on three-dimensional (3d) square lattices with periodic boundary conditions, and explore the optimal search strategy with a power-law step length distribution, P(l)~l^(-μ), known as Lévy flights. We find that compared to random searches on two-dimensional (2d) lattices, the optimal exponent μ_oupt on 3d lattices is relatively smaller in non-destructive case and remains similar in destructive case. We also find μ_oupt decreases as the lattice length in z direction increases under high target density. Our findings may help us to understand the role of spatial dimension in search behaviors.

Repetitive users network emerges from multiple rumor cascades

Abstract: Rumor spreading on online social media is presenting a significant threat to society of post-truth epoch. Extensive efforts have been devoted to rumor identification and debunking, assuming that a specific rumor propagation is a single event network and neglecting possible interdependence between different rumor cascades. Here we study the collective propagation of multiple rumors, and surprisingly find a network of users that repeatedly participate in different rumor cascades. Though these repetitive users demonstrate minor difference at the level of single propagation network, they are found to form a significantly more intensive collaboration network from multiple rumor cascades compared to news propagation. The clique-like cluster formed by repetitive rumor spreaders can serve as a high quality feature for rumor identification and blocking targets for rumor prevention. Our findings can provide a better understanding of rumor spread by viewing multiple rumor propagations as one interacting rumor ecosystem, and suggest novel methods for distinguishing and mitigation based on rumor spreading history.

Function-call Network Reliability of Kernel in Android Operating System

Restoration of interdependent network against cascading overload failure

Abstract: Many networks are physically or logically interdependent with each other, such as smart power grid, city traffic network and communication systems, where cascading overload failure becomes a major threat. Based on a load-dependent cascading model, we investigate the restoration characteristics in the consideration of repair resource, timing and load tolerance, for different coupling strength and network topologies in interdependent networks. We find that the restoration on the network with different coupling strength may lead to two extreme system effects with early repair: full recovery or completely collapse. Furthermore, SF–SF network is sensitive to repair resources, while repair effect of ER–ER network increases sharply when load tolerance is increased. When overloads are triggered in an ER network coupled with a SF network, the restoration effect can be obviously worse than other topology combinations. Our findings may help to design restoration strategy for interdependent networks and improve the system resilience.

Scale-free resilience of real traffic jams

Abstract: The concept of resilience can be realized in natural and engineering systems, representing the ability of a system to adapt and recover from various disturbances. Although resilience is a critical property needed for understanding and managing the risks and collapses of transportation systems, an accepted and useful definition of resilience for urban traffic as well as its statistical property under perturbations are still missing. Here, we define city traffic resilience based on the spatiotemporal clusters of congestion in real traffic and find that the resilience follows a scale-free distribution in 2D city road networks and 1D highways with different exponents but similar exponents on different days and in different cities. The traffic resilience is also revealed to have a scaling relation between the cluster size of the spatiotemporal jam and its recovery duration independent of microscopic details. Our findings of universal traffic resilience can provide an indication toward better understanding and designing of these complex engineering systems under internal and external disturbances.

Switch between critical percolation modes in city traffic dynamics

Abstract: Percolation transition is widely observed in networks ranging from biology to engineering. While much attention has been paid to network topologies, studies rarely focus on critical percolation phenomena driven by network dynamics. Using extensive real data, we study the critical percolation properties in city traffic dynamics. Our results suggest that two modes of different critical percolation behaviors are switching in the same network topology under different traffic dynamics. One mode of city traffic (during nonrush hours or days off) has similar critical percolation characteristics as small world networks, while the other mode (during rush hours on working days) tends to behave as a 2D lattice. This switching behavior can be understood by the fact that the high-speed urban roads during nonrush hours or days off (that are congested during rush hours) represent effective long-range connections, like in small world networks. Our results might be useful for understanding and improving traffic resilience.

Evolution of Function-Call Network Reliability in Android Operating System

Abstract: Operating systems (OS) are critical infrastructures for information system. To design a highly reliable software, it is essential to understand the architecture feature of operating systems, which is recently explored by network analysis. While most focus is on the topological properties, the network reliability is rarely studied. In this paper, based on percolation method, we analyze the function-call graph of Android OS in different levels. While OS network is more vulnerable under degree-based percolation at node level, it becomes more vulnerable under strength-based percolation at community level. Furthermore, we found that although topological properties of kernel network are evolving with different released versions, percolation properties seem rather stable. Our findings may help to understand the reliability principle of OS architecture and to design new system testing methods.

Fake news propagate differently from real news even at early stages of spreading

Abstract: Social media can be a double-edged sword for society, either as a convenient channel exchanging ideas or as an unexpected conduit circulating fake news through a large population. While existing studies of fake news focus on theoretical modeling of propagation or identification methods based on machine learning, it is important to understand the realistic mechanisms between theoretical models and black-box methods. Here we track large databases of fake news and real news in both, Weibo in China and Twitter in Japan from different culture, which include their complete traces of re-postings. We find in both online social networks that fake news spreads distinctively from real news even at early stages of propagation, e.g. five hours after the first re-postings. Our finding demonstrates collective structural signals that help to understand the different propagation evolution of fake news and real news. Different from earlier studies, identifying the topological properties of the information propagation at early stages may offer novel features for early detection of fake news in social media.

Multiple metastable network states in urban traffic

Abstract: 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.

Network endurance against cascading overload failure

Abstract: Network endurance can be regarded as the upper limit of survival time before the system's complete breakdown, which is highly related to system resilience. Although network endurance against overload failure is critical for network design and operational management, the definition and corresponding evaluation method still remain challenging. In this paper, based on the load-dependent overload model, we define network endurance as the cascade duration at criticality before the complete network breakdown and develop an approach for endurance evaluation. We find that network endurance highly depends on initial disturbance intensity and cascade intensity. The network endurance with a uniform initial load distribution usually monotonically increases with decreasing initial disturbance intensity, while for other initial load distributions endurance behaviors are more complicated. We also provide theoretical analysis for the network endurance. Our findings may help to understand the network reliability mechanism against cascading overload failures and design a highly reliable network.

Percolation transition in temporal airport network

Abstract: The air transportation system has a critical impact on the global economy. While the system reliability is essential for the operational management of air traffic, it remains challenging to understand the network reliability of the air transportation system. This paper focuses on how the global air traffic is integrated from local scale along with operational time. The integration process of air traffic into a temporally connected network is viewed as percolation process by increasing the integration time constantly. The critical integration time  which is found during the integration process can measure the global reliability of air traffic. The critical links at  are also identified, the delay of which will influence the global integration of the airport network. These findings may provide insights on the reliability management for the temporal airport network.

Random walk model simulates the increased drowsiness of children with obstructive sleep apnea

Abstract: Obstructive sleep apnea (OSA) is a common sleep disorder, which is particularly harmful to children as it may lead to learning deficits, attention deficit hyperactivity disorder (ADHD) and growth retardation. Furthermore, OSA alters the dynamics of sleep-stage transitions and in particular increases the transition time from being awake to falling asleep (“drowsiness”). In this letter, we show that sleep bout durations during this transient state can be described by an exponential distribution with a longer characteristic time scale for OSA compared to healthy children. This finding can be simulated and better understood by using a random walk model of the integrated neuronal voltage of wake-promoting neurons, and by introducing a new concept of a light sleep threshold parameter  that distinguishes between drowsiness and deeper forms of light sleep. Our analysis also shows that the value of  correlates well with OSA severity. Moreover, we find that after OSA treatment, the parameter  returns to normal values similar to those we detected for healthy children. We anticipate that our methodology can help in better understanding and modeling sleep dynamics, and may improve diagnostics and treatment monitoring of OSA.