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.     

First passage time of multiple Brownian particles on networks with applications

In this article, we study some theoretical and technological problems with relation to multiple Brownian particles on networks. We are especially interested in the behavior of the first arriving Brownian particle when all the Brownian particles start out from the source s simultaneously and head to the destination h randomly. We analyze the first passage time (FPT) Y_sh(z) and the mean first passage time (MFPT) 〈Y_sh(z)〉 of multiple Brownian particles on complex networks. Equations of Y_sh(z) and 〈Y_sh(z)〉 are obtained. On a variety of commonly encountered networks, we observe first passage properties of multiple Brownian particles from different aspects. We find that 〈Y_sh(z)〉 drops substantially when particle number z increases at the first stage, and converges to d_sh, the distance between the source and the destination when z→∞. The distribution of FPT Prob{Y_sh(z)=t},t=0,1,2,… is also analyzed in these networks. The distribution curve peaks up towards t=d_sh when z increases. Consequently, if particle number z is set appropriately large, the first arriving Brownian particle will go along the shortest or near shortest paths between the source and the destination with high probability. Simulations confirm our analysis. Based on theoretical studies, we also investigate some practical problems using multiple Brownian particles, such as communication on P2P networks, optimal routing in small world networks, phenomenon of asymmetry in scale-free networks, information spreading in social networks, pervasion of viruses on the Internet, and so on. Our analytic and experimental results on multiple Brownian particles provide useful evidence for further understanding and properly tackling these problems.     

Adaptive local routing strategy on a scale-free network

Due to the heterogeneity of the structure on a scale-free network, making the betweennesses of all nodes become homogeneous by reassigning the weights of nodes or edges is very difficult. In order to take advantage of the important effect of high degree nodes on the shortest path communication and preferentially deliver packets by them to increase the probability to destination, an adaptive local routing strategy on a scale-free network is proposed, in which the node adjusts the forwarding probability with the dynamical traffic load (packet queue length) and the degree distribution of neighbouring nodes. The critical queue length of a node is set to be proportional to its degree, and the node with high degree has a larger critical queue length to store and forward more packets. When the queue length of a high degree node is shorter than its critical queue length, it has a higher probability to forward packets. After higher degree nodes are saturated (whose queue lengths are longer than their critical queue lengths), more packets will be delivered by the lower degree nodes around them. The adaptive local routing strategy increases the probability of a packet finding its destination quickly, and improves the transmission capacity on the scale-free network by reducing routing hops. The simulation results show that the transmission capacity of the adaptive local routing strategy is larger than that of three previous local routing strategies.     

Reducing congestion on complex networks by dynamic relaxation processes

We study the effects of relaxational dynamics on the congestion pressure in general transport networks. We show that the congestion pressure is reduced in scale-free networks if a relaxation mechanism is utilized, while this is in general not the case for non-scale-free graphs such as random graphs. We also present evidence supporting the idea that the emergence of scale-free networks arise from optimization mechanisms to balance the load of the networks nodes.     

Complete condensation in a zero range process on scale-free networks

We study a zero range process on scale-free networks in order to investigate how network structure influences particle dynamics. The zero range process is defined with the rate p(n) = n(delta) at which particles hop out of nodes with n particles. We show analytically that a complete condensation occurs when delta < or = delta(c) triple bond 1/(gamma-1) where gamma is the degree distribution exponent of the underlying networks. In the complete condensation, those nodes whose degree is higher than a threshold are occupied by macroscopic numbers of particles, while the other nodes are occupied by negligible numbers of particles. We also show numerically that the relaxation time follows a power-law scaling tau approximately L(z) with the network size L and a dynamic exponent z in the condensed phase.     

耦合含时滞的相互依存网络的局部自适应异质同步

针对由两个子网络构成的耦合含时滞的相互依存网络,研究其局部自适应异质同步问题.时滞同时存在于两个子网络的内部耦合项和子网络间的一对一相互依赖耦合项中,且网络的耦合关系满足非线性特性和光滑性.基于李雅普诺夫稳定性理论、线性矩阵不等式方法和自适应控制技术,通过对子网络设置合适的控制器,提出了使得相互依存网络的子网络分别同步到异质孤立系统的充分条件.针对小世界网络和无标度网络构成的相互依存网络进行数值模拟,验证了提出理论的正确性和有效性.     

Perfect quantum state transfer with spinor bosons on weighted graphs

A duality between the properties of many spinor bosons on a regular lattice and those of a single particle on a weighted graph reveals that a quantum particle can traverse an infinite hierarchy of networks with perfect probability in polynomial time, even as the number of nodes increases exponentially. The one-dimensional "quantum wire" and the hypercube are special cases in this construction, where the number of spin degrees of freedom is equal to one and the number of particles, respectively. An implementation of a near-perfect quantum state transfer across a weighted parallelepiped with ultracold atoms in optical lattices is discussed.     

RWCE算法中选择性接受差解策略优化换热网络

强制进化随机游走算法优化换热网络时,以一定的概率接受差解可有效促进结构进化,非贪婪性的差解搜索机制是目标函数跳出局部极值的关键。本文分析接受差解机制的作用,探究不同优化阶段的差解结构来源,观察年综合费用变化,发现大多数被接受的差解结构在后续的优化中又回归到原结构,存在较多无效的参数传递过程。我们提出选择性接受差解策略,只接受具有新个体产生的差解,基于指数函数建立接受差解概率递增公式,并对结构中的新个体加以保护以增强其在结构中的存活率。最后选用9SP₂、20SP算例进行验证,取得了优于已发表文献的最优结果,证明了该策略的可行性。     

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.     

Research on bimodal particle extinction coefficient during Brownian coagulation and condensation for the entire particle size regime

The extinction coefficient of atmospheric aerosol particles influences the earth’s radiation balance directly or indirectly, and it can be determined by the scattering and absorption characteristics of aerosol particles. The problem of estimating the change of extinction coefficient due to time evolution of bimodal particle size distribution is studied, and two improved methods for calculating the Brownian coagulation coefficient and the condensation growth rate are proposed, respectively. Through the improved method based on Otto kernel, the Brownian coagulation coefficient can be expressed simply in powers of particle volume for the entire particle size regime based on the fitted polynomials of the mean enhancement function. Meanwhile, the improved method based on Fuchs–Sutugin kernel is developed to obtain the condensation growth rate for the entire particle size regime. And then, the change of the overall extinction coefficient of bimodal distributions undergoing Brownian coagulation and condensation can be estimated comprehensively for the entire particle size regime. Simulation experiments indicate that the extinction coefficients obtained with the improved methods coincide fairly well with the true values, which provide a simple, reliable, and general method to estimate the change of extinction coefficient for the entire particle size regime during the bimodal particle dynamic processes.     

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

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

Phase Separation in a Bidirectional Two-Lane Asymmetric Exclusion Process

This paper studies a bidirectional two-lane asymmetric exclusion process, in which particles move in opposite direction on the two lanes. Interaction between the two lanes is implemented as follows: particle hops with rate p when there is a particle at the same site in the other lane, otherwise it hops with rate 1. It is shown that under periodic boundary conditions, a plateau will form on the fundamental diagram if p<1. This plateau corresponds to a phase separation phenomenon. We have compared the phase separation with those reported in previous works, and it is shown that the mechanism of phase separation in our model is different from previous ones. A possible phase separation mechanism is proposed, i.e., the system always tries to maximize the probability that particles could hop with rate 1. A simple mean field approximation and a 2-cluster mean field approach have been applied to calculate the steady current. It is shown that the results of the 2-cluster mean field approach are much closer to the simulations.     

Average Cycle Period in Asymmetrical Flashing Ratchet

The directed motion of a Brownian particle in a flashing potential with various transition probabilities and waiting times in one of two states is studied. An expression for the average cycle period is proposed and the steady current J of the particle is calculated via Langevin simulation. The results show that the optimal cycle period τ_m, which takes the maximum of J, is shifted to a small value when the transition probability λ from the potential on to the potential off decreases, the maximal current appears in the case of the average waiting time in the potential on being longer than in the potential off, and the direction of current depends on the ratio of the average times waiting in two states.     

Using bimodal probability distributions in the problems of Brownian diffusion

When analyzing nonlinear stochastic systems, we deal with the chains of differential equations for the moments or cumulants of dynamic variables. To disconnect such chains, the well-known cumulant approach, which is adequate to the quasi-Gaussian expansion of the higher-order moments is used. However, this method is inefficient in the problems of Brownian diffusion in bimodal potential profiles, and the disconnection problem should be solved on the basis of bimodal probability distributions. To this end, we propose to construct bimodal model distributions, in particular, the bi-Gaussian distribution. Cumulants and the expansions of the higher-order moments for symmetric and nonsymmetric bi-Gaussian models. On this basis, we consider relaxation of probability characteristics of one-dimensional Brownian motion in the bimodal potential profile. The dependences of relaxation of the mean value and variance of particle coordinate on the potential barrier “power,” the noise intensity, and the initial distribution of particles are analyzed numerically. In particular, it is shown that relaxation proceeds by stages with different temporal scales in the case of a powerful barrier. __________ Translated from Izvestiya Vysshikh Uchebnykh Zavedenii, Radiofizika, Vol. 49, No. 8, pp. 718–729, August 2006.     

Brownian diffusion of gold nanoparticles in an optical trap studied by fluorescence correlation spectroscopy

The effect of thermal-induced Brownian motion on gold nanoparticles (Au NPs) in optical traps is studied by fluorescence correlation spectroscopy (FCS) method. The Brownian motion and optical trapping potential are investigated by the decay time of the FCS curve and the laser power. It is shown that that the probability of finding a gold nanoparticle in the trap depends on the ratio of the optical energy of the particle to its thermal energy. A power threshold is observed by the decay time as a function of laser power. The experimental studies show that the temperature rise does not seriously affect the average number of particles in the focal spot, but the average residence time is more sensitively affected by the temperature.     

Dynamics of congestion transition triggered by multiple walkers on complex networks

The congestion transition triggered by multiple walkers walking along the shortest path on complex networks is numerically investigated. These networks are composed of nodes that have a finite capacity in analogy to the buffer memory of a computer. It is found that a transition from free-flow phase to congestion phase occurs at a critical walker density f_c, which varies for complex networks with different topological structures. The dynamic pictures of congestion for networks with different topological structures show that congestion on scale-free networks is a percolation process of congestion clusters, while the dynamics of congestion transition on non-scale-free networks is mainly a process of nucleation.     

Congestion prevention for reliable OBS

It is known that Internet traffic exhibits a structural self-similarity over a wide range of time scales. Existing performance evaluation studies in optical burst switching (OBS) networks show high contention performance degradation in the nodes under correlated traffic. Due to its buffer-less nature, OBS efficiency can be reduced by resource contention leading to burst loss. Several methods have been proposed to address this problem, most of them relying on reactive mechanisms, which increase the complexity of core nodes, hampering scalability. In this paper to have congestion prevention, an efficient scheme incorporating delayed reservation decision has been proposed which not only offers reduction in resource contention by maintaining the same node complexity as that in general OBS networks with optical buffers but also provides improvement in system's throughput. Simulations show the proposed scheme has better performance than existing schemes in terms of burst loss probability.     

Brownian motion with active fluctuations

We study the effect of different types of fluctuation on the motion of self-propelled particles in two spatial dimensions. We distinguish between passive and active fluctuations. Passive fluctuations (e.g., thermal fluctuations) are independent of the orientation of the particle. In contrast, active ones point parallel or perpendicular to the time dependent orientation of the particle. We derive analytical expressions for the speed and velocity probability density for a generic model of active Brownian particles, which yields an increased probability of low speeds in the presence of active fluctuations in comparison to the case of purely passive fluctuations. As a consequence, we predict sharply peaked Cartesian velocity probability densities at the origin. Finally, we show that such a behavior may also occur in non-Gaussian active fluctuations and discuss briefly correlations of the fluctuating stochastic forces.     

Major impact of queue-rule choice on the performance of dynamic networks with limited buffer size

We investigate the similarities and differences among three queue rules, the first-in-first-out(FIFO) rule, last-in-firstout(LIFO) rule and random-in-random-out(RIRO) rule, on dynamical networks with limited buffer size. In our network model, nodes move at each time step. Packets are transmitted by an adaptive routing strategy, combining Euclidean distance and node load by a tunable parameter. Because of this routing strategy, at the initial stage of increasing buffer size, the network density will increase, and the packet loss rate will decrease. Packet loss and traffic congestion occur by these three rules, but nodes keep unblocked and lose no packet in a larger buffer size range on the RIRO rule networks. If packets are lost and traffic congestion occurs, different dynamic characteristics are shown by these three queue rules. Moreover, a phenomenon similar to Braess' paradox is also found by the LIFO rule and the RIRO rule.     

一种基于网络最大可控子图的导航搜索模型

基于网络可控性模型提出了最大可控子图的概念,在此基础上提出了一种基于最大可控子图的导航搜索模型. 模型中基于最大可控子图的加边策略用最小的代价解决了有向网络搜索中存在的粒子因“无路可走”而终止搜索的问题;基于最大可控子图部署导航节点,仅用节点总数2%左右的导航点,就使全网搜索时间接近导航网络的平均最短路径. 通过在ER和SF 网络上的实验表明,全网搜索时间与网络的可控性有关,可控性越好,添加的边数量越少,同时会使网络中导航节点分布越多,越能提高网络的搜索效率. 关键词： 导航搜索 有向网 网络可控性