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

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

Random walks in generalized delayed recursive trees

Recently a great deal of effort has been made to explicitly determine the mean first-passage time （MFPT） between two nodes averaged over all pairs of nodes on a fractal network. In this paper, we first propose a family of generalized delayed recursive trees characterized by two parameters, where the existing nodes have a time delay to produce new nodes. We then study the MFPT of random walks on this kind of recursive tree and investigate the effect of the time delay on the MFPT. By relating random walks to electrical networks, we obtain an exact formula for the MFPT and verify it by numerical calculations. Based on the obtained results, we further show that the MFPT of delayed recursive trees is much shorter, implying that the efficiency of random walks is much higher compared with the non-delayed counterpart. Our study provides a deeper understanding of random walks on delayed fractal networks.     

Exact scaling for the mean first-passage time of random walks on a generalized Koch network with a trap

In this paper, we study the scaling for the mean first-passage time (MFPT) of the random walks on a generalized Koch network with a trap. Through the network construction, where the initial state is transformed from a triangle to a polygon, we obtain the exact scaling for the MFPT. We show that the MFPT grows linearly with the number of nodes and the dimensions of the polygon in the large limit of the network order. In addition, we determine the exponents of scaling efficiency characterizing the random walks. Our results are the generalizations of those derived for the Koch network, which shed light on the analysis of random walks over various fractal networks.     

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.     

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.     

Random walks on complex networks

We investigate random walks on complex networks and derive an exact expression for the mean first-passage time (MFPT) between two nodes. We introduce for each node the random walk centrality C, which is the ratio between its coordination number and a characteristic relaxation time, and show that it determines essentially the MFPT. The centrality of a node determines the relative speed by which a node can receive and spread information over the network in a random process. Numerical simulations of an ensemble of random walkers moving on paradigmatic network models confirm this analytical prediction.     

Exact scaling for the mean first-passage time of random walks on a generalized Koch network with a trap

In this paper,we study the scaling for the mean first-passage time(MFPT) of the random walks on a generalized Koch network with a trap.Through the network construction,where the initial state is transformed from a triangle to a polygon,we obtain the exact scaling for the MFPT.We show that the MFPT grows linearly with the number of nodes and the dimensions of the polygon in the large limit of the network order.In addition,we determine the exponents of scaling efficiency characterizing the random walks.Our results are the generalizations of those derived for the Koch network,which shed light on the analysis of random walks over various fractal networks.     

Lévy Walk with Multiple Internal States

Lévy walk with multiple internal states can effectively model the motion of particles that don’t immediately move back to the directions or areas which they come from. When the Lévy walk behaves superdiffusion, it is discovered that the non-immediately-repeating property, characterized by the constructed transition matrix, has no influence on the particle’s mean square displacement (MSD) or Pearson coefficient. This is a kind of stable property of Lévy walk. However, if the Lévy walk shows the dynamical behaviors of normal diffusion, then the effect of non-immediately-repeating emerges. For the Lévy walk with some particular transition matrices, it may display nonsymmetric dynamics; in these cases, the behaviors of their variances are detailedly discussed, especially some comparisons with the ones of the continuous time random walks are made (a striking difference is the changes of the exponents of the variances). The first passage time distribution and its average of Lévy walks are simulated, the results of which turn out that the first passage time can distinguish Lévy walks with different transition matrices, while the MSD can not.

     

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

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

Quantum Approach to Fast Protein-Folding Time

In the traditional random-conformational-search model,various hypotheses with a series of meta-stable intermediate states were proposed to resolve the Levinthal paradox in protein-folding time.Here we introduce a quantum strategy to formulate protein folding as a quantum walk on a definite graph, which provides us a g'eneral framework without making hypotheses.Evaluating it by the mean of first passage time,we find that the folding time via our quantum approach is much shorter than the one obtained via.classical random walks.This idea is expected to evoke more insights for future studies.     

Walks on Apollonian networks

We carry out comparative studies of random walks on deterministic Apollonian networks (DANs) and random Apollonian networks (RANs). We perform computer simulations for the mean first-passage time, the average return time, the mean-square displacement, and the network coverage for the unrestricted random walk. The diffusions both on DANs and RANs are proved to be sublinear. The effects of the network structure on the dynamics and the search efficiencies of walks with various strategies are also discussed. Contrary to intuition, it is shown that the self-avoiding random walk, which has been verified as an optimal local search strategy in networks, is not the best strategy for the DANs in the large size limit.     

Biased trapping issue on weighted hierarchical networks

In this paper, we present trapping issues of weight-dependent walks on weighted hierarchical networks which are based on the classic scale-free hierarchical networks. Assuming that edge’s weight is used as local information by a random walker, we introduce a biased walk. The biased walk is that a walker, at each step, chooses one of its neighbours with a probability proportional to the weight of the edge. We focus on a particular case with the immobile trap positioned at the hub node which has the largest degree in the weighted hierarchical networks. Using a method based on generating functions, we determine explicitly the mean first-passage time (MFPT) for the trapping issue. Let parameter a (0 < a < 1) be the weight factor. We show that the efficiency of the trapping process depends on the parameter a; the smaller the value of a, the more efficient is the trapping process.     

Open Quantum Random Walks

A new model of quantum random walks is introduced, on lattices as well as on finite graphs. These quantum random walks take into account the behavior of open quantum systems. They are the exact quantum analogues of classical Markov chains. We explore the “quantum trajectory” point of view on these quantum random walks, that is, we show that measuring the position of the particle after each time-step gives rise to a classical Markov chain, on the lattice times the state space of the particle. This quantum trajectory is a simulation of the master equation of the quantum random walk. The physical pertinence of such quantum random walks and the way they can be concretely realized is discussed. Differences and connections with the already well-known quantum random walks, such as the Hadamard random walk, are established.     

二维量子随机行走及其物理实现

近年来量子随机行走相关课题因其非经典的特性,已经成为越来越多科研人员的研究热点。这篇文章中我们回顾了一维经典随机行走和一维量子随机行走模型,并且在分析两种二维经典随机行走模型的基础上,我们构建二维量子随机行走模型。通过对随机行走者的位置分布标准差的计算,我们可以证明基于这种二维量子随机行走模型的算法优于其他上述随机行走。除此之外,我们提出一个利用线性光学方法的实验方案,实现这种二维量子随机行走模型。     

复式格子上无规行走问题的一种处理方法

本文中通过引入格子无规行走的结构因子矩阵,推广了生成函数技术,提出一种可以处理具有复杂元胞结构的格子无规行走问题的理论方法。为说明这一方法的有效性以及如何运用这一方法,本文求解了一维无限二聚化链上的无规行走问题。 关键词：     

A study on correlated exponential random walks

Based on the linear Boltzmann transport formulation, we investigate the statistics of correlated exponential random walks that are continuous in space and discrete in time. We show that asymptotically, the correlated random walk process is diffusive and derive an effective diffusion constant. We investigate the power spectral characteristics of the associated random forces. We also present some results on the first passage time distribution and establish that asymptotically it reduces to that associated with simple Gaussian walks.     

Multiple-predators-based capture process on complex networks

The predator/prey(capture) problem is a prototype of many network-related applications. We study the capture process on complex networks by considering multiple predators from multiple sources. In our model, some lions start from multiple sources simultaneously to capture the lamb by biased random walks, which are controlled with a free parameterα. We derive the distribution of the lamb's lifetime and the expected lifetime T. Through simulation, we find that the expected lifetime drops substantially with the increasing number of lions. Moreover, we study how the underlying topological structure affects the capture process, and obtain that locating on small-degree nodes is better than on largedegree nodes to prolong the lifetime of the lamb. The dense or homogeneous network structures are against the survival of the lamb. We also discuss how to improve the capture efficiency in our model.     

Duplication： a Mechanism Producing Disassortative Mixing Networks in Biology

Assortative/disassortative mixing is an important topological property of a network. A network is called assortative mixing if the nodes in the network tend to connect to their connectivity peers, or disassortative mixing if nodes with low degrees are more likely to connect with high-degree nodes. We have known that biological networks such as protein-protein interaction networks （PPI）, gene regulatory networks, and metabolic networks tend to be disassortative. On the other hand, in biological evolution, duplication and divergence are two fundamental processes. In order to make the relationship between the property of disassortative mixing and the two basic biological principles clear and to study the cause of the disassortative mixing property in biological networks, we present a random duplication model and an anti-preference duplication model. Our results show that disassortative mixing networks can be obtained by both kinds of models from uncorrelated initial networks. Moreover, with the growth of the network size, the disassortative mixing property becomes more obvious.     

Random Walk of Second Class Particles in Product Shock Measures

We consider shock measures in a class of conserving stochastic particle systems on ℤ. These shock measures have a product structure with a step-like density profile and include a second class particle at the shock position. We show for the asymmetric simple exclusion process, for the exponential bricklayers’ process, and for a generalized zero range process, that under certain conditions these shocks, and therefore the second class particles, perform a simple random walk. Some previous results, including random walks of product shock measures and stationary shock measures seen from a second class particle, are direct consequences of our more general theorem. Multiple shocks can also be handled easily in this framework. Similar shock structure is also found in a nonconserving model, the branching coalescing random walk, where the role of the second class particle is played by the rightmost (or leftmost) particle.     

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.