Effective usage of shortest paths promotes transportation efficiency on scale-free networks

With rapid economic and social development, the problem of traffic congestion is getting more and more serious. Accordingly, network traffic models have attracted extensive attention. In this paper, we introduce a shortest-remaining-path-first queuing strategy into a network traffic model on Barabási–Albert scale-free networks under efficient routing protocol, where one packet’s delivery priority is related to its current distance to the destination. Compared with the traditional first-in-first-out queuing strategy, although the network capacity has no evident changes, some other indexes reflecting transportation efficiency are significantly improved in the congestion state. Extensive simulation results and discussions are carried out to explain the phenomena. Our work may be helpful for the designing of optimal networked-traffic systems.     

Correlations and clustering in a scale-free network in Euclidean space

Empirical study shows that many real networks in nature and society share two generic properties: they are scale-free and they display a high degree of clustering. Quite often they are modular in nature also, implying occurrences of several small tightly linked groups which are connected in a hierarchical manner among themselves. Recently, we have introduced a model of spatial scale-free network where nodes pop-up at randomly located positions in the Euclidean space and are connected to one end of the nearest link of the existing network. It has been already argued that the large scale behaviour of this network is like the Barabási-Albert model. In the present paper we briefly review these results as well as present additional results on the study of non-trivial correlations present in this model which are found to have similar behaviours as in the real-world networks. Moreover, this model naturally possesses the hierarchical characteristics lacked by most of the models of the scale-free networks.      

Traffic dynamics in scale-free networks with tunable strength of community structure

In this paper we systematically investigate the impact of community structure on traffic dynamics in scale-free networks based on local routing strategy. A growth model is introduced to construct scale-free networks with tunable strength of community structure, and a packet routing strategy with a parameter α is used to deal with the navigation and transportation of packets simultaneously. Simulations show that the maximal network capacity stands at α=−1 in the case of identical vertex capacity and monotonously decreases with the strength of community structure which suggests that the networks with fuzzy community structure (i.e., community strength is weak) are more efficient in delivering packets than those with pronounced community structure. To explain these results, the distribution of packets of each vertex is carefully studied. Our results indicate that the moderate strength of community structure is more convenient for the information transfer of real complex systems.     

Routing in scale-free networks based on expanding betweenness centrality

In this paper, an improved routing strategy is proposed for enhancing the traffic capacity of scale-free networks. Instead of using the information of degree and betweenness centrality, the new algorithm is derived on the basis of the expanding betweenness centrality of nodes, which gives an estimate of the traffic handled by the vertex for a certain route set. Since the nodes with large betweenness centrality are more susceptible to traffic congestion, the traffic can be improved by redistributing traffic loads from nodes with large betweenness centrality to nodes with small betweenness centrality in the process of computing the collective routing table. Comparing with results of previous routing strategies, it is shown that the present improved routing performs more effectively.     

面向成本-收益好的无标度耦合网络构建方法

较大平均路径长度的网络会带来较大的网络延迟, 难以支持时间敏感业务与应用. 通过增加连接可以降低源和目的节点之间的跳数, 进而降低网络平均延迟, 使得更加快速地传播信息, 但是增加连接的同时也增加了网络构建成本. 分层网络是研究网络耦合的一个有效方法, 但目前网络构建过程中将每层网络分别处理并认为每层网络之间没有强相关性. 本文提出了一种面向成本-收益的无标度网络动态构建方法. 此方法将网络分为多层, 基于连续论在高层网络中添加连接, 使得网络演化为无标度网络. 此连续过程包括节点度增加过程和局部网络半径增长两个连续过程, 在增加连接的过程中引入表征网络构建成本和收益的成本-收益指标. 模拟结果表明引入成本-收益指标的无标度耦合网络构建方法能够在合理范围内有效降低网络平均路径长度, 提升网络性能, 并且本文给出了耦合网络的动态业务性能, 通过调整高层网络避免网络拥塞.     

Monomer-dimer model on a scale-free small-world network

The explicit determination of the number of monomer-dimer arrangements on a network is a theoretical challenge, and exact solutions to monomer-dimer problem are available only for few limiting graphs with a single monomer on the boundary, e.g., rectangular lattice and quartic lattice; however, analytical research (even numerical result) for monomer-dimer problem on scale-free small-world networks is still missing despite the fact that a vast variety of real systems display simultaneously scale-free and small-world structures. In this paper, we address the monomer-dimer problem defined on a scale-free small-world network and obtain the exact formula for the number of all possible monomer-dimer arrangements on the network, based on which we also determine the asymptotic growth constant of the number of monomer-dimer arrangements in the network. We show that the obtained asymptotic growth constant is much less than its counterparts corresponding to two-dimensional lattice and Sierpinski fractal having the same average degree as the studied network, which indicates from another aspect that scale-free networks have a fundamentally distinct architecture as opposed to regular lattices and fractals without power-law behavior.     

Emergency response to disaster-struck scale-free network with redundant systems

Disasters cause tremendous damage every year. In this paper, we have specifically studied emergency response to disaster-struck scale-free networks when some nodes in the network have redundant systems. If one node collapses, its redundant system will substitute it to work for a period of time. In the first part, according to the network structure, several redundant strategies have been formulated, and then our studies focused on their effectiveness by means of simulation. Results show that the strategy based on total degrees is the most effective one. However, many nodes still collapse in the end if redundant systems do not have sufficient capability, so emergency responses are necessary. Several emergent strategies controlling the distribution of external resources have been proposed in the second part. The effectiveness of those emergent strategies are then studied from three aspects, such as the effect of strategies on spreading processes, minimum sufficient quantities of external resources and determination of the most appropriate emergent strategy. In addition, the effects of redundant intensity on these aspects have been discussed as well.     

考虑网络流量的无标度网络病毒免疫策略研究

考虑网络交通流量对病毒传播行为的影响,基于平均场理论研究无标度网络上的病毒免疫策略,提出一种改进的熟人免疫机理.理论分析表明,在考虑网络交通流量影响的情况下,当免疫节点密度较小时,随机免疫几乎不能降低病毒的传播速率,而对网络实施目标免疫则能够有效抑制病毒的传播,并且选择度最大的节点进行免疫与选择介数最大的节点进行免疫的效果基本相同.研究还发现,对于网络全局信息未知的情况,与经典熟人免疫策略相比,所提出的免疫策略能够获得更好的免疫效果.通过数值仿真对理论分析进行了验证. 关键词： 无标度网络 病毒传播 交通流量 免疫策略     

A scale-free network with limiting on vertices

We propose and analyze a random graph model which explains a phenomena in the economic company network in which company may not expand its business at some time due to the limiting of money and capacity. The random graph process is defined as follows: at any time-step t, (i) with probability α(k) and independently of other time-step, each vertex is inactive which means it cannot be connected by more edges, where k is the degree of v_i at the time-step t; (ii) a new vertex v_t is added along with m edges incident with v_t at one time and its neighbors are chosen in the manner of preferential attachment. We prove that the degree distribution P(k) of this random graph process satisfies if α(⋅) is a constant α₀; and P(k)∝C₂k⁻³ if α(?)↓0 as ?↑∞, where C₁,C₂ are two positive constants. The analytical result is found to be in good agreement with that obtained by numerical simulations. Furthermore, we get the degree distributions in this model with m-varying functions by simulation.     

A stochastic SIR epidemic on scale-free network with community structure

The scale-free degree distribution and community structure are two significant properties shared by numerous complex networks. In this paper, we investigate the impact of these properties on a stochastic SIR epidemic which incorporates the stochastic nature of epidemic spreading. A two-type branching process is employed to approximate the early stage of epidemic spreading. The basic reproduction number _R0$R_0$ is obtained. And the influences of scale-free property and community structure on _R0$R_0$ are analyzed by numerical simulations.     

Routing strategies in traffic network and phase transition in network traffic flow

The dynamics of information traffic over scale-free networks has been investigated systematically. A series of routing strategies of data packets have been proposed, including the local routing strategy, the next-nearest-neighbour routing strategy, and the mixed routing strategy based on local static and dynamic information. The capacity of the network can be quantified by the phase transition from free flow state to congestion state. The optimal parameter values of each model leading to the highest efficiency of scale-free networked traffic systems have been found. Moreover, we have found hysteretic loop in networked traffic systems with finite packets delivering ability. Such hysteretic loop indicates the existence of the bi-stable state in the traffic dynamics over scale-free networks.      

Optimization of transport protocols in complex networks

In this paper, an optimal routing strategy is proposed to enhance the traffic capacity of complex networks. In order to avoid nodes overloading, the new algorithm is derived on the basis of generalized betweenness centrality which gives an estimate of traffic handled by the node for a route set. Since the nodes with large betweenness centrality are more susceptible to traffic congestion, the traffic can be improved, as our strategy, by redistributing traffic load from nodes with large betweenness centrality to nodes with small betweenness centrality in the proceeding of computing collective routing table. Particularly, depending on a parameter that controls the optimization scale, the new routing can not only enlarge traffic capacity of networks more, but also enhance traffic efficiency with smaller average path length. Comparing results of previous routing strategies, it is shown that the present improved routing performs more effectively.     

Stochastic resonance in hybrid scale-free neuronal networks

We study the phenomenon of stochastic resonance in a system of coupled neurons that are globally excited by a weak periodic input signal. We make the realistic assumption that the chemical and electrical synapses interact in the same neuronal network, hence constituting a hybrid network. By considering a hybrid coupling scheme embedded in the scale-free topology, we show that the electrical synapses are more efficient than chemical synapses in promoting the best correlation between the weak input signal and the response of the system. We also demonstrate that the average degree of neurons within the hybrid scale-free network significantly influences the optimal amount of noise for the occurrence of stochastic resonance, indicating that there also exists an optimal topology for the amplification of the response to the weak input signal. Lastly, we verify that the presented results are robust to variations of the system size.     

The effect of TTL on the information traffic

In real communication protocols, the information packets have a finite Time-to-Live (TTL) to avoid the waste of network resources, such as infinite loop induced by routing error or too long transferring time. In this paper, we introduce TTL into the information traffic model on Barabási-Albert scale-free networks under local routing strategy and focus on its effect on the network capacity measured by the critical point (R_c) of phase transition from free flow to congestion. Simulations show that the network capacity and the communication velocity are improved. However, some packets are dropped before they arrived at destinations. It is found that the share of successfully arrived packets monotonously increases with the increment of TTL and it is considerably acceptable if TTL is not very small. We also examine the effect of TTL on the positive-feedback preference (PFP) internet model and the results are alike. Our work may be helpful in quantifying the effect of packet lifetime in real communication networks and in routing strategy designing.     

On structural properties of scale-free networks with finite size

Since many large real networks tend to present scale-free degree distribution, this paper investigates the structural properties of scale-free networks with finite size. Beginning with a comprehensive analysis of the degree distribution consisting of the concentration trend, dispersion and inequality, this paper then focuses on the discussion of heterogeneity and hub nodes of scale-free networks. The findings will help to improve our understanding of the structure and function of real networks.     

Integrating network structure and dynamic information for better routing strategy on scale-free networks

We study information packet routing processes on scale-free networks by mimicking the Internet traffic delivery strategies. We incorporate both the global network structure information and local queuing information in the dynamic processes. We propose several new routing strategies to guide the packet routing. The performance of the routing strategies is measured by the average transit time of the packets as well as their dependence on the traffic amount. We find that the routing strategies which integrate both global network structure information and local dynamic information perform much better than the traditional shortest-path routing protocol which takes into account only the global topological information. Moreover, from comparative studies of these routing strategies, we observe that some of our proposed methods can decrease the average transit time of packets but the performance is closely dependent on the total amount of traffic while some other proposed methods can have good performance independent of the total amount of traffic with hyper-excellent average transit time of packets. Also, numerical results show that our proposed methods integrating network structure information and local dynamic information can work much better than the methods recently proposed in [S. Sreenivasan, R. Cohen, E. López, Z. Toroczkai, H.E. Stanley, Phys. Rev. E 75 (2007) 036105, Zhi-Xi Wu, Gang Peng, Eric W.M. Wong, Kai-Hau Yeung, J. Stat. Mech. (2008) P11002.], which only considered network structure information.     

Load balanced diffusive capture process on homophilic scale-free networks

Diffusive capture processes are known to be an effective method for information search on complex networks. The biased N$N$ lions–lamb model provides quick search time by attracting random walkers to high degree nodes, where most capture events take place. The price of the efficiency is extreme traffic concentration on top hubs. We propose traffic load balancing provided by type specific biased random walks. For that we introduce a multi-type scale-free graph generation model, which embeds homophily structure into the network by utilizing type dependent random walks. We show analytically and with simulations that by augmenting the biased random walk method with a simple type homophily rule, we can alleviate the traffic concentration on high degree nodes by spreading the load proportionally between hubs with different types of our generated multi-type scale-free topologies.     

Complex scale-free networks with tunable power-law exponent and clustering

We introduce a network evolution process motivated by the network of citations in the scientific literature. In each iteration of the process a node is born and directed links are created from the new node to a set of target nodes already in the network. This set includes m$m$ “ambassador” nodes and l$l$ of each ambassador’s descendants where m$m$ and l$l$ are random variables selected from any choice of distributions _pl$p_l$ and _qm$q_m$. The process mimics the tendency of authors to cite varying numbers of papers included in the bibliographies of the other papers they cite. We show that the degree distributions of the networks generated after a large number of iterations are scale-free and derive an expression for the power-law exponent. In a particular case of the model where the number of ambassadors is always the constant m$m$ and the number of selected descendants from each ambassador is the constant l$l$, the power-law exponent is (2l+1)/l$(2l+1)/l$. For this example we derive expressions for the degree distribution and clustering coefficient in terms of l$l$ and m$m$. We conclude that the proposed model can be tuned to have the same power law exponent and clustering coefficient of a broad range of the scale-free distributions that have been studied empirically.     

The impact of connection density on scale-free distribution in random networks

Preferential attachment is considered as a fundamental mechanism that contributes to the scale-free characteristics of random networks, which include growth and non-growth networks. There exist some situations of non-growth random networks, particularly for very sparse or dense networks, where preferential attachments cannot consequentially result in true scale-free features, but only in scale-free-like appearances. This phenomenon implies that, a close relationship exists between the connection density p$p$ and the scaling. In this study, we propose a self-organized model with constant network size to study the phenomenon. We show analytically and numerically that there exists a certain critical point _pc$p_c$. Only when p=_pc$p=p_c$, the random network evolves into steady scale-free state. Otherwise, the network exhibits a steady scale-free-like state. The closer the p$p$ approximates _pc$p_c$, the closer the scale-free-like distribution approximates the true scale-free distribution. Our results show that, in random network lack of growth, a preferential scheme does not necessarily lead to a scale-free state, and a formation of scale-free is a consequence of two mechanisms: (i) a preferential scheme and (ii) appropriate connection density.     

Bandwidth allocation strategy for traffic systems of scale-free network

In this Letter, the bandwidth resource allocation strategy is considered for traffic systems of complex networks. With a finite resource of bandwidth, an allocation strategy with preference parameter α is proposed considering the links importance. The performance of bandwidth allocation strategy is studied for the local routing protocol and the shortest path protocol. When important links are slightly favored in the bandwidth allocation, the system can achieve the optimal traffic performance for the two routing protocols. For the shortest path protocol, we also give a method to estimate the network traffic capacity theoretically.