Incremental routing strategy on scale-free networks

The most important function of a network is for transporting traffic. Due to the low traffic capacity of network systems under the global shortest path routing, plenty of heuristic routing strategies are emerging. In this paper, we propose a heuristic routing strategy called the incremental routing algorithm to improve the traffic capacity of complex networks. We divide the routing process into N$N$(the network size) steps and, at each step, we heuristically calculate all the routes for one source node considering both the dynamic efficient betweenness centrality and node degree information. We do extensive simulations on scale-free networks to confirm the effectiveness of the proposed incremental routing strategy. The simulation results show that the traffic capacity has been enhanced by a substantial factor at the expense of a slight lengthening in the average path.     

Scaling of mean first-passage time as efficiency measure of nodes sending information on scale-free Koch networks

Random walks on complex networks, especially scale-free networks, have attracted considerable interest in the past few years. A lot of previous work showed that the average receiving time (ART), i.e., the average of mean first-passage time (MFPT) for random walks to a given hub node (node with maximum degree) averaged over all starting points in scale-free small-world networks exhibits a sublinear or linear dependence on network order N (number of nodes), which indicates that hub nodes are very efficient in receiving information if one looks upon the random walker as an information messenger. Thus far, the efficiency of a hub node sending information on scale-free small-world networks has not been addressed yet. In this paper, we study random walks on the class of Koch networks with scale-free behavior and small-world effect. We derive some basic properties for random walks on the Koch network family, based on which we calculate analytically the average sending time (AST) defined as the average of MFPTs from a hub node to all other nodes, excluding the hub itself. The obtained closed-form expression displays that in large networks the AST grows with network order as N ln N, which is larger than the linear scaling of ART to the hub from other nodes. On the other hand, we also address the case with the information sender distributed uniformly among the Koch networks, and derive analytically the global mean first-passage time, namely, the average of MFPTs between all couples of nodes, the leading scaling of which is identical to that of AST. From the obtained results, we present that although hub nodes are more efficient for receiving information than other nodes, they display a qualitatively similar speed for sending information as non-hub nodes. Moreover, we show that that AST from a starting point (sender) to all possible targets is not sensitively affected by the sender’s location. The present findings are helpful for better understanding random walks performed on scale-free small-world networks.     

Kinetics of node splitting in evolving complex networks

We introduce a collection of complex networks generated by a combination of preferential attachment and a previously unexamined process of “splitting” nodes of degree k$k$ into k$k$ nodes of degree 1$1$. Four networks are considered, each evolves at each time step by either preferential attachment, with probability p$p$, or splitting with probability 1−p$1-p$. Two methods of attachment are considered; first, attachment of an edge between a newly created node and an existing node in the network, and secondly by attachment of an edge between two existing nodes. Splitting is also considered in two separate ways; first by selecting each node with equal probability and secondly, selecting the node with probability proportional to its degree. Exact solutions for the degree distributions are found and scale-free structure is exhibited in those networks where the candidates for splitting are chosen with uniform probability, those that are chosen preferentially are distributed with a power law with exponential cut-off.     

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.     

一种基于布朗粒子的混合搜索模型

基于网络上的布朗粒子运动基本原理,提出了一种单粒子和多粒子相结合的混合搜索模型.该模型将一次搜索过程分成单粒子搜索与多粒子搜索两个阶段,既克服了单粒子搜索效率低下的缺点,又降低了多粒子搜索的硬件代价.在各种复杂网络拓扑上实施该模型,并与混合导航模型进行比较.结果表明,混合搜索模型的平均搜索时间收敛更快,硬件代价更小.将度大优先的目标选择策略与混合搜索模型相结合,能进一步提高搜索效率.此外通过仿真发现,在无标度网络上混合搜索模型的效率远高于单粒子随机行走,与多粒子随机行走的效率相当,但硬件代价远小于多粒子行走.最后针对该模型给出了一种能有效降低负载的"吸收"策略.     

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.     

度关联无标度网络上的有倾向随机行走

有倾向随机行走是研究网络上数据包路由策略的有效方法. 由于许多真实技术网络包括互联网都具有负的度关联特征, 因此本文研究这种网络上的有倾向随机行走性质. 研究表明: 在负关联网络上粒子可以在连接度较大的节点上均匀分布, 而连接度小的节点上粒子较少; 负关联网络上随机行走的速度比非关联网络更快; 找到了负关联网络上的最佳倾向性系数, 在此情况下负关联网络上随机行走的速度远快于非关联网络. 负关联网络既可以利用度小的节点容纳粒子, 又可以利用度大的节点快速传输, 这是负关联网络上高行走效率产生的机制.     

Epidemic spreading in a scale-free network of regular lattices

The susceptible-infected-susceptible (SIS) epidemics in a scale-free network in which each node is a square lattice itself is investigated through large-scale computer simulations. The model combines a local contact process among individuals in a node (or city) with stochastic long-range infections due to people traveling between cities interconnected by the national transportation scale-free network. A nonzero epidemic threshold is found and it is approached with a power-law behavior by the density of infected individuals, as observed in the small-world network of Watts and Strogatz. Also, the epidemic propagation follows a 1/f$1/f$, hierarchical dynamics from the highly connected square lattices to the smaller degree nodes in outbreaks with sizes distributed accordingly a Gaussian function.     

On the non-equivalence of two standard random walks

We focus on two models of nearest-neighbour random walks on d$d$-dimensional regular hyper-cubic lattices that are usually assumed to be identical—the discrete-time Polya walk, in which the walker steps at each integer moment of time, and the Montroll–Weiss continuous-time random walk in which the time intervals between successive steps are independent, exponentially and identically distributed random variables with mean 1$1$. We show that while for symmetric random walks both models indeed lead to identical behaviour in the long time limit, when there is an external bias they lead to markedly different behaviour.     

Influence of network structure on rumor propagation

Rumor propagation in complex networks is studied analytically and numerically by using the SIR model. Analytically, a mean-field theory is worked out by considering the influence of network topological structure and the unequal footings of neighbors of an infected node in propagating the rumor. It is found that the final infected density of population with degree k   is ρ(k)=1−exp(−αk)$\rho (k)=1-\exp (-\alpha k)$, where α is a parameter related to network structure. The number of the total final infected nodes depends on the network topological structure and will decrease when the structure changes from random to scale-free network. Numerical simulations confirm the theoretical predictions.     

Dirac Spatial Search with Electric Fields

Electric Dirac quantum walks, which are a discretisation of the Dirac equation for a spinor coupled to an electric field, are revisited in order to perform spatial searches. The Coulomb electric field of a point charge is used as a non local oracle to perform a spatial search on a 2D grid of N points. As other quantum walks proposed for spatial search, these walks localise partially on the charge after a finite period of time. However, contrary to other walks, this localisation time scales as N for small values of N and tends asymptotically to a constant for larger Ns, thus offering a speed-up over conventional methods.     

Mechanism of the jamming transition in the two-dimensional traffic networks

The mechanism of the jamming transition in two-dimensional traffic networks is discussed on the basis of several models, where the update rule is deterministic, though the initial car configuration is random. It has turned out that the introduced concept of the occupation probability, which depends upon time and the site, is useful. The fluctuation in the local   car density plays an important role to give rise to small initial clusters of the cars. To examine the growth of such clusters a time-dependent function C$C$ is introduced, which is the number of the neighboring car pairs, and C$C$ increases to a certain maximum value, correlated with the total jamming. The critical car density in the symmetric two-dimensional N×N/N×N$N\times N/N\times N$ system is found to be 0.22–0.23 for each of the east-bound (x)$\left(x\right)$ and the north-bound (y)$\left(y\right)$ cars.     

Mean Hitting Time for Random Walks on a Class of Sparse Networks

For random walks on a complex network, the configuration of a network that provides optimal or suboptimal navigation efficiency is meaningful research. It has been proven that a complete graph has the exact minimal mean hitting time, which grows linearly with the network order. In this paper, we present a class of sparse networks G(t) in view of a graphic operation, which have a similar dynamic process with the complete graph; however, their topological properties are different. We capture that G(t) has a remarkable scale-free nature that exists in most real networks and give the recursive relations of several related matrices for the studied network. According to the connections between random walks and electrical networks, three types of graph invariants are calculated, including regular Kirchhoff index, M-Kirchhoff index and A-Kirchhoff index. We derive the closed-form solutions for the mean hitting time of G(t), and our results show that the dominant scaling of which exhibits the same behavior as that of a complete graph. The result could be considered when designing networks with high navigation efficiency.     

Visibility graph analysis of wind speed records measured in central Argentina

Hourly means of wind speed time series recorded at two wind stations in central Argentina (one inland and the other coastal) are analyzed by means of the visibility graph method. The degree distribution of both series was calculated along with that of their shuffled, Gaussian- and uniform-distributed surrogates. The original series as well as their surrogates show an apparent exponential degree distribution. The v$v$–k$k$ (value–degree) plot of the original wind series indicates that the higher values of the series are not necessarily “hubs” for the series, while that of the surrogates are characterized by a reduced connectivity degree of the higher hubs.     

A Monte Carlo model for networks between professionals and society

We propose a network model with a fixed number of nodes and links and with a dynamic which favors links between nodes differing in connectivity. We observe a phase transition and parameter regimes with degree distributions following power laws, P(k)∼k^-γ$P(k)\sim k^{-\gamma }$, with γ$\gamma$ ranging from 0.2$0.2$ to 0.5$0.5$, small-world properties, with a network diameter following D(N)∼logN$D(N)\sim \log N$ and relative high clustering, following C(N)∼1/N$C(N)\sim 1/N$ and C(k)∼k^-α$C(k)\sim k^{-\alpha }$, with α$\alpha$ close to 3. We compare our results with data from real-world protein interaction networks.     

Mixing search on complex networks

In this article, we derive the first passage time (FPT) distribution and the mean first passage time (MFPT) of random walks from multiple sources on networks. On the basis of analysis and simulation, we find that the MFPT drops substantially when particle number increases at the first stage, and converges to the shortest distance between the sources and the destination when particle number tends to infinite. Given the fact that a Brownian particle from a high-degree node often needs a large number of steps to reach an expected low-degree node, which is the bottleneck for a single random walk, we propose a mixing search model to improve the efficiency of search processes by using random walks from multiple sources to continue the searches from high-degree nodes to destinations. We compare our model with the mixing navigation model proposed by Zhou on complex networks and find that our model converges much faster with lower hardware cost than Zhou’s model. Moreover, simulations on scale-free networks show that the search efficiency of our model is much higher than that of a single random walk, and comparable to that of multiple random walks which have much higher hardware cost than our model. Finally, we discuss the traffic cost of our model, and propose an absorption strategy for our model to recover the additional walkers in networks. Simulations indicate that this strategy reduces the traffic cost of our model effectively.     

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.