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.     

Growing networks with preferential deletion and addition of edges

A preferential attachment model for a growing network incorporating the deletion of edges is studied and the expected asymptotic degree distribution is analyzed. At each time step t=1,2,…, with probability π₁>0 a new vertex with one edge attached to it is added to the network and the edge is connected to an existing vertex chosen proportionally to its degree, with probability π₂ a vertex is chosen proportionally to its degree and an edge is added between this vertex and a randomly chosen other vertex, and with probability π₃=1−π₁−π₂<1/2 a vertex is chosen proportionally to its degree and a random edge of this vertex is deleted. The model is intended to capture a situation where high-degree vertices are more dynamic than low-degree vertices in the sense that their connections tend to be changing. A recursion formula is derived for the expected asymptotic fraction p_k of vertices with degree k, and solving this recursion reveals that, for π₃<1/3, we have p_k∼k^{−(3−7π₃)/(1−3π₃)}, while, for π₃>1/3, the fraction p_k decays exponentially at rate (π₁+π₂)/2π₃. There is hence a non-trivial upper bound for how much deletion the network can incorporate without losing the power-law behavior of the degree distribution. The analytical results are supported by simulations.     

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.     

Modeling worldwide highway networks

This Letter addresses the problem of modeling the highway systems of different countries by using complex networks formalism. More specifically, we compare two traditional geographical models with a modified geometrical network model where paths, rather than edges, are incorporated at each step between the origin and the destination vertices. Optimal configurations of parameters are obtained for each model and used for the comparison. The highway networks of Australia, Brazil, India, and Romania are considered and shown to be properly modeled by the modified geographical model.     

Statistical properties of world investment networks

We have performed a detailed investigation on the world investment networks constructed from the Coordinated Portfolio Investment Survey (CPIS) data of the International Monetary Fund, ranging from 2001 to 2006. The distributions of degrees and node strengths are scale-free. The weight distributions can be well modeled by the Weibull distribution. The maximum flow spanning trees of the world investment networks possess two universal allometric scaling relations, independent of time and the investment type. The topological scaling exponent is 1.17±0.02 and the flow scaling exponent is 1.03±0.01.     

Scale-free networks by super-linear preferential attachment rule

A network growth model with geographic limitation of accessible information about the status of existing nodes is investigated. In this model, the probability Π(k) of an existing node of degree k is found to be super-linear with Π(k)∼k^α and α>1 when there are links from new nodes. The numerical results show that the constructed networks have typical power-law degree distributions P(k)∼k^−γ and the exponent γ depends on the constraint level. An analysis of local structural features shows the robust emergence of scale-free network structure in spite of the super-linear preferential attachment rule. This local structural feature is directly associated with the geographical connection constraints which are widely observed in many 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.     

Information traffic in scale-free networks with fluctuations in packet generation rate

We study the information traffic in scale-free networks where the information generation rate varies with time as a periodic function. We observe that when the fluctuation in packet generation rate increases, the average transit time increases and network performance degrades. In order to improve the transportation efficiency in this situation, we propose a new routing method called mixed routing. It operates in two modes: (1) when the packet generation rate is small, the shortest paths are used to deliver the packets to the destination; (2) when the packet generation rate is large, the traffic loads in central nodes are redistributed to other non-central nodes, using the so-called efficient routing method. We find that the time shifting between the two modes is very critical for the routing performance. Consequently, we provide an efficient method to determine the critical times to shift the routing modes for achieving good network performance.     

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.     

A unified model for Sierpinski networks with scale-free scaling and small-world effect

In this paper, we propose an evolving Sierpinski gasket, based on which we establish a model of evolutionary Sierpinski networks (ESNs) that unifies deterministic Sierpinski network [Z.Z. Zhang, S.G. Zhou, T. Zou, L.C. Chen, J.H. Guan, Eur. Phys. J. B 60 (2007) 259] and random Sierpinski network [Z.Z. Zhang, S.G. Zhou, Z. Su, T. Zou, J.H. Guan, Eur. Phys. J. B 65 (2008) 141] to the same framework. We suggest an iterative algorithm generating the ESNs. On the basis of the algorithm, some relevant properties of presented networks are calculated or predicted analytically. Analytical solution shows that the networks under consideration follow a power-law degree distribution, with the distribution exponent continuously tuned in a wide range. The obtained accurate expression of clustering coefficient, together with the prediction of average path length reveals that the ESNs possess small-world effect. All our theoretical results are successfully contrasted by numerical simulations. Moreover, the evolutionary prisoner’s dilemma game is also studied on some limitations of the ESNs, i.e., deterministic Sierpinski network and random Sierpinski network.     

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.     

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.     

Multiple scale analysis of complex networks using the empirical mode decomposition method

Empirical mode decomposition (EMD) method can decompose any complicated data into finite ‘intrinsic mode functions’ (IMFs). In this paper, we use EMD method to analyze and discuss the structural properties of complex networks. A random-walk method is used to collect the data series of network systems. Utilizing the EMD method, we decompose the obtained data into finite IMFs under different spatial scales. The analysis results show that EMD method is an effective tool for capturing the topological properties of network systems under different spatial scales, such as the modular structures of network systems and their energy densities.     

Three-species reaction-diffusion processes on scale-free networks

We study the novel three-species reaction-diffusion processes of scale-free networks that are significantly different from numerical calculations manipulated on regular and small-world lattices. The inverse particle density for the three-species process scales according to the power-law with a scaling exponent α=1.5 for γ>3. It is, however, found from numerical results that the inverse particle density scales in a different way depending on time t when γ<3. In the early time regime, α?1.5, but the inverse particle density increases exponentially over time. We also discuss the possible relationship with the dynamical properties of random walks. In particular, we measure the ratio between the number of inactive and active bonds which shows the segregation of the particles.     

Boltzmann power laws

In this paper we propose a model based on the Boltzmann distribution as a mechanism for generating power laws, Boltzmann Power Laws (BPL). Some of these power laws are studied and compared to popular power laws such as ‘1/f’ noise and self-organized criticality (SOC). We will show how, in some cases, these BPLs reproduce behaviors similar to the finite size scaling (FSS) scenario, which is typical of SOC.     

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.     

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.     

Heterogeneous distribution of metabolites across plant species

We investigate the distribution of flavonoids, a major category of plant secondary metabolites, across species. Flavonoids are known to show high species specificity, and were once considered as chemical markers for understanding adaptive evolution and characterization of living organisms. We investigate the distribution among species using bipartite networks, and find that two heterogeneous distributions are conserved among several families: the power-law distributions of the number of flavonoids in a species and the number of shared species of a particular flavonoid. In order to explain the possible origin of the heterogeneity, we propose a simple model with, essentially, a single parameter. As a result, we show that two respective power-law statistics emerge from simple evolutionary mechanisms based on a multiplicative process. These findings provide insights into the evolution of metabolite diversity and characterization of living organisms that defy genome sequence analysis for different reasons.     

Complex Behaviour for the Origin and Destination Matrix Estimation Problem

The origin and destination （O-D） matrix estimation is an important problem in traffic networks. We apply the gravitation model to express the preference attachment and to analyse the statistical characteristics of the traffic flow in each O-D pair in theory. It is found that the distribution of the future O-D matrix decays as a power law. Additionally, different exponents are obtained for both the constant and variable link cost.     

Sensitivity of Exponents of Three-Power Laws to Hybrid Ratio in Weighted HUHPM

The sensitivity of exponents of three-power laws for node degree, node strength and edged weight to hybrid ratio are studied analytically and numerically in the weighted harmonious unifying hybrid preferential model （HUHPM）, which is extended from an-weighted hybrid preferential attachment model we proposed previously [Chin. Phys. Lett. 22 （2005）719]. Our weighted HUHPMs plus the Barrat-Barthelemy-Vespignani model and the traffic-driven evolution model, respectively, are taken as two typical examples for demonstration and application of the HUHPM.