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.     

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.     

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.     

Mixing navigation on networks

In this article, we propose a mixing navigation mechanism, which interpolates between random-walk and shortest-path protocol. The navigation efficiency can be remarkably enhanced via a few routers. Some advanced strategies are also designed: For non-geographical scale-free networks, the targeted strategy with a tiny fraction of routers can guarantee an efficient navigation with low and stable delivery time almost independent of network size. For geographical localized networks, the clustering strategy can simultaneously increase efficiency and reduce the communication cost. The present mixing navigation mechanism is of significance especially for information organization of wireless sensor networks and distributed autonomous robotic systems.     

Effect Attack on Scale-Free Networks due to Cascading Failures

Adopting the initial load of a node j to be Lj = [kj ∑mεГkm）]^α with kj and Fj being the degree of the node j and the set of its neighbouring nodes respectively, we propose a cascading model based on a local preferential redistribution rule of the load after removing a node. Assuming that a failed node leads only to a redistribution of the load passing through it to its neighbouring nodes, we explore the response of scale-free networks subject to two different attack strategies on nodes and find some interesting and counterintuitive results in our cascading model. On the one hand, unexpectedly, tile attack on the nodes with the lowest degree is more harmful than the attack on the highest degree nodes when α〈1/2. On the other hand, when α = 1/2, the effects of two attacks for the robustness against cascading failures are almost identical. In addition, the numerical simulations are also verified by the theoretical analysis. These results may be very helpful for real-life networks to protect the key nodes selected effectively and to avoid cascading-failure-induced disasters.     

Universal power laws in the threshold network model: A theoretical analysis based on extreme value theory

We theoretically and numerically investigated the threshold network model with a generic weight function where there were a large number of nodes and a high threshold. Our analysis was based on extreme value theory, which gave us a theoretical understanding of the distribution of independent and identically distributed random variables within a sufficiently high range. Specifically, the distribution could be generally expressed by a generalized Pareto distribution, which enabled us to formulate the generic weight distribution function. By using the theorem, we obtained the exact expressions of degree distribution and clustering coefficient which behaved as universal power laws within certain ranges of degrees. We also compared the theoretical predictions with numerical results and found that they were extremely consistent.     

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.     

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.     

Walks on Weighted Networks

We investigate the dynamics of random walks on weighted networks. Assuming that the edge weight and the node strength are used as local information by a random walker. Two kinds of walks, weight-dependent walk and strength-dependent walk, are studied. Exact expressions for stationary distribution and average return time are derived and confirmed by computer simulations. The distribution of average return time and the mean-square displacement are calculated for two walks on the Barrat-Barthelemy-Vespignani （BBV） networks. It is found that a weight-dependent walker can arrive at a new territory more easily than a strength-dependent one.     

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.     

Comparison of co-occurrence networks of the Chinese and English languages

Co-occurrence networks of Chinese characters and words, and of English words, are constructed from collections of Chinese and English articles, respectively. Four types of collections are considered, namely, essays, novels, popular science articles, and news reports. Statistical parameters of the networks are studied, including diameter, average degree, degree distribution, clustering coefficient, average shortest path length, as well as the number of connected subnetworks. It is found that the character and word networks of each type of article in the Chinese language, and the word network of each type of article in the English language all exhibit scale-free and small-world features. The statistical parameters of these co-occurrence networks are compared within the same language and across the two languages. This study reveals some commonalities and differences between Chinese and English languages, and among the four types of articles in each language from a complex network perspective. In particular, it is shown that expressions in English are briefer than those in Chinese in a certain sense.     

The complexity of Chinese syntactic dependency networks

This paper proposes how to build a syntactic network based on syntactic theory and presents some statistical properties of Chinese syntactic dependency networks based on two Chinese treebanks with different genres. The results show that the two syntactic networks are small-world networks, and their degree distributions obey a power law. The finding, that the two syntactic networks have the same diameter and different average degrees, path lengths, clustering coefficients and power exponents, can be seen as an indicator that complexity theory can work as a means of stylistic study. The paper links the degree of a vertex with a valency of a word, the small world with the minimized average distance of a language, that reinforces the explanations of the findings from linguistics.     

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.     

Synchronization of Kuramoto oscillators in random complex networks

We study the synchronization of coupled phase oscillators in random complex networks. The topology of the networks is assumed to be vary over time. Here we mainly study the onset of global phase synchronization when the topology switches rapidly over time. We find that the results are, to some extent, different from those in deterministic situations. In particular, the synchronizability of coupled oscillators can be enhanced in ER networks and scale-free networks under fast switching, while in stochastic small-world networks such enhancement is not significant.     

A complex network model based on the Gnutella protocol

Gnutella is one of the basic protocols for P2P software. In this paper, a novel network model based on Gnutella is introduced. The mechanism of this network is based on resource occupancy and search activities of peers. As for the structure, the power-law exponent of in-degree γ_in≈4.2, the length of the average shortest path 〈l〉=57.74, and the diameter of the network is 156; these topological properties of the proposed structure differ from known results.     

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.     

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.     

Role of parties in the vote distribution of proportional elections

We analyze proportional election data to show the influence of parties on the results of this kind of election. The study compiles data from different countries and dates to show that depending on how the candidate’s votes are counted, one can find that these votes have different distributions. When considering the fraction of votes received by the candidates, the vote distribution has a power law behavior with exponent α=1 for all cases studied. However, this universal behavior is modified when we normalize the fraction of votes by the mean number of votes of the candidate’s party. Considering this normalization, the Brazilian and the Finnish results are now different. The former follows an exponential while the latter a log-normal distribution.     

Consensus problem in directed networks of multi-agents via nonlinear protocols

In this Letter, the consensus problem via distributed nonlinear protocols for directed networks is investigated. Its dynamical behaviors are described by ordinary differential equations (ODEs). Based on graph theory, matrix theory and the Lyapunov direct method, some sufficient conditions of nonlinear protocols guaranteeing asymptotical or exponential consensus are presented and rigorously proved. The main contribution of this work is that for nonlinearly coupled networks, we generalize the results for undirected networks to directed networks. Consensus under pinning control technique is also developed here. Simulations are also given to show the validity of the theories.