Percolation on bipartite scale-free networks

Recent studies introduced biased (degree-dependent) edge percolation as a model for failures in real-life systems. In this work, such process is applied to networks consisting of two types of nodes with edges running only between nodes of unlike type. Such bipartite graphs appear in many social networks, for instance in affiliation networks and in sexual-contact networks in which both types of nodes show the scale-free characteristic for the degree distribution. During the depreciation process, an edge between nodes with degrees k and q is retained with a probability proportional to (kq)^−α, where α is positive so that links between hubs are more prone to failure. The removal process is studied analytically by introducing a generating functions theory. We deduce exact self-consistent equations describing the system at a macroscopic level and discuss the percolation transition. Critical exponents are obtained by exploiting the Fortuin-Kasteleyn construction which provides a link between our model and a limit of the Potts model.     

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.     

A packet routing strategy using neural networks on scale-free networks

We propose a dynamic packet routing strategy by using neural networks on scale-free networks. In this strategy, in order to determine the nodes to which the packets should be transmitted, we use path lengths to the destinations of the packets, and adjust the connection weights of the neural networks attached to the nodes from local information and the path lengths. The performances of this strategy on scale-free networks which have the same degree distribution and different degree correlations are compared to one another. Our numerical simulations confirm that this routing strategy is more effective than the shortest path based strategy on scale-free networks with any degree correlations and that the performance of our strategy on assortative scale-free networks is better than that on disassortative and uncorrelated scale-free networks.     

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.     

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.     

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.     

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.     

Dynamics of load entropy during cascading failure propagation in scale-free networks

In this Letter, we introduce the concept of load entropy, which can be an average measure of a network's heterogeneity in the load distribution. Then we investigate the dynamics of load entropy during failure propagation using a new cascading failures load model, which can represent the node removal mechanism in many real-life complex systems. Simulation results show that in the early stage of failure propagation the load entropy for a larger cascading failure increases more sharply than that for a smaller one, and consequently the cascading failure with a larger damage can be identified at the early stage of failure propagation according to the load entropy. Particularly, load entropy can be used as an index to be optimized in cascading failures control and defense in many real-life complex networks.     

A maximum algebraic connectivity increment edge-based strategy for capacity enhancement in scale-free networks

In this paper, we focus on how to improve transportation efficiency of scale-free networks via edge increments. Based on analyzing the correlation between algebraic connectivity, which is the second smallest eigenvalue of the graph Laplacian matrix, and traffic capacity, we propose an effective edge-addition strategy called maximum algebraic connectivity increment edge (MACIE). Existing approaches are based on topological structure parameters, such as path and degree of a network, which require expensive computation. Different from existing edge-addition strategies, MACIE enhances transport efficiency by maximizing algebraic connectivity, and thus has a shorter running time. Simulation results show that MACIE is efficient and performs better than the previous strategy of reduction structural hole (RSH).     

Effects of the cascading failures on scale-free traffic networks

In this paper, we consider the artificial scale-free traffic network with dynamic weights (cost) and focus on how the removal strategies (flow-based removal, betweenness-based removal and mix-based removal) affect the damage of cascading failures based on the user-equilibrium (UE) assignment, which ensures the balance of flow on the traffic network. Experiment simulation shows that different removal strategies can bring large dissimilarities of the efficiency and damage after the intentional removal of an edge. We show that the mix-based removal of a single edge might reduce the damage of cascading failures and delay the breakdown time, especially for larger reserve capacity coefficient α. This is particularly important for real-world networks with a highly hetereogeneous distribution of flow, i.e., traffic and transportation networks, logistics networks and electrical power grids.     

一种应用于含权无标度网络的全局路由算法

针对含权无标度网络提出了一种全局路由算法.该算法利用网络路径上的节点强度信息构建了一种全局路由代价函数,选择使该代价函数最小的路径来传输信息包,有效避开了网络中易发生拥塞的核心节点.实验结果表明,与最短路径算法相比,该算法以较小的平均路径长度的增加为代价,将网络容量提高了十多倍.     

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.     

Comparison of cascading failures in small-world and scale-free networks subject to vertex and edge attacks

Complex networks may undergo a global cascade of overload failures when a single highly loaded vertex or edge is intentionally attacked. Here we use the recent load model of cascading failures to investigate the performance of the small-world (SW) and scale-free (SF) networks subject to deliberate attacks on vertex and edge. Simulation results suggest that compared with the SW network, the SF network is more vulnerable to deliberate vertex attacks and more robust to deliberate edge attacks. In the SF network, deliberate vertex attacks can result in larger cascading failures than deliberate edge attacks; however, in the SW network the situation is opposite. Furthermore, with the increase of the rewiring probability the SW network becomes more and more robust to deliberate vertex and edge attacks.     

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.     

An efficient approach of controlling traffic congestion in scale-free networks

We propose and study a model of traffic in communication networks. The underlying network has a structure that is tunable between a scale-free growing network with preferential attachments and a random growing network. To model realistic situations where different nodes in a network may have different capabilities, the message or packet creation and delivering rates at a node are assumed to depend on the degree of the node. Noting that congestions are more likely to take place at the nodes with high degrees in networks with scale-free character, an efficient approach of selectively enhancing the message-processing capability of a small fraction (e.g. 3%) of the nodes is shown to perform just as good as enhancing the capability of all nodes. The interplay between the creation rate and the delivering rate in determining non-congested or congested traffic in a network is studied more numerically and analytically.     

无标度网络中最大传染能力限定的病毒传播问题研究

传统的病毒传播模型在无限大无标度网络上不存在病毒传播阈值,即无论病毒的传播速率多么低,病毒始终能够在网络中传播.但研究发现,这个结论是在网络中存在超级传染者的假设下得到的,然而许多真实的无标度网络中并不存在超级传染者.因此,文章提出了一个最大传染能力限定的病毒传播模型,并从理论上证明了在最大传染能力限定的无限大无标度网络上,病毒传播阈值是存在的;同时,也分析了最大传染能力限定下非零传播阈值与有限规模网络下非零传播阈值的本质区别,并解释了为什么人们总是认为传统病毒传播模型对许多真实网络病毒感染程度估计过高的 关键词： 无标度网络 最大传染能力 传播阈值 感染程度     

Traffic of packets with non-homogeneously selected destinations in scale-free network

In this paper, we study the information traffic flow in communication networks with scale-free topology. We consider the situation arising when packets are delivered to non-homogeneously selected destinations. It is found that the network capacity R_c increases with the increase of 〈k〉 (average degree of destination nodes) under local routing strategy. In contrast, R_c is essentially independent of 〈k〉 under shortest path strategy. Based on this finding, an integrated routing strategy that can enhance network capacity is proposed by combining the two strategies.     

Effects of consumption strategy on wealth distribution on scale-free networks

We investigate wealth distribution on scale-free networks with different consumption strategies. We indicate that nonlinear consumption function can lead to exponential wealth distribution with a power law tail in accordance with empirical data. In addition, we suggest that anti-degree preference and consumption promotion can make distribution more equal. This provides an effective and practical way to optimize the equality of wealth distribution.     

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.