Complex System Reliability Lab
Research Results
Click to download at the bottom to save PDF files
  • 2006
  • 2007
  • 2008
  • 2010
  • 2011
  • 2013
  • 2014
  • 2015
  • 2016
  • 2017
  • 2018
  • 2019
  • 2020
Effects of Weight on Structure and Dynamics in Complex Networks
Abstract:Link weight is crucial in weighted complex networks. It provides additional dimension for describing and adjusting the properties of networks. The topological role of weight is studied by the effects of random redistribution of link weights based on regular network with initial homogeneous weight. The small world effect emerges due to the weight randomization. Its effects on the dynamical systems coupled by weighted networks are also investigated. Randomization of weight can increase the transition temperature in Ising model and enhance the ability of synchronization of chaotic systems dramatically.
Enhancing synchronizability by weight randomization on regular networks
Abstract:In weighted networks, redistribution of link weights can effectively change the properties of networks, even though the corresponding binary topology remains unchanged. In this paper, the effects of weight randomization on synchronization of coupled chaotic maps is investigated on regular weighted networks. The results reveal that synchronizability is enhanced by redistributing of link weights, i.e.coupled maps reach complete synchronization with lower cost. Furthermore, we show numerically that the heterogeneity of link weights could improve the complete synchronization on regular weighted networks.
Small-world effect induced by weight randomization on regular networks
Abstract:The concept of edge weight provides additional depth for describing and adjusting the properties of networks. Redistribution of edge weight can effectively change the properties of networks even though the corresponding binary topology remains unchanged. Based on regular networks with initially homogeneous dissimilarity weights, random redistribution of edge weight can be enough to induce small world phenomena. The effects of random weight redistribution on both static properties and dynamical models of networks are investigated. The results reveal that randomization of weight can enhance the ability of synchronization of chaotic systems dramatically.
Synchronization interfaces and overlapping communities in complex networks
Abstract: We show that a complex network of phase oscillators may display interfaces between domains (clusters) of synchronized oscillations. The emergence and dynamics of these interfaces are studied in the general framework of interacting phase oscillators composed of either dynamical domains (influenced by different forcing processes), or structural domains (modular networks). The obtained results allow to give a functional definition of overlapping structures in modular networks, and suggest a practical method to identify them. As a result, our algorithm could detect information on both single overlapping nodes and overlapping clusters.

Entrainment Competition in Complex Networks

Abstract: The response of a random and modular network to the simultaneous presence of two frequencies is considered. The competition for controlling the dynamics of the network results in different behaviors, such as frequency changes or permanent synchronization frustration, which can be directly related to the network structure. From these observations, we propose a new method for detecting overlapping communities in structured networks.

Dynamics of overlapping structures in modular networks

Abstract: Modularity is a fundamental feature of real networks, being intimately bounded to their functionality, i.e., to their capability of performing parallel tasks in a coordinated way. Although the modular structure of real graphs has been intensively studied, very little is known on the interactions between functional modules of a graph. Here, we present a general method based on synchronization of networking oscillators, that is able to detect overlapping structures in multimodular environments. We furthermore report the full analytical and theoretical description on the relationship between the overlapping dynamics and the underlying network topology. The method is illustrated by means of a series of applications.

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

Abstract: In addition to the well known common properties such as small world and community structures, recent empirical investigations suggest a universal scaling law for the spatial structure of social networks. Itis found that the probability density distribution of an individual to have a friend at distance r scales as P(r)∝r^(-1). The basic principle that yields this spatial scaling property is not yet understood. Here wepropose a fundamental origin for this law based on the concept of entropy. We show that this spatial scaling law can result from maximization of information entropy, which means individuals seek to maximize the diversity of their friendships. Such spatial distribution can benefit individuals significantly in optimally collecting information in a social network.

Dimension of spatially embedded networks

Abstract: The dimension of a system is one of the most fundamental quantities to characterize its structure and basic physical properties. Diffusion and vibrational excitations, for example, as well as the universal features of a system near a critical point depend crucially on its dimension. However, in the theory of complex networks the concept of dimension has been rarely discussed. Here we study models for spatially embedded networks and show how their dimension can be determined. Our results indicate that networks characterized by a broad distribution of link lengths have a dimension higher than that of the embedding space. We illustrate our findings using the global airline network and the Internet and argue that although these networks are embedded in two-dimensional space they should be regarded as systems with dimension close to 3 and 4.5, respectively. We show that the network dimension is a key concept to understand not only network topology, but also dynamical processes on networks, such as diffusion and critical phenomena including percolation.

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

Abstract: While most of the works on functional annotation of proteins via their network of interactions are exclusively based in topological measurements from the properties of the protein interaction network (PIN), we propose the application of an algorithm based on the synchronization behavior emerging from a modular network organization. The method relies on how phase oscillators organize in a network structure of dynamical interactions, and on a recently proposed technique for the identifaction of synchronization interfaces and overlapping communities [5] in ensembles of networking dynamical systems. The combination of the synchronization behavior of the PIN structure and an initial modular classification of proteins allows for protein function predictions of those proteins lying at the overlapping interface that are in agreement with predictions obtained by other methods.

Percolation of spatially constraint networks

Abstract: We study how spatial constraints are reflected in the percolation properties of networks embedded in one-dimensional chains and two-dimensional lattices. We assume longrange connections between sites on the lattice where two sites at distance  are chosen to be linked with probability P(r)r^(-δ). Similar distributions have been found in spatially embedded real etworks such as social and airline networks. We find that for networks embedded in two dimensions, with 2<δ<4, the ercolation properties show new intermediate behavior different from mean field, with critical exponents that depend on δ. For δ<2, the percolation transition belongs to the universality class of percolation in Erdös-Rényi networks (mean field), while for δ>4 it belongs to the universality class of percolation in regular lattices. For networks embedded in one dimension, we find that, for δ<1, the percolation transition is mean field. For 1<δ<2, the critical exponents depend on δ, while for δ>2 there is no ercolation transition as in regular linear chains.

Possible Origin of Efficient Navigation in Small Worlds

Abstract: The small-world phenomenon is one of the most important properties found in social networks. It includes both short path lengths and efficient navigation between two individuals. It is found by Kleinberg that navigation is efficient only if the probability density distribution of an individual to have a friend at distance  scales as . Although this spatial scaling is found in many empirical studies, the origin of how this scaling emerges is still missing. In this Letter, we propose the origin of this scaling law using the concept of entropy from statistical physics and show that this scaling is the result of optimization of collecting information in social networks.

Unveiling Protein Functions through the Dynamics of the Interaction Network

Abstract: Protein interaction networks have become a tool to study biological processes, either for predicting molecular functions or for designing proper new drugs to regulate the main biological interactions. Furthermore, such networks are known to be organized in sub-networks of proteins contributing to the same cellular function. However, the protein function prediction is not accurate and each protein has traditionally been assigned to only one function by the network formalism. By considering the network of the physical interactions between proteins of the yeast together with a manual and single functional classification scheme, we introduce a method able to reveal important information on protein function, at both micro- and macro-scale. In particular, the inspection of the properties of oscillatory dynamics on top of the protein interaction network leads to the identification of misclassification problems in protein function assignments, as well as to unveil correct identification of protein functions. We also demonstrate that our approach can give a network representation of the meta-organization of biological processes by unraveling the interactions between different functional classes.

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

Abstract: Many real networks are embedded in space, where in some of them the links length decay as a power law distribution with distance. Indications that such systems can be characterized by the concept of dimension were found recently. Here,we present further support for this claim, based on extensive numerical simulations for model networks embedded on lattices of dimensions d_e=1 and d_e=2. We evaluate the dimension d from the power law scaling of (a) the mass of the network with the Euclidean radius r and (b) the probability of return to the origin with the distance r travelled by the random walker. Both approaches yield the same dimension.For networks with δ<d_e, d is infinity, while for δ>2d_e, d obtains the value of the embedding dimension d_e. In the intermediate regime of interest d_e≤δ<2d_e, our numerical results suggest that d decreases continously from d=∞ to d_e, with d−d_e∼(δ-d_e)^(-1) for δ close to d_e. Finally, we discuss the scaling of the mass M and the Euclidean distance r with the topological distance ℓ (minimum number of links between two sites in the network). Our results suggest that in the intermediate regime d_eδ<2d_e, M(ℓ) and r(ℓ) do not increase with ℓ as a power law but with a stretched exponential, M(ℓ) exp[Aℓ^δ'(2-δ')] and r(ℓ) exp[Bℓ^δ'(2-δ')], where δ′=δ/d_e. The parameters A and B are related to d by d = A/B, such that M(ℓ)ℓ^dℓ. For δ<, M increases exponentially with ℓ, as known for δ = 0, while r is constant and independent of ℓ. For δ ≥ 2d_e, we find power law scaling, M(ℓ)ℓ^dℓ and r(ℓ) ℓ^(1/d_min), with d_ℓ·d_min=d. For networks embedded in d_e=1, we find the expected result, d_ℓ=d_min=1, while for networks embedded in d_e=2 we find surprisingly, that although d = 2, d_ℓ>2 and d_min< 1, in contrast to regular lattices.

Reliability Analysis of Interdependent Networks Using Percolation Theory

Abstract: Many complex systems have functional interdependency between each other and can be modeled as interdependent networks.The failure of a small fraction of nodes in interdependent networks may lead to catastrophic cascading failures across network borders. Starting from a model of static interdependent networks, by introducing lifetime for each component,we study the reliability properties and lifetimes of the interdependent networks to which these components belong. Depending on the lifetime of the network components, the trigger of cascading failures will shape the interdependent networks reliability. In this framework, we analyze the evolution of the reliability properties of interdependent networks, and compare them with single networks. Interdependent SF networks are found to have lower reliability than interdependent ER networks.

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

Abstract: A briefly review about the interdependent networks is given in this article. The concept and models of interdependent networks are introduced. The failure of nodes in one network may trigger cascading failures and catastrophic consequences. According to the topology of the system, the existing empirical research on the robustness of interdependent networks is reviewed from four aspects: the systems with one-to-one connection relationship, the systems with multiple dependencies, the systems of networks, and the scale-free networks. The existing methods for enhancing network robustness are given. At last, the research on interdependent networks is briefly summarized.

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

Abstract: Many real world complex systems such as infrastructure, communication and transportation networks are embedded in space, where entities of one system may depend on entities of other systems. These systems are subject to geographically localized failures due to malicious attacks or natural disasters. Here we study the resilience of a system composed of two interdependent spatially embedded networks to localized geographical attacks. We find that if an attack is larger than a finite (zero fraction of the system) critical size, it will spread through the entire system and lead to its complete collapse. If the attack is below the critical size, it will remain localized. In contrast, under random attack a finite fraction of the system needs to be removed to initiate system collapse. We present both numerical simulations and a theoretical approach to analyze and predict the effect of local attacks and the critical attack size. Our results demonstrate the high risk of local attacks on interdependent spatially embedded infrastructures and can be useful for designing more resilient systems.

The resilience of interdependent transportation networks under targeted attack

Abstract: Modern world builds on the resilience of interdependent infrastructures characterized as complex networks. Recently, a framework for analysis of interdependent networks has been developed to explain the mechanism of resilience in interdependent networks. Here we extend this interdependent network model by considering flows in the networks and study the system’s resilience under different attack strategies. In our model, nodes may fail due to either overload or loss of interdependency. Under the interaction between these two failure mechanisms, it is shown that interdependent scale-free networks show extreme vulnerability. The resilience of interdependent SF networks is found in our simulation much smaller than single SF network or interdependent SF networks without flows.

The robustness of interdependent transportation networks under targeted attack

Abstract: The modern world is built on the robustness of interdependent infrastructures, which can be characterized as complex networks. Recently, a framework for the analysis of interdependent networks has been developed to explain the mechanism of robustness in interdependent networks. Here, we extend this interdependent network model by considering flows in the networks, and we study the system's robustness under different attack strategies. In our model, nodes may fail because of either overload or loss of interdependency. Considering the interaction between these two failure mechanisms, it is shown that interdependent scale-free networks show extreme vulnerability. The robustness of interdependent scale-free networks is found in our simulations to be much smaller than that of the single scale-free networks or the interdependent scale-free networks without flows.

A Modeling Framework for System Restoration from Cascading Failures

Abstract: System restoration from cascading failures is an integral part of the overall defense against catastrophic breakdown in networked critical infrastructures. From the outbreak of cascading failures to the system complete breakdown,actions can be taken to prevent failure propagation through the entire network. While most analysis efforts have been carried out before or after cascading failures,restoration during cascading failures has been rarely studied. In this paper,we present a modeling framework to investigate the effects of in-process restoration,which depends strongly on the timing and strength of the restoration actions. Furthermore,in the model we also consider additional disturbances to the system due to restoration actions themselves. We demonstrate that the effect of restoration is also influenced by the combination of system loading level and restoration disturbance. Our modeling framework will help to provide insights on practical restoration from cascading failures and guide improvements of reliability and resilience of actual network systems.

CYBER 2014 Organizing Committees

1. Smart Power Systems and Smart Grids
2. Cloud Robotics and Automation
3. Challenges and Opportunities of Connected Vehicle Safety
4. Information Analysis and Natural Presentation based on Cyber Physical System for Automobiles
5. Scalable Visual Robot Navigation in Changing Environments
6. Reliability of Cyber Physical Systems: Opportunities and Challenges
7. The SIGVerse project: Simulator Platform for Cognitive Social Robotics

Epidemics on interconnected lattices

Abstract: Epidemic remains one of the major threats to human society,which has attracted much attention for decades.Since real-world systems usually depend on each other,epidemics on interconnected networks have been studied ecently.However,in most studies spatial constraints in these interconnected networks are neglected.Here we study the epidemics in a system composed of two interconnected lattices,which is compared with the epidemics in interconnected Erd¨os-R´enyi (ER) networks.Our results show that the epidemic threshold in interconnected lattices decreases with increasing spatial length of interconnected links between networks.When the infection rate is small,the spatial onstraints limit the transmission of the disease,where the infection density is lower in interconnected lattices than in interconnected ER networks.For large infection rate,however,the infection density is higher in interconnected lattices than in nterconnected ER networks.

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

Abstract: In this paper, a fault propagation model (FPM) of mobile ad hoc network (MANET) is proposed based on random walk model. We adopt the random walk model to describe the movement behavior of the nodes in MANET. Based on this model, the influence of the average transmission range, the node's number and the size of the simulation areas on MANET's connectivity is studied. And the comparison of the influence of different causes on the message loss fault in different conditions is given. Finally, according to the state of the nodes and the paths, the position distribution of the congestion nodes and paths is presented. Using the model can distinctly describe the congestion state of the whole network, and the fault data could be directly collected from the FPM, which can make great contributions to MANET's network control and optimization.

Framework design for reliability engineering of complex systems

Abstract: Complex systems are known to show emergent, unexpected failure behaviors due to their inherent interdependency and interaction, including Internet, power grid, transportation systems and even financial systems. These complexities and the corresponding failure behaviors pose a challenge to traditional reliability engineering, since reliability of complex systems could not be comprehensively analyzed by methods such as FTA and FMECA, etc. Complex network theory is an effective and available technique to characterize the complex systems. The study on failure behaviors of complex systems combined with complex network theory will help to overcome the barriers in analyzing, calculating and improving the reliability of complex systems. A framework for the reliability engineering of complex systems is proposed in this paper, which is illustrated by an example of IEEE 14 BUS. The reliability of this typical complex system is calculated, and the vulnerable part of the system has also been identified, which can help us to improve the system reliability in terms of management and future design activities.

From a single network to a network of networks

Abstract: Network science has attracted much attention in recent years due to its interdisciplinary applications. We witnessed the revolution of network science in 1998 and 1999 started with small-world and scale-free networks having now thousands of high-profile publications, and it seems that since 2010 studies of 'network of networks' (NON), sometimes called multilayer networks or multiplex, have attracted more and more attention. The analytic framework for NON yields a novel percolation law for n interdependent networks that shows that percolation theory of single networks studied extensively in physics and mathematics in the last 50 years is a specific limit of the rich and very different general case of n coupled networks. Since then, properties and dynamics of interdependent and interconnected networks have been studied extensively, and scientists are finding many interesting results and discovering many surprising phenomena. Because most natural and engineered systems are composed of multiple subsystems and layers of connectivity, it is important to consider these features in order to improve our understanding of such complex systems. Now the study of NON has become one of the important directions in network science. In this paper, we review recent studies on the new emerging area—NON. Due to the fast growth of this field, there are many definitions of different types of NON, such as interdependent networks, interconnected networks, multilayered networks, multiplex networks and many others. There exist many datasets that can be represented as NON, such as network of different transportation networks including flight networks, railway networks and road networks, network of ecological networks including species interacting networks and food webs, network of biological networks including gene regulation network, metabolic network and protein–protein interacting network, network of social networks and so on. Among them, many interdependent networks including critical infrastructures are embedded in space, introducing spatial constraints. Thus, we also review the progress on study of spatially embedded networks. As a result of spatial constraints, such interdependent networks exhibit extreme vulnerabilities compared with their non-embedded counterparts. Such studies help us to understand, realize and hopefully mitigate the increasing risk in NON.

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

Abstract: For the problem of service dynamic composition in the reliability assessment of SOA architecture software system, this paper propose a reliability assessment method based on complex networks analysis method. Through 3 steps as system modeling, statistics analysis, reliability assessment, gains the system reliability and make it validated by raising an example.

Robustness of networks with topologies of dependency links

Abstract: The robustness of complex networks with dependencies has been studied in recent years. However, previous studies

focused on the robustness of networks composed of dependency links without network topology. In this study, we will analyze the percolation properties of a realistic network model where dependency links follow certain network topology. We perform the theoretical analysis and numerical simulations to show the critical effects of topology of dependency links on robustness of complex networks. For Erdös-Rényi (ER) connectivity network, we find that the system with dependency of RR topology is more vulnerable than system with dependency of ER topology. And RR-RR (i.e. random-regular (RR) network with dependency of RR topology) disintegrates in an abrupt transition. In particular, we find that the system of RR-ER shows different types of phase transitions. For system of different combinations, the type of percolation depends on the interaction between connectivity topology and dependency topology.

Spatial correlation analysis of cascading failures: Congestions and Blackouts

Abstract: Cascading failures have become major threats to network robustness due to their potential catastrophic consequences, where local perturbations can induce global propagation of failures. Unlike failures spreading via direct contacts due to structural interdependencies, overload failures usually propagate through collective interactions among system components. Despite the critical need in developing protection or mitigation strategies in networks such as power grids and transportation, the propagation behavior of cascading failures is essentially unknown. Here we find by analyzing our collected data that jams in city traffic and faults in power grid are spatially long-range correlated with correlations decaying slowly with distance. Moreover, we find in the daily traffic, that the correlation length increases dramatically and reaches maximum, when morning or evening rush hour is approaching. Our study can impact all efforts towards improving actively system resilience ranging from evaluation of design schemes, development of protection strategies to implementation of mitigation programs.

Epidemics in Interconnected Small-World Networks

Abstract: Networks can be used to describe the interconnections among individuals, which play an important role in the spread of disease. Although the small-world effect has been found to have a significant impact on epidemics in single networks, the small-world effect on epidemics in interconnected networks has rarely been considered. Here, we study the susceptible infected-susceptible (SIS) model of epidemic spreading in a system comprising two interconnected small-world networks. We find that the epidemic threshold in such networks decreases when the rewiring probability of the component small-world networks increases. When the infection rate is low, the rewiring probability affects the global steady-state infection density, whereas when the infection rate is high, the infection density is insensitive to the rewiring probability. Moreover, idemics in interconnected small-world networks are found to spread at different velocities that depend on the rewiring probability.

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


Nowadays, networks exist everywhere. In the recent decade, complex networks have been widely investigated partly due to their wide applications in biological neural networks, ecosystems, metabolic pathways, the Internet, the WWW, electrical power grids, communication systems, etc., and partly due to their broad scientific progress in physics, mathematics, engineering, biology, etc. The key character for a complex network is that it can represent a large-scale system in nature, human societies, and technology with the nodes representing the individual agents and the edges representing the mutual connections. Thus, the research work on fundamental properties, such as dynamics, controls, and applications of various complex networks has become overwhelming recently.

Actually, complex network studies can be dated back to the eighteenth century when the great mathematician Leonhard Euler studied the well-known Königsburg seven-bridge problem. Then, in the early 1960s, Erdös and Rényi (ER) proposed a random-graph model, which can be regarded as the modern network theory framework. In order to describe a transition from a regular network to a random network, Watts and Strogatz (WS) rewired the connections on some nodes in a regular network and proposed a small-world network model. Then, Barabási and Albert (BA) proposed a new scale-free network model, in which the degree distribution of the nodes follows a power-law form. Thereafter, complex networks have been widely discussed. In particular, small-world and scale-free complex networks have been extensively investigated worldwide.

The contents of this book are summarized as follows. First, the dynamics of complex networks are studied regarding, for example, the cluster dynamic analysis using kernel spectral methods, community detection algorithms in bipartite networks, epidemiological modeling with demographics and epidemic spreading on multi-layer networks, and resilience of spatial networks leading to the catastrophic cascading failures under various local perturbations. Then, some evolving hyper-network and color-network models are generated by adopting both growth and preferential attachment mechanisms and some new nonlinear chaotic pseudo random number generator, based on tent and logistic maps are also discussed.

Second, the controls of complex networks are investigated. The interesting topics include distributed finite-time cooperative control of multi-agent systems by applying homogeneous-degree and Lyapunov methods, composite finite-time containment control for disturbed second-order multi-agent systems, fractional-order observer design of multi-agent systems, chaos control and anticontrol of complex systems via Parrondos game, collective behavior coordination with predictive mechanisms, convergence, consensus and synchronization of complex networks via contraction theory, and structural controllability of temporal complex networks.

Third, the applications of complex networks provide some applicable carriers, which show the importance of theories developed in complex networks. In particular, a general model for studying time evolution of transition networks, deflection routing in complex networks, recommender systems for social networks analysis and mining, strategy selection in networked evolutionary games, integration and methods in computational biology, are discussed in detail.

Recently, studies of the dynamics and controls of complex networks have become more attractive. In particular, some emergent behaviors of complex networks need to be investigated because new applied science and technology require new methods and theories to solve new challenging problems. Thus, an in-depth study with detailed description of dynamics, controls, and applications of complex networks will benefit both theoretical research and applications in the near-future development of related subjects. This book provides some state-of-the-art research results on broad disciplinary sciences in complex networks to meet such demands.

We would like to express our sincere thanks to all the chapter contributors for their great support to our book, without which this book would not have been possible. Special thanks are directed to the founding editor of the Springer Series in Understanding Complex Systems, Scott Kelso, for his encouragement and support to edit this volume. Thanks also go to Dr. Thomas Ditzinger, Holger Schäpe, and Priyadarshini Senthilkumar from Springer for their assistance during the publication of this book. Last but not least, we also would like to thank the financial support from the National Science and Technology Major Project of China under Grant 2014ZX10004001-014, the 973 Project under Grant 2014CB845302, and the National Natural Science Foundation of China under Grant Nos. 11472290, 61322302, and 61104145, Australian Research Council Discovery under Grants Nos. DP130104765 and DP140100544, and Hong Kong Research Grants Council under the GRF Grants CityU 11201414 and 11208515.

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

Abstract: Operating systems are critical infrastructures for the information systems. Malfunction of certain function component can induce unexpected risks and countless damage for the computing service based on the operating systems. While it is critical for understanding the failure mechanism of operating system, it remains unclear how the function components interact with each other. Here we study these interactions in the kernel of Android OS by modeling the operating system as a complex network. In this network, each node represents a function and links are various call relationship between them. With community analysis, we find three different relations between the topological statistics and the community size. To reveal the organization vulnerability in different scale, we also perform the percolation analysis and identify the critical structures of this software networks. Our findings may help to understand the system complexity and design corresponding software testing methods.

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.