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.     

Emergence of scale-free behavior in networks from limited-horizon linking and cost trade-offs

We study network growth from a fixed set of initially isolated nodes placed at random on the surface of a sphere. The growth mechanism we use adds edges to the network depending on strictly local gain and cost criteria. Only nodes that are not too far apart on the sphere may be considered for being joined by an edge. Given two such nodes, the joining occurs only if the gain of doing it surpasses the cost. Our model is based on a multiplicative parameter λ that regulates, in a function of node degrees, the maximum geodesic distance that is allowed between nodes for them to be considered for joining. For n nodes distributed uniformly on the sphere, and for within limits that depend on cost-related parameters, we have found that our growth mechanism gives rise to power-law distributions of node degree that are invariant for constant . We also study connectivity- and distance-related properties of the networks.     

Role of Clustering Coefficient on Cooperation Dynamics in Homogeneous Networks

Based on previous works, we give further investigations on the Prisoners＇ Dilemma Game （PDG） on two different types of homogeneous networks, i.e. the homogeneous small-world network （HSWN） and the regular ring graph. We find that the so-called resonance-like character can occur on both the networks. Different from the viewpoint in previous publications, we think the small-world effect may be unnecessary to produce this character. Therefore, over these two types of networks, we suggest a common understanding in the viewpoint of clustering coefficient. Detailed simulation results can sustain our viewpoint quite well. Furthermore, we investigate the Snowdrift Game （SG） on the same networks. The difference between the outputs of the PDG and the SG can also sustain our viewpoint.     

The emergence of scale-free networks with a seceding mechanism

In order to explore further the underlying mechanism of scale-free networks, we study stochastic secession as a mechanism for the creation of complex networks. In this evolution the network growth incorporates the addition of new nodes, the addition of new links between existing nodes, the deleting and rewiring of some existing links, and the stochastic secession of nodes. To random growing networks with preferential attachment, the model yields scale-free behavior for the degree distribution. Furthermore, we obtain an analytical expression of the power-law degree distribution with scaling exponent γ ranging from 1.1 to 9. The analytical expressions are in good agreement with the numerical simulation results.     

Dynamics-driven evolution to structural heterogeneity in complex networks

The mutual influence of dynamics and structure is a central issue in complex systems. In this paper we study by simulation slow evolution of network under the feedback of a local-majority-rule opinion process. If performance-enhancing local mutations have higher chances of getting integrated into its structure, the system can evolve into a highly heterogeneous small-world with a global hub (whose connectivity is proportional to the network size), strong local connection correlations and power-law-like degree distribution. Networks with better dynamical performance are achieved if structural evolution occurs much slower than the network dynamics. Structural heterogeneity of many biological and social dynamical systems may also be driven by various dynamics-structure coupling mechanisms.     

High-performance distribution of limited resources via a dynamical reallocation scheme

Using the context of routing efficiency in a complex scale-free network, we study the problem of how a limited amount of resources should be distributed to the nodes in a network so as to achieve a better performance, without imposing a certain pre-determined distribution. A dynamical reallocation scheme, based on the willingness of sharing resources with a busy neighboring node, is proposed as a tool for allowing an initially uniform distribution of resource to evolve to a high-performance distribution. The resulting distribution gives a critical packet generation rate R_c that is significantly enhanced when compared with evenly distributing the same amount of resources on the nodes. There emerges a relation between the resource allocated to a node and the degree of the node in the form of . The exponent γ is found to vary with the packet generation rate R. For R<R_c, γ takes on a high value and shows a weak dependence on R; for R>R_c, γ drops with R; and for R?R_c, γ saturates. For good performance, the values of γ indicate a behavior different from that linear in k, as often assumed in previous studies. The resource distribution is also analyzed in terms of the betweenness of the nodes.     

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.     

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.     

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.     

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.     

Attack vulnerability of scale-free networks due to cascading failures

In this paper, adopting the initial load of a node i to be with k_i being the degree of the node i, we propose a cascading model based on a load local redistribution rule and examine cascading failures on the typical network, i.e., the BA network with the scale-free property. We find that the BA scale-free network reaches the strongest robustness level in the case of α=1 and the robustness of the network has a positive correlation with the average degree 〈k〉, where the robustness is quantified by a transition from normal state to collapse. In addition, we further discuss the effects of two different attacks for the robustness against cascading failures on our cascading model and find an interesting result, i.e., the effects of two different attacks, strongly depending to the value α. These results may be very helpful for real-life networks to avoid cascading-failure-induced disasters.     

Naming game on small-world networks with geographical effects

The naming game model characterizes the main evolutionary features of languages or more generally of communication systems. Very recently, the combination of complex networks and the naming game has received much attention and the influences of various topological properties on the corresponding dynamical behavior have been widely studied. In this paper, we investigate the naming game on small-world geographical networks. The small-world geographical networks are constructed by randomly adding links to two-dimensional regular lattices, and it is found that the convergence time is a nonmonotonic function of the geographical distance of randomly added shortcuts. This phenomenon indicates that, although a long geographical distance of the added shortcuts favors consensus achievement, too long a geographical distance of the added shortcuts inhibits the convergence process, making it even slower than the moderates.     

Coevolutionary extremal dynamics on gasket fractal

We considered a Bak-Sneppen model on a Sierpinski gasket fractal. We calculated the avalanche size distribution and the distribution of distances between subsequent minimal sites. To observe the temporal correlations of the avalanche, we estimated the return time distribution, the first-return time, and the all-return time distribution. The avalanche size distribution follows the power law, P(s)∼s−τ, with the exponent τ=1.004(7). The distribution of jumping sites also follows the power law, P(r)∼r−π, with the critical exponent π=4.12(4). We observe the periodic oscillation of the distribution of the jumping distances which originated from the jumps of the level when the minimal site crosses the stage of the fractal. The first-return time distribution shows the power law, Pf(t)∼t−τf, with the critical exponent τf=1.418(7). The all-return time distribution is also characterized by the power law, Pa(t)∼t−τa, with the exponent τa=0.522(4). The exponents of the return time satisfy the scaling relation τf+τa=2 for τf?2.     

Limited ability driven phase transitions in the coevolution process in Axelrod's model

We study the coevolution process in Axelrod's model by taking into account of agents' abilities to access information, which is described by a parameter α to control the geographical range of communication. We observe two kinds of phase transitions in both cultural domains and network fragments, which depend on the parameter α. By simulation, we find that not all rewiring processes pervade the dissemination of culture, that is, a very limited ability to access information constrains the cultural dissemination, while an exceptional ability to access information aids the dissemination of culture. Furthermore, by analyzing the network characteristics at the frozen states, we find that there exists a stage at which the network develops to be a small-world network with community structures.     

Scaling relation for earthquake networks

The scaling relation, 2γ−δ=1, for the exponents of the power-law connectivity distribution, γ, and the power-law eigenvalue distribution of the adjacency matrix, δ, is theoretically predicted to be fulfilled by a locally treelike scale-free network in the “effective medium approximation” (i.e., an analog of the mean field approximation). Here, it is shown that such a relation holds well for the reduced simple earthquake networks (i.e., the network without tadpole-loops and multiple edges) constructed from the seismic data taken from California and Japan. This validates the goodness of the effective medium approximation in the earthquake networks and is consistent with the hierarchical organization of the networks. The present result may be useful for modeling seismicity on complex networks.     

Multi-directed Eulerian growing networks

We introduce and analyze a model of a multi-directed Eulerian network, that is a directed and weighted network where a path exists that passes through all the edges of the network once and only once. Networks of this type can be used to describe information networks such as human language or DNA chains. We are able to calculate the strength and degree distribution in this network and find that they both exhibit a power law with an exponent between 2 and 3. We then analyze the behavior of the accelerated version of the model and find that the strength distribution has a double slope power-law behavior. Finally we introduce a non-Eulerian version of the model and find that the statistical topological properties remain unchanged. Our analytical results are compared with numerical simulations.     

Preferential attachment renders an evolving network of populations robust against crashes

We study a model for the evolution of chemical species under a combination of population dynamics on a short time scale, and a selection mechanism on a longer time scale. Least fit nodes are replaced by new nodes whose links are attached to the nodes of the given network via preferential attachment. In contrast to a random attachment of newly incoming nodes that was used in previous work, this preferential attachment mechanism accelerates the generation of a so-called autocatalytic set after a start from a random geometry, and the growth of this structure, until it saturates in a stationary phase in which the whole system is an autocatalytic set. Moreover, the system in the stationary phase becomes much more stable against crashes in the population size as compared to random attachment. We explain in detail, in terms of graph theoretical notions, which structure of the resulting network is responsible for this stability. Essentially it is a very dense core with many loops and less nodes playing the role of a keystone that prevents the system from crashing, almost completely.     

Sandpile on directed small-world networks

We numerically investigate the avalanche dynamics of the Bak-Tang-Wiesenfeld sandpile model on directed small-world networks. We find that the avalanche size and duration distribution follow a power law for all rewiring probabilities p. Specially, we find that, approaching the thermodynamic limit (L→∞), the values of critical exponents do not depend on p and are consistent with the mean-field solution in Euclidean space for any p>0. In addition, we measure the dynamic exponent in the relation between avalanche size and avalanche duration and find that the values of the dynamic exponents are also consistent with the mean-field values for any p>0.     

Local Events and Dynamics on Weighted Complex Networks

We examine the weighted networks grown and evolved by local events, such as the addition of new vertices and links and we show that depending on frequency of the events, a generalized power-law distribution of strength can emerge. Continuum theory is used to predict the scaling function as well as the exponents, which is in good agreement with the numerical simulation results. Depending on event frequency, power-law distributions of degree and weight can also be expected. Probability saturation phenomena for small strength and degree in many real world networks can be reproduced. Particularly, the non-trivial clustering coefficient, assortativity coefficient and degree-strength correlation in our model are all consistent with empirical evidences.     

The web of connections between tourism companies: Structure and dynamics

Tourism destination networks are amongst the most complex dynamical systems, involving a myriad of human-made and natural resources. In this work we report a complex network-based systematic analysis of the Elba (Italy) tourism destination network, including the characterization of its structure in terms of several traditional measurements, the investigation of its modularity, as well as its comprehensive study in terms of the recently reported superedges approach. In particular, structural (the number of paths of distinct lengths between pairs of nodes, as well as the number of reachable companies) and dynamical features (transition probabilities and the inward/outward activations and accessibilities) are measured and analyzed, leading to a series of important findings related to the interactions between tourism companies. Among the several reported results, it is shown that the type and size of the companies influence strongly their respective activations and accessibilities, while their geographical position does not seem to matter. It is also shown that the Elba tourism network is largely fragmented and heterogeneous, so that it could benefit from increased integration.