Evolution of canalizing Boolean networks

Boolean networks with canalizing functions are used to model gene regulatory networks. In order to learn how such networks may behave under evolutionary forces, we simulate the evolution of a single Boolean network by means of an adaptive walk, which allows us to explore the fitness landscape. Mutations change the connections and the functions of the nodes. Our fitness criterion is the robustness of the dynamical attractors against small perturbations. We find that with this fitness criterion the global maximum is always reached and that there is a huge neutral space of 100% fitness. Furthermore, in spite of having such a high degree of robustness, the evolved networks still share many features with “chaotic” networks.     

Effects of small world topology on the critical boundary for Boolean networks

Due to their complexity, real dynamic systems are widely regarded as operating on the boundary between order and chaos. Therefore it is of great interest to determine analytical expressions for this boundary. For random Boolean networks model, a well known critical value of bias is established as , where K is the mean connectivity. Recent research shows, however, that this expression may need to be modified. In this paper, we shall focus on the effects of topology deviation from the random network assumption since the topologies of many real networks are neither pure random nor fully regular Boolean networks. A modification of the critical boundary condition is given with parameters of the degree distribution in the setting of more realistic networks modeled with small world features.     

Dynamical response to perturbation of critical Boolean networks

Boolean networks can be used as simple but general models for complex self-organizing systems. The freedom to choose different rules and structures of interactions makes this model applicable to a wide variety of complex phenomena. It is known that the damage dynamics in annealed Boolean systems should fall in the same universality class of the directed percolation model. In this work we present results about the behavior of this model at and near the critically ordered condition for both the annealed and the quenched versions of the model. Our study concentrates on the way the system responds to a small perturbation. We show that the characteristic correlation time, i.e., the time in which any memory of this perturbation is lost, diverges as one moves towards criticality. Exactly at the critical point, we observe that the time for returning to the natural state after the perturbation follows a power-law distribution. This indicates that most perturbations are quickly restored, while few events may have a global effect on the system, suggesting a mechanism that assures at the same time robustness and adaptability. The critical exponents obtained are in agreement with the values expected for the universality class of mean-field directed percolation both in the annealed and in the quenched Boolean network model. This gives further evidence that annealed Boolean networks may in certain conditions provide a good model for understanding the behavior of regulatory systems. Our results may give insight into the way real self-organizing systems respond to external stimuli, and why critically ordered systems are often observed in Nature.     

Local affinity in heterogeneous growing networks

In this paper we present a study of the influence of local affinity in heterogeneous preferential attachment (PA) networks. Heterogeneous PA models are a generalization of the Barabási-Albert model to heterogeneous networks, where the affinity between nodes biases the attachment probability of links. Threshold models are a class of heterogeneous PA models where the affinity between nodes is inversely related to the distance between their states. We propose a generalization of threshold models where network nodes have individual affinity functions, which are then combined to yield the affinity of each potential interaction. We analyze the influence of the affinity functions in the topological properties averaged over a network ensemble. The network topology is evaluated through the distributions of connectivity degrees, clustering coefficients and geodesic distances. We show that the relaxation of the criterion of a single global affinity still leads to a reasonable power-law scaling in the connectivity and clustering distributions under a wide spectrum of assumptions. We also show that the richer behavior of the model often exhibits a better agreement with the empirical observations on real networks.     

Imperfect targeted immunization in scale-free networks

Scale-free networks are prone to epidemic spreading. To provide cost-effective protection for such networks, targeted immunization was proposed to selectively immunize the hub nodes. In many real-life applications, however, the targeted immunization may not be perfect, either because some hub nodes are hidden and consequently not immunized, or because the vaccination simply cannot provide perfect protection. We investigate the effects of imperfect targeted immunization in scale-free networks. Analysis and simulation results show that there exists a linear relationship between the inverse of the epidemic threshold and the effectiveness of targeted immunization. Therefore, the probability of epidemic outbreak cannot be significantly lowered unless the protection is reasonably strong. On the other hand, even a relatively weak protection over the hub nodes significantly decreases the number of network nodes ever getting infected and therefore enhances network robustness against virus. We show that the above conclusions remain valid where there exists a negative correlation between nodal degree and infectiousness.     

A model for cascading failures in scale-free networks with a breakdown probability

Considering that not all overload nodes will be removed from networks due to some effective measures to protect them, we propose a new cascading model with a breakdown probability. Adopting the initial load of a node j to be L_j=[k_j(∑_m∈Γjk_m)]^α with k_j and Γ_j being the degree of the node j and the set of its neighboring nodes, respectively, where α is a tunable parameter, we investigate the relationship between some parameters and universal robustness characteristics against cascading failures on scale-free networks. According to a new measure originated from a phase transition from the normal state to collapse, the numerical simulations show that Barabási-Albert (BA) networks reach the strongest robustness level against cascading failures when the tunable parameter α=0.5, while not relating to the breakdown probability. We furthermore explore the effect of the average degree 〈k〉 for network robustness, thus obtaining a positive correlation between 〈k〉 and network robustness. We then analyze the effect of the breakdown probability on the network robustness and confirm by theoretical predictions this universal robustness characteristic observed in simulations. Our work may have practical implications for controlling various cascading-failure-induced disasters in the real world.     

Edge-based-attack induced cascading failures on scale-free networks

Most previous existing works on cascading failures only focused on attacks on nodes rather than on edges. In this paper, we discuss the response of scale-free networks subject to two different attacks on edges during cascading propagation, i.e., edge removal by either the descending or ascending order of the loads. Adopting a cascading model with a breakdown probability p of an overload edge and the initial load (k_ik_j)^α of an edge ij, where k_i and k_j are the degrees of the nodes connected by the edge ij and α is a tunable parameter, we investigate the effects of two attacks for the robustness of Barabási-Albert (BA) scale-free networks against cascading failures. In the case of α<1, our investigation by the numerical simulations leads to a counterintuitive finding that BA scale-free networks are more sensitive to attacks on the edges with the lowest loads than the ones with the highest loads, not relating to the breakdown probability. In addition, the same effect of two attacks in the case of α=1 may be useful in furthering studies on the control and defense of cascading failures in many real-life networks. We then confirm by the theoretical analysis these results observed in simulations.     

Kauffman networks with threshold functions

We investigate Threshold Random Boolean Networks with K = 2 inputs per node, which are equivalent to Kauffman networks, with only part of the canalyzing functions as update functions. According to the simplest consideration these networks should be critical but it turns out that they show a rich variety of behaviors, including periodic and chaotic oscillations. The analytical results are supported by computer simulations.     

Adjacency networks

We consider a finite set S={x₁,…,x_r} and associate to each element x_i a probability p_i. We then form sequences (N-strings) by drawing at random N elements from S with respect to the probabilities assigned to them. Each N-string generates a network where the elements of S are represented as vertices and edges are drawn between adjacent vertices. These structures are multigraphs having multiple edges and loops. We show that the degree distributions of these networks are invariant under permutations of the generating N-strings. We describe then a constructive method to generate scale-free networks and we show how scale-free topologies naturally emerge when the probabilities are Zipf distributed.     

Unified index to quantifying heterogeneity of complex networks

Although recent studies have revealed that degree heterogeneity of a complex network has significant impact on the network performance and function, a unified definition of the heterogeneity of a network with any degree distribution is absent. In this paper, we define a heterogeneity index 0≤H<1 to quantify the degree heterogeneity of any given network. We analytically show the existence of an upper bound of H=0.5 for exponential networks, thus explain why exponential networks are homogeneous. On the other hand, we also analytically show that the heterogeneity index of an infinite power law network is between 1 and 0.5 if and only if its degree exponent is between 2 and 2.5. We further show that for any power law network with a degree exponent greater than 2.5, there always exists an exponential network such that both networks have the same heterogeneity index. This may help to explain why 2.5 is a critical degree exponent for some dynamic behaviors on power law networks.     

Evolution of a population of random Boolean networks

We investigate the evolution of populations of random Boolean networks under selection for robustness of the dynamics with respect to the perturbation of the state of a node. The fitness landscape contains a huge plateau of maximum fitness that spans the entire network space. When selection is so strong that it dominates over drift, the evolutionary process is accompanied by a slow increase in the mean connectivity and a slow decrease in the mean fitness. Populations evolved with higher mutation rates show a higher robustness under mutations. This means that even though all the evolved populations exist close to the plateau of maximum fitness, they end up in different regions of network space.     

Effect of Eliminating Edges on Robustness of Scale-Free Networks under Intentional Attack

We study the robustness of complex networks under edge elimination. We propose three different edge elimination strategies and investigate their effects on the robustness of scale-free networks under intentional attack. We show that deleting a proper fraction of edges connecting hub nodes and hub nodes can enhance the robustness of scale-free networks under intentional attack.     

Network Entropy Based on Topology Configuration and Its Computation to Random Networks

A definition of network entropy is presented, and as an example, the relationship between the value of network entropy of ER network model and the connect probability p as well as the total nodes N is discussed. The theoretical result and the simulation result based on the network entropy of the ER network are in agreement well with each other. The result indicated that different from the other network entropy reported before, the network entropy defined here has an obvious difference from different type of random networks or networks having different total nodes. Thus, this network entropy may portray the characters of complex networks better. It is also pointed out that, with the aid of network entropy defined, the concept of equilibrium networks and the concept of non-equilibrium networks may be introduced, and a quantitative measurement to describe the deviation to equilibrium state of a complex network is carried out.     

Cascading Failures of Complex Networks Based on Two-Step Degree

We propose a new concept, two-step degree. Defining it as the capacity of a node of complex networks, we establish a novel capacity-load model of cascading failures of complex networks where the capacity of nodes decreases during the process of cascading failures. For scale-free networks, we find that the average two-step degree increases with the increase of the heterogeneity of the degree distribution, showing that the average two- step degree can be used for measuring the heterogeneity of the degree distribution of complex networks. In addition, under the condition that the average degree of a node is given, we can design a scale-free network with the optimal robustness to random failures by maximizing the average two-step degree.     

Opinion Dynamics on Complex Networks with Communities

The Ising or Potts models of ferromagnetism have been widely used to describe locally interacting social or economic systems. We consider a related model, introduced by Sznajd to describe the evolution of consensus in the scale-free networks with the tunable strength （noted by Q） of community structure. In the Sznajd model, the opinion or state of any spins can only be changed by the influence of neighbouring pairs of similar connection spins. Such pairs can polarize their neighbours. Using asynchronous updating, it is found that the smaller the community strength Q, the larger the slope of the exponential relaxation time distribution. Then the effect of the initial upspin concentration p as a function of the final all up probability E is investigated by taking different initialization strategies, the random node-chosen initialization strategy has no difference under different community strengths, while the strategies of community node-chosen initialization and hub node-chosen initialization are different in fina/probability under different Q, and the latter one is more effective in reaching final state.     

Prisoner's Dilemma Game on Two Types of Positively Correlated Networks

We study the effects of degree correlations on the evolution of cooperation in the prisoner＇s dilemma game with individuals located on two types of positively correlated networks. It is shown that the positive degree correlation can either promote or inhibit the emergence of cooperation depending on network configurations. Furthermore, we investigate the probability to cooperate as a function of connectivity degree, and find that high-degree individuals generally have a higher tendency to cooperate. Finally, it is found that small-degree individuals usually change their strategy more frequently, and such change is shown to be unfavourable to cooperation for both kinds of networks.     

Cumulative Laws, Team Assembling Mechanisms Determining Network Structure

A number of researching works have shed light on the field of complex networks recently. We investigate a wide range of real-world networks and find several interesting phenomena. Firstly, almost all of these networks evolve by overlapping new small graphs on former networks. Secondly, not only the degree sequence of the mature network follows a power-law distribution, but also the distribution of the cumulative occurrence times during the growing process are revealed to have a heavy tail. Existing network evolving models do not provide interpretation to these phenomena. We suggest a model based on the team assembling mechanism, which is extracted from the growing processes of real-world networks and requires simple parameters, and produces networks exhibiting these properties observed in the present study and in previous works.     

Preservation of network degree distributions from non-uniform failures

There has been a considerable amount of interest in recent years on the robustness of networks to failures. Many previous studies have concentrated on the effects of node and edge removals on the connectivity structure of a static network; the networks are considered to be static in the sense that no compensatory measures are allowed for recovery of the original structure. Real world networks such as the world wide web, however, are not static and experience a considerable amount of turnover, where nodes and edges are both added and deleted. Considering degree-based node removals, we examine the possibility of preserving networks from these types of disruptions. We recover the original degree distribution by allowing the network to react to the attack by introducing new nodes and attaching their edges via specially tailored schemes. We focus particularly on the case of non-uniform failures, a subject that has received little attention in the context of evolving networks. Using a combination of analytical techniques and numerical simulations, we demonstrate how to preserve the exact degree distribution of the studied networks from various forms of attack.     

An empirical study of Chinese language networks

Chinese is spoken by the largest number of people in the world, and it is regarded as one of the most important languages. In this paper, we explore the statistical properties of Chinese language networks (CLNs) within the framework of complex network theory. Based on one of the largest Chinese corpora, i.e. People’s Daily Corpus, we construct two networks (CLN1 and CLN2) from two different respects, with Chinese words as nodes. In CLN1, a link between two nodes exists if they appear next to each other in at least one sentence; in CLN2, a link represents that two nodes appear simultaneously in a sentence. We show that both networks exhibit small-world effect, scale-free structure, hierarchical organization and disassortative mixing. These results indicate that in many topological aspects Chinese language shapes complex networks with organizing principles similar to other previously studied language systems, which shows that different languages may have some common characteristics in their evolution processes. We believe that our research may shed some new light into the Chinese language and find some potentially significant implications.     

Robustness of heterogeneous complex networks

In this paper we study the robustness of heterogeneous preferential attachment networks. The robustness of a network measures its structural tolerance to the random removal of nodes and links. We numerically analyze the influence of the affinity parameters on a set of ensemble-averaged robustness metrics. We show that the presence of heterogeneity does not fundamentally alter the smooth nature of the fragmentation process of the models. We also show that a moderate level of locality translates into slight improvements in the robustness metrics, which prompts us to conjecture an evolutionary argument for the existence of real networks with power-law scaling in their connectivity and clustering distributions.