Sandpile on scale-free networks

We investigate the avalanche dynamics of the Bak-Tang-Wiesenfeld sandpile model on scale-free (SF) networks, where the threshold height of each node is distributed heterogeneously, given as its own degree. We find that the avalanche size distribution follows a power law with an exponent tau. Applying the theory of the multiplicative branching process, we obtain the exponent tau and the dynamic exponent z as a function of the degree exponent gamma of SF networks as tau=gamma divided by (gamma-1) and z=(gamma-1) divided by (gamma-2) in the range 23, with a logarithmic correction at gamma=3. The analytic solution supports our numerical simulation results. We also consider the case of a uniform threshold, finding that the two exponents reduce to the mean-field ones.     

Balls-in-boxes condensation on networks

We discuss two different regimes of condensate formation in zero-range processes on networks: on a q-regular network, where the condensate is formed as a result of a spontaneous symmetry breaking, and on an irregular network, where the symmetry of the partition function is explicitly broken. In the latter case we consider a minimal irregularity of the q-regular network introduced by a single Q node with degree Q>q. The statics and dynamics of the condensation depend on the parameter alpha=ln Q/q, which controls the exponential falloff of the distribution of particles on regular nodes and the typical time scale for melting of the condensate on the Q node, which increases exponentially with the system size N. This behavior is different than that on a q-regular network, where alpha=0 and where the condensation results from the spontaneous symmetry breaking of the partition function, which is invariant under a permutation of particle occupation numbers on the q nodes of the network. In this case the typical time scale for condensate melting is known to increase typically as a power of the system size.     

A new local-world evolving network model

In some real complex networks, only a few nodes can obtain the global information about the entire networks, but most of the nodes own only local connections therefore own only local information of the networks. A new local-world evolving network model is proposed in this paper. In the model, not all the nodes obtain local network information, which is different from the local world network model proposed by Li and Chen (LC model). In the LC model, each node has only the local connections therefore owns only local information about the entire networks. Theoretical analysis and numerical simulation show that adjusting the ratio of the number of nodes obtaining the global information of the network to the total number of nodes can effectively control the valuing range for the power-law exponent of the new network. Therefore, if the topological structure of a complex network, especially its exponent of power-law degree distribution, needs controlling, we just add or take away a few nodes which own the global information of the network.     

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.     

虚拟社区网络的演化过程研究

模拟了虚拟社区网络的演化过程并研究其拓扑结构.发现虚拟社区网络在演化过程中,节点的加入、边的加入、网络中度分布、节点的度与其加入网络时间的关系、平均度随时间的变化等方面与传统的无标度网络有所不符.根据国内某论坛的实际网络数据统计与分析,提出了虚拟社区网络的演化机理——虚拟社区网络构造算法.仿真结果表明,模拟以互联网论坛为代表的虚拟社区网络时,该模型能够得到与真实网络相符的特性. 关键词： 复杂网络 虚拟社区 无标度网络     

Measuring persistence in a stationary time series using the complex network theory

A growing interest exists currently in the analysis of time series by the complex network theory. Here we present a simple and quick way for mapping time series to complex networks. Using a simple rule allows us to transform time series into a textual sequence then we divide it into words with fixed size. Distinct words are nodes of the network, and we have complete control on the network scale by adjusting the word size. Two nodes are linked if their associated words co-occur in sequence. We show that the network topological measures quantify the persistence and the long range correlations in fractional Brownian processes. For a particular word size we assume some relations between the topological measures and the Hurst exponent which characterised the persistence in fractional Brownian processes.     

Partially asymmetric exclusion models with quenched disorder

We consider the one-dimensional partially asymmetric exclusion process with random hopping rates, in which a fraction of particles (or sites) have a preferential jumping direction against the global drift. In this case, the accumulated distance traveled by the particles, x, scales with the time, t, as x approximately t(1/z), with a dynamical exponent z>0. Using extreme value statistics and an asymptotically exact strong disorder renormalization group method, we exactly calculate z(PW) for particlewise disorder, which is argued to be related as z(SW)=z(PW)/2 for sitewise disorder. In the symmetric case with zero mean drift, the particle diffusion is ultraslow, logarithmic in time.     

Hierarchy measures in complex networks

Using each node's degree as a proxy for its importance, the topological hierarchy of a complex network is introduced and quantified. We propose a simple dynamical process used to construct networks which are either maximally or minimally hierarchical. Comparison with these extremal cases as well as with random scale-free networks allows us to better understand hierarchical versus modular features in several real-life complex networks. For random scale-free topologies the extent of topological hierarchy is shown to smoothly decline with gamma, the exponent of a degree distribution, reaching its highest possible value for gamma3.     

Sensitivity of the resilience of congested random networks to rolloff and offset in truncated power-law degree distributions

Random networks were generated with the random configuration model with prescribed truncated power-law degree distributions, parameterized by an exponent, an offset, and an exponential rolloff. As a model of an attack, each network had exactly one of its highest degree nodes removed, with the result that in some cases, one or more remaining nodes became congested with the reassignment of the load. The congested nodes were then removed, and the “cascade failure” process continued until all nodes were uncongested. The ratio of the number of nodes of the largest remaining cluster to the number of nodes in the original network was taken to be a measure of the network's resiliency to highest-degree node removal. We found that the resiliency is sensitive to both rolloff and offset (but not to cutoff) in the degree distribution, and that rolloff tends to decrease resiliency while offset tends to increase it.     

Impact of degree heterogeneity on the behavior of trapping in Koch networks

Previous work shows that the mean first-passage time (MFPT) for random walks to a given hub node (node with maximum degree) in uncorrelated random scale-free networks is closely related to the exponent γ of power-law degree distribution P(k) ～ k(-γ), which describes the extent of heterogeneity of scale-free network structure. However, extensive empirical research indicates that real networked systems also display ubiquitous degree correlations. In this paper, we address the trapping issue on the Koch networks, which is a special random walk with one trap fixed at a hub node. The Koch networks are power-law with the characteristic exponent γ in the range between 2 and 3, they are either assortative or disassortative. We calculate exactly the MFPT that is the average of first-passage time from all other nodes to the trap. The obtained explicit solution shows that in large networks the MFPT varies lineally with node number N, which is obviously independent of γ and is sharp contrast to the scaling behavior of MFPT observed for uncorrelated random scale-free networks, where γ influences qualitatively the MFPT of trapping problem.     

Research on the search ability of Brownian particles on networks with an adaptive mechanism

In this paper, we focus on the search ability of Brownian particles with an adaptive mechanism. In the adaptive mechanism, nodes are allowed to be able to change their own accepting probability according to their congestion states. Two searching-traffic models, the static one in which nodes have fixed accepting probability to the incoming particles and the adaptive one in which nodes have adaptive accepting probability to the incoming particles are presented for testing the adaptive mechanism. Instead of number of hops, we use the traveling time, which includes not only the number of hops for a particle to jump from the source node to the destination but also the time that the particle stays in the queues of nodes, to evaluate the search ability of Brownian particles. We apply two models to different networks. The experiment results show that the adaptive mechanism can decrease the network congestion and the traveling time of the first arriving particle. Furthermore, we investigate the influence of network topologies on the congestion of networks by addressing several main properties: degree distribution, average path length, and clustering coefficient. We show the reason why random topologies are more able to deal with congested traffic states than others. We also propose an absorption strategy to deal with the additional Brownian particles in networks. The experiment results on Barabási–Albert (BA) scale-free networks show that the absorption strategy can increase the probability of a successful search and decrease the average per-node particles overhead for our models.     

Robustness of a network of networks

Network research has been focused on studying the properties of a single isolated network, which rarely exists. We develop a general analytical framework for studying percolation of n interdependent networks. We illustrate our analytical solutions for three examples: (i) For any tree of n fully dependent Erd?s-Rényi (ER) networks, each of average degree k, we find that the giant component is P∞ =p[1-exp(-kP∞)](n) where 1-p is the initial fraction of removed nodes. This general result coincides for n = 1 with the known second-order phase transition for a single network. For any n>1 cascading failures occur and the percolation becomes an abrupt first-order transition. (ii) For a starlike network of n partially interdependent ER networks, P∞ depends also on the topology-in contrast to case (i). (iii) For a looplike network formed by n partially dependent ER networks, P∞ is independent of n.     

Deterministic scale-free small-world networks of arbitrary order

In many real-life networks, both the scale-free distribution of degree and small-world behavior are important features. There are many random or deterministic models of networks to simulate these features separately. However, there are few models that combine the scale-free effect and small-world behavior, especially in terms of deterministic versions. What is more, all the existing deterministic algorithms running in the iterative mode generate networks with only several discrete numbers of nodes. This contradicts the purpose of creating a deterministic network model on which we can simulate some dynamical processes as widely as possible. According to these facts, this paper proposes a deterministic network generation algorithm, which can not only generate deterministic networks following a scale-free distribution of degree and small-world behavior, but also produce networks with arbitrary number of nodes. Our scheme is based on a complete binary tree, and each newly generated leaf node is further linked to its full brother and one of its direct ancestors. Analytical computation and simulation results show that the average degree of such a proposed network is less than 5, the average clustering coefficient is high (larger than 0.5, even for a network of size 2 million) and the average shortest path length increases much more slowly than logarithmic growth for the majority of small-world network models.     

Accelerating networks: Effects of preferential connections

Networks are commonly observed structures in complex systems with interacting and interdependent parts that self-organize. For nonlinearly growing networks, when the total number of connections increases faster than the total number of nodes, the network is said to accelerate. We propose a systematic model for the dynamics of growing networks represented by distribution kinetics equations. We define the nodal-linkage distribution, construct a population dynamics equation based on the association-dissociation process, and perform the moment calculations to describe the dynamics of such networks. For nondirectional networks with finite numbers of nodes and connections, the moments are the total number of nodes, the total number of connections, and the degree (the average number of connections per node), represented by the average moment. Size independent rate coefficients yield an exponential network describing the network without preferential attachment, and size dependent rate coefficients produce a power law network with preferential attachment. The model quantitatively describes accelerating network growth data for a supercomputer (Earth Simulator), for regulatory gene networks, and for the Internet.     

Iterative decomposition of Barabasi-Albert scale-free networks

We study a decomposition process where all nodes with a targeted degree are removed from the network. Each removal step results in changes in the degrees of the remaining nodes, and other nodes may attain the targeted degree. The processes continue iteratively until no more nodes with the targeted degree are present in the decomposed network. The network model used in our study is the well known Barabasi-Albert network, that is built with an iterative growth based on preferential attachment. Our results show an exponential decay of the number of nodes removed at each step. The total number of nodes removed in the whole process depends on the targeted degree and decay with a power law controlled by the same exponent as the degree distribution of the network.     

相依网络上基于相连边的择优恢复算法

如何有效地应对和控制故障在相依网络上的级联扩散避免系统发生结构性破碎,对于相依网络抗毁性研究具有十分重要的理论价值和现实意义.最新的研究提出一种基于相依网络的恢复模型,该模型的基本思想是通过定义共同边界节点,在每轮恢复阶段找出符合条件的共同边界节点并以一定比例实施恢复.当前的做法是按照随机概率进行选择.这种方法虽然简单直观,却没有考虑现实世界中资源成本的有限性和择优恢复的必然性.为此,针对相依网络的恢复模型,本文利用共同边界节点在极大连通网络内外的连接边数计算边界节点的重要性,提出一种基于相连边的择优恢复算法(preferential recovery based on connectivity link,PRCL)算法.利用渗流理论的随机故障模型,通过ER随机网络和无标度网络构建的不同结构相依网络上的级联仿真结果表明,相比随机方法和度数优先以及局域影响力优先的恢复算法,PRCL算法具备恢复能力强、起效时间早且迭代步数少的优势,能够更有效、更及时地遏制故障在网络间的级联扩散,极大地提高了相依网络遭受随机故障时的恢复能力.     

Evolving pseudofractal networks

We present a family of scale-free network model consisting of cliques, which is established by a simple recursive algorithm. We investigate the networks both analytically and numerically. The obtained analytical solutions show that the networks follow a power-law degree distribution, with degree exponent continuously tuned between 2 and 3. The exact expression of clustering coefficient is also provided for the networks. Furthermore, the investigation of the average path length reveals that the networks possess small-world feature. Interestingly, we find that a special case of our model can be mapped into the Yule process.     

Limited path percolation in complex networks

We study the stability of network communication after removal of a fraction q=1-p of links under the assumption that communication is effective only if the shortest path between nodes i and j after removal is shorter than al(ij)(a> or =1) where l(ij) is the shortest path before removal. For a large class of networks, we find analytically and numerically a new percolation transition at p(c)=(kappa(0)-1)((1-a)/a), where kappa(0) [triple bond] / and k is the node degree. Above p(c), order N nodes can communicate within the limited path length al(ij), while below p(c), N(delta) (delta<1) nodes can communicate. We expect our results to influence network design, routing algorithms, and immunization strategies, where short paths are most relevant.     

中国城市航空网络的实证研究与分析

以城市为节点，城市间直航线路为边，实证地研究了中国城市航空网络的拓扑性质.研究表明，中国城市航空网络是一个小世界网络，具有短的平均路径长度和大的簇系数，且其度分布服从双段幂律分布.它的度度相关性质与世界航空网络和北美航空网络都不相同.当度较小时，世界航空网络和北美航空网络都是正相关的，但中国城市航空网络未表现出度度相关性；而对于度较大的节点，世界航空网络中其邻点平均度几乎是一个常值，但中国城市航空网络却呈现出负相关性.以往的实证研究暗示，节点具有明确几何位置的网络，如计算机互联网、电力网络等，不表现层次性.但是中国城市航空网络展现出明显的层次性，表明地理因素对其结构演化的影响并不强烈.进一步地，以城市间直航计划每周提供的座位数为边权，研究了网络的含权性质，发现该网络节点度权之间是幂律相关的，相关指数为1.37.     

On the construction of complex networks with optimal Tsallis entropy

In this work, we first formulate the Tsallis entropy in the context of complex networks. We then propose a network construction whose topology maximizes the Tsallis entropy. The growing network model has two main ingredients: copy process and random attachment mechanism (C-R model). We show that the resulting degree distribution exactly agrees with the required degree distribution that maximizes the Tsallis entropy. We also provide another example of network model using a combination of preferential and random attachment mechanisms (P-R model) and compare it with the distribution of the Tsallis entropy. In this case, we show that by adequately identifying the exponent factor q, the degree distribution can also be written in the q-exponential form. Taken together, our findings suggest that both mechanisms, copy process and preferential attachment, play a key role for the realization of networks with maximum Tsallis entropy. Finally, we discuss the interpretation of q parameter of the Tsallis entropy in the context of complex networks.