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

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

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

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

Continuous-Time Classical and Quantum Random Walk on Direct Product of Cayley Graphs

In this paper we define direct product of graphs and give a recipe for obtaining probability of observing particle on vertices in the continuous-time classical and quantum random walk. In the recipe, the probability of observing particle on direct product of graph is obtained by multiplication of probability on the corresponding to sub-graphs, where this method is useful to determining probability of walk on compficated graphs. Using this method, we calculate the probability of Continuous-time classical and quantum random walks on many of finite direct product Cayley graphs （complete cycle, complete Kn, charter and n-cube）. Also, we inquire that the classical state the stationary uniform distribution is reached as t→∞ but for quantum state is not always satisfied.     

Biased random walk with restart for essential proteins prediction

Predicting essential proteins is crucial for discovering the process of cellular organization and viability. We propose biased random walk with restart algorithm for essential proteins prediction, called BRWR. Firstly, the common process of practice walk often sets the probability of particles transferring to adjacent nodes to be equal, neglecting the influence of the similarity structure on the transition probability. To address this problem, we redefine a novel transition probability matrix by integrating the gene express similarity and subcellular location similarity. The particles can obtain biased transferring probabilities to perform random walk so as to further exploit biological properties embedded in the network structure. Secondly, we use gene ontology (GO) terms score and subcellular score to calculate the initial probability vector of the random walk with restart. Finally, when the biased random walk with restart process reaches steady state, the protein importance score is obtained. In order to demonstrate superiority of BRWR, we conduct experiments on the YHQ, BioGRID, Krogan and Gavin PPI networks. The results show that the method BRWR is superior to other state-of-the-art methods in essential proteins recognition performance. Especially, compared with the contrast methods, the improvements of BRWR in terms of the ACC results range in 1.4%-5.7%, 1.3%-11.9%, 2.4%-8.8%, and 0.8%-14.2%, respectively. Therefore, BRWR is effective and reasonable.     

Improving Network Representation Learning via Dynamic Random Walk,Self-Attention and Vertex Attributes-Driven Laplacian Space Optimization

Network data analysis is a crucial method for mining complicated object interactions. In recent years, random walk and neural-language-model-based network representation learning (NRL) approaches have been widely used for network data analysis. However, these NRL approaches suffer from the following deficiencies: firstly, because the random walk procedure is based on symmetric node similarity and fixed probability distribution, the sampled vertices’ sequences may lose local community structure information; secondly, because the feature extraction capacity of the shallow neural language model is limited, they can only extract the local structural features of networks; and thirdly, these approaches require specially designed mechanisms for different downstream tasks to integrate vertex attributes of various types. We conducted an in-depth investigation to address the aforementioned issues and propose a novel general NRL framework called dynamic structure and vertex attribute fusion network embedding, which firstly defines an asymmetric similarity and h-hop dynamic random walk strategy to guide the random walk process to preserve the network’s local community structure in walked vertex sequences. Next, we train a self-attention-based sequence prediction model on the walked vertex sequences to simultaneously learn the vertices’ local and global structural features. Finally, we introduce an attributes-driven Laplacian space optimization to converge the process of structural feature extraction and attribute feature extraction. The proposed approach is exhaustively evaluated by means of node visualization and classification on multiple benchmark datasets, and achieves superior results compared to baseline approaches.     

Random Walk on the Range of Random Walk

We study the random walk X on the range of a simple random walk on ℤ ^d in dimensions d≥4. When d≥5 we establish quenched and annealed scaling limits for the process X, which show that the intersections of the original simple random walk path are essentially unimportant. For d=4 our results are less precise, but we are able to show that any scaling limit for X will require logarithmic corrections to the polynomial scaling factors seen in higher dimensions. Furthermore, we demonstrate that when d=4 similar logarithmic corrections are necessary in describing the asymptotic behavior of the return probability of X to the origin.     

Random walk in a random medium in one dimension

Applying scaling and universality arguments, the long-time behavior of the probability distribution for a random walk in a one-dimensional random medium satisfying Sinai's constraint is obtained analytically. The convergence to this asymptotic limit and the fluctuations of this distribution are evaluated by solving numerically the stochastic equations for this walk.     

Laplace operator and random walk on one-dimensional nonhomogeneous lattice

A classical result of probability theory states that under suitable space and time renormalization, a random walk converges to Brownian motion. We prove an analogous result in the case of nonhomogeneous random walk on onedimensional lattice. Under suitable conditions on the nonhomogeneous medium, we prove convergence to Brownian motion and explicitly compute the diffusion coefficient. The proofs are based on the study of the spectrum of random matrices of increasing dimension.     

General Random Walk in One Dimension and Its Application to DNA Transcription Process

We have derived a two-order difference equation about the general random walk in one dimension. Using this model in some physiological processes, we have calculated the average time in which enzyme released at random anywhere moves along a one-dimensional macromolecular strand to the end in quest of its binding site. From the results we can see that the average time can be affected greatly owing to the presence of "obstacles" on the macromolecular strand.     

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.     

一种基于随机行走和策略连接的网络演化模型

本文提出了一个基于随机行走和策略选择的复杂网络局域演化模型RAPA. 新节点加入系统不需要全局知识,而是通过随机行走构造局域世界;然后依据概率采用随机连接,"扶贫"连接或"亲富"连接策略,从局域世界中选择节点增加连接边;最终自组织演化具有幂律特点的复杂网络. 初步的解析计算和仿真实验都表明,RAPA模型不仅重现了具有小世界特性、整体上的无标度特性,还可以演化出小变量饱和以及指数截断等现象,同时也具有明显的聚类特性,并能够构造出同配或异配等不同混合模式的网络. 关键词： 复杂网络 模型 随机行走 策略连接     

Solution of the persistent, biased random walk

The solution of the one-dimensional persistent, biased random walk is found. Its finite differences equation is derived and shown to be satisfied by the said solution.     

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.     

Directional quantum random walk induced by coherence

Quantum walk (QW), which is considered as the quantum counterpart of the classical random walk (CRW), is actually the quantum extension of CRW from the single-coin interpretation. The sequential unitary evolution engenders correlation between different steps in QW and leads to a non-binomial position distribution. In this paper, we propose an alternative quantum extension of CRW from the ensemble interpretation, named quantum random walk (QRW), where the walker has many unrelated coins, modeled as two-level systems, initially prepared in the same state. We calculate the walker's position distribution in QRW for different initial coin states with the coin operator chosen as Hadamard matrix. In one-dimensional case, the walker's position is the asymmetric binomial distribution. We further demonstrate that in QRW, coherence leads the walker to perform directional movement. For an initially decoherenced coin state, the walker's position distribution is exactly the same as that of CRW. Moreover, we study QRW in 2D lattice, where the coherence plays a more diversified role in the walker's position distribution.     

Classical random walk with memory versus quantum walk on a one-dimensional infinite chain

Quantum walk is a very useful tool for building quantum algorithms due to the faster spreading of probability distributions as compared to a classical random walk. Comparing the spreading of the probability distributions of a quantum walk with that of a mnemonic classical random walk on a one-dimensional infinite chain, we find that the classical random walk could have a faster spreading than that of the quantum walk conditioned on a finite number of walking steps. Quantum walk surpasses classical random walk with memory in spreading speed when the number of steps is large enough. However, in such a situation, quantum walk would seriously suffer from decoherence. Therefore, classical walk with memory may have some advantages in practical applications.     

Two-state random walk model of lattice diffusion. 1. Self-correlation function

Diffusion with interruptions (arising from localized oscillations, or traps, or mixing between jump diffusion and fluid-like diffusion, etc.) is a very general phenomenon. Its manifestations range from superionic conductance to the behaviour of hydrogen in metals. Based on a continuous-time random walk approach, we present a comprehensive two-state random walk model for the diffusion of a particle on a lattice, incorporating arbitrary holding-time distributions for both localized residence at the sites and inter-site flights, and also the correct first-waiting-time distributions. A synthesis is thus achieved of the two extremes of jump diffusion (zero flight time) and fluid-like diffusion (zero residence time). Various earlier models emerge as special cases of our theory. Among the noteworthy results obtained are: closed-form solutions (ind dimensions, and with arbitrary directional bias) for temporally uncorrelated jump diffusion and for the ‘fluid diffusion’ counterpart; a compact, general formula for the mean square displacement; the effects of a continuous spectrum of time scales in the holding-time distributions, etc. The dynamic mobility and the structure factor for ‘oscillatory diffusion’ are taken up in part 2.     

一种信息传播促进网络增长的网络演化模型

为了研究信息传播过程对复杂网络结构演化的影响,提出了一种信息传播促进网络增长的网络演化模型,模型包括信息传播促进网内增边、新节点通过局域世界建立第一条边和信息传播促进新节点连边三个阶段,通过多次自回避随机游走模拟信息传播过程,节点根据路径节点的节点度和距离与其选择性建立连接。理论分析和仿真实验表明,模型不仅具有小世界和无标度特性,而且不同参数下具有漂移幂律分布、广延指数分布等分布特性,呈现小变量饱和、指数截断等非幂律现象,同时,模型可在不改变度分布的情况下调节集聚系数,并能够产生从同配到异配具有不同匹配模式的网络.     

Scattering Matrix Modeling of Photon Migration in Turbid Media

Ｉｎｔｒｏｄｕｃｔｉｏｎ　　Ｏｐｔｉｃａｌｔｏｍｏｇｒａｐｈｙｕｓｉｎｇｎｅａｒｉｎｆｒａｒｅｄｌｉｇｈｔｔｏｅｘｔｒａｃｔｉｎｔｅｒｉｏｒａｂｎｏｒｍａｌｉｔｉｅｓｉｎｆｏｒｍａｔｉｏｎａｔｔｒａｃｔｓｍａｎｙｒｅｓｅａｒｃｈｉｎｔｅｒｅｓｔｓｉｎｂｉｏｍｅｄｉｃａｌｏｐｔｉｃｓ［１］,ｂｅｃａｕｓｅｉｔｐｒｏｖｉｄｅｓａｎａｌｔｅｒｎａｔｉｖｅｐｏｔｅｎｔｉａｌｍｏｄａｌｉｔｙｔｏｐｒｏｂｅｂｒｅａｓｔｃａｎｃｅｒａｎｄｍｏｎｉｔｏｒｂｒａｉｎａｎｄｍｕｓｃｌｅｏｘｙｇｅｎａｔｉｏｎｎｏｎ…     

Scattering Matrix Modeling of Photon Migration in Turbid Media

A lattice random walk model based on walkers wandering on discrete lattice of scattering space by discrete spatial and temporal step is presented. The scattering matrix and linking matrix of the lattice random walk are given for the scattering and absorption processes in homogenous and inhomogeneous turbid media. All the results obey the principle of causality.     

激光陀螺捷联惯性导航系统误差分析及仿真计算

激光陀螺随机游走现象的存在，严重影响了捷联惯性导航系统的导航性能。本文用数学分析的方法推导出激光陀螺随机游走造成的系统导航误差标准偏差的解析表达式，以便定量地研究激光陀螺随机游走对系统精度的影响，并提出改进措施。同时按照给定的飞行轨迹和随机游走系数，进行了系统数学仿真计算，对仿真计算结果进行了分析。