Non-Backtracking Random Walks and a Weighted Ihara’s Theorem

We study the mixing rate of non-backtracking random walks on graphs by looking at non-backtracking walks as walks on the directed edges of a graph. A result known as Ihara’s Theorem relates the adjacency matrix of a graph to a matrix related to non-backtracking walks on the directed edges. We prove a weighted version of Ihara’s Theorem which relates the transition probability matrix of a non-backtracking walk to the transition matrix for the usual random walk. This allows us to determine the spectrum of the transition probability matrix of a non-backtracking random walk in the case of regular graphs and biregular graphs. As a corollary, we obtain a result of Alon et al. in [1] that in most cases, a non-backtracking random walk on a regular graph has a faster mixing rate than the usual random walk. In addition, we obtain an analogous result for biregular graphs.

基于Random Walk算法的CT图像肺实质自动分割

针对复杂情况下肺实质的分割问题,提出了一种基于Random Walk算法对肺实质自动分割的方法。首先,根据胸部组织解剖学及其计算机断层扫描(CT)图像的影像学特征,在肺实质及其周围组织分别确定目标区域种子点和背景种子点位置;然后,使用Random Walk算法对CT图像进行分割,提取近似肺区域的掩模;接下来,对掩模实施数学形态学运算,来进一步调整目标区域种子点和背景种子点的标定位置,使其适合具体的复杂情况;最后,再次使用Random Walk算法分割图像,得到最终的肺实质分割结果。实验结果显示,该方法与金标准的平均绝对距离为0.44±0.13 mm,重合率(DC)为99.21%±0.38%。与其他分割方法相比,该方法在分割精度上得到了显著提高。结果表明,提出的方法能够解决复杂情况下肺实质分割的问题,确保了分割的完整性、准确性、实时性和鲁棒性,分割结果和时间均可满足临床需求。

Study on application of random walk method to calculate water exchange in large-scale bay

The water exchange matrix is an efficient tool to study the water exchange among the sub-areas in large-scale bays.The application of the random walk method to calculate the water exchange matrix is studied.Compared with the advection-diffusion model,the random walk model is more flexible to calculate the water exchange matrix. The forecast matrix suggested by Thompson et al.is used to evaluate the water exchange characteristics among the sub-areas fast.According to the theoretic analysis,it is found that the precision of the predicted results is mainly affected by three factors,namely, the particle number,the generated time of the forecast matrix,and the number of the sub-areas.The impact of the above factors is analyzed based on the results of a series of numerical tests.The results show that the precision of the forecast matrix increases with the increase of the generated time of the forecast matrix and the number of the particles. If there are enough particles in each sub-area,the precision of the forecast matrix will increase with the number of the sub-areas.Moreover,if the particles in each sub-area are not enough,the excessive number of the sub-areas can result in the decrease of the precision of the forecast matrix.

基于LBP的改进Random Walks算法在颅脑磁共振影像分割中的应用

目的由于颅脑结构复杂且颅脑磁共振影像易受噪声、磁场不均匀性、部分容积效应等因素的影响,精确的脑组织分割方法仍需深入研究。方法本文提出一种基于Random Walks的改进算法以提高脑白质、脑灰质及脑脊液分割的准确性。通过引入局部二值模式(local binary patterns,LBP)改进了传统Random Walks权重函数的构造,在反映相邻像素灰度变化信息的同时包含了局部图像的纹理信息,有利于合并同质区域并增强边缘轮廓的识别。本文还使用了灰度先验概率模型减少Random Walks种子点交互的次数。结果实验结果表明基于LBP的改进算法在多种不同水平的噪声及不均匀场作用下,能够有效识别磁共振影像中脑组织区域的边缘轮廓,并对噪声有良好的鲁棒性。结论基于LBP的改进Random Walks算法可精确分割颅脑磁共振影像。

Ergodicity recovery of random walk in heterogeneous disordered media

Significant and persistent trajectory-to-trajectory variance are commonly observed in particle tracking experiments,which have become a major challenge for the experimental data analysis.In this theoretical paper we investigate the ergodicity recovery behavior,which helps clarify the origin and the convergence of trajectory-to-trajectory fluctuation in various heterogeneous disordered media.The concepts of self-averaging and ergodicity are revisited in the context of trajectory analysis.The slow ergodicity recovery and the non-Gaussian diffusion in the annealed disordered media are shown as the consequences of the central limit theorem in different situations.The strange ergodicity recovery behavior is reported in the quenched disordered case,which arises from a localization mechanism.The first-passage approach is introduced to the ergodicity analysis for this case,of which the central limit theorem can be employed and the ergodicity is recovered in the length scale of diffusivity correlation.

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.

The Random Walk and Trend Stationary Models with an Analysis of the US Real GDP: Can We Distinguish between the Two Models?

The unit root can lead to major problems in economic time series analyses. I obtain the asymptotic distributions of the ordinary least squares (OLS) estimator when the true model is trend stationary for the following three cases: 1) the null model is a random walk without drift, and the auxiliary regression model does not contain a constant;2) the null model is a random walk with drift, and the auxiliary regression model contains a constant;and 3) the null model is a random walk with drift, and the auxiliary regression model contains both a constant and a time trend. In the third case, the asymptotic distribution of the OLS estimator is determined by the first order of the autocorrelation, and we can distinguish between the random walk and trend stationary models, unlike in previous studies. Based on these results, the real US gross domestic product is analyzed. A time trend model with autoregressive error terms is chosen. The results suggest that the impacts of a shock can become larger than the original shock in some periods and then gradually decline. However, the impacts continue for a long period, and policy makers should account for this to design better economic policies.

基于改进Random Walk算法的磁共振图像脑组织分割

在Random Walk算法中,边的权重对算法分割性能有着重要的影响,针对原算法在计算权重时仅使用相邻像素灰度值变化信息的局限性,通过引入图像局部熵,使得权重函数同时反映相邻像素灰度变化信息和图像局部灰度离散度信息,增强算法对目标内容和边界的识别能力。同时通过Fisher评价函数构造最佳分类阈值的选取法则,增强了算法的判别能力。实验表明改进后的算法对目标内容和边界的识别能力有较大提高,且对噪声具有更好的鲁棒性。

基于Random Walks算法的心脏双源CT左心房分割

针对在传统的CT介入式治疗过程中,胸腔中软组织较多软组织的厚度和注射的造影剂在心脏中呈现的不均匀分布,导致在采用CT成像的图像中胸腔内部各组织之间存在边界模糊或者确实等状况,本文提出一种采用形态重构和随机行走相结合的分割方法。首先利用形态学开闭运算对图像进行化简,并使得心脏CT腔体边界分离,进而使得各个组织组织分离,再结合Random walks算法。从而使得不需要标记太多种子点的情况下提高了分割的速度和准确性,实验证明该方法能够达到预期的目标。

CENTRAL LIMIT THEOREMS FOR A BRANCHING RANDOM WALK WITH A RANDOM ENVIRONMENT IN TIME

We consider a branching random walk with a random environment in time, in which the offspring distribution of a particle of generation n and the distribution of the displacements of its children depend on an environment indexed by the time n. The environment is supposed to be independent and identically distributed. For AR, let Zn(A) be the number of particles of generation n located in A. We show central limit theorems for the counting measure Zn(·) with appropriate normalization.

ASYMPTOTIC PROPERTIES OF A BRANCHING RANDOM WALK WITH A RANDOM ENVIRONMENT IN TIME

We consider a branching random walk in an independent and identically distributed random environment ξ=(ξn) indexed by the time. Let W be the limit of the martingale Wn=∫e^-txZn(dx)/Eξ∫e^-txZn(dx), with Zn denoting the counting measure of particles of generation n, and Eξ the conditional expectation given the environment ξ. We find necessary and sufficient conditions for the existence of quenched moments and weighted moments of W, when W is non-degenerate.

A random walk evolution model of wireless sensor networks and virus spreading

In this paper, considering both cluster heads and sensor nodes, we propose a novel evolving a network model based on a random walk to study the fault tolerance decrease of wireless sensor networks (WSNs) due to node failure, and discuss the spreading dynamic behavior of viruses in the evolution model. A theoretical analysis shows that the WSN generated by such an evolution model not only has a strong fault tolerance, but also can dynamically balance the energy loss of the entire network. It is also found that although the increase of the density of cluster heads in the network reduces the network efficiency, it can effectively inhibit the spread of viruses. In addition, the heterogeneity of the network improves the network efficiency and enhances the virus prevalence. We confirm all the theoretical results with sufficient numerical simulations.

Random walk search in unstructured P2P

Unstructured P2P has power-law link distribution, and the random walk in power-law networks is analyzed. The analysis results show that the probability that a random walker walks through the high degree nodes is high in the power-law network, and the information on the high degree nodes can be easily found through random walk. Random walk spread and random walk search method (RWSS) is proposed based on the analysis result. Simulation results show that RWSS achieves high success rates at low cost and is robust to high degree node failure.

Random walk modeling of wake dispersion for the exhaust tower of an underground tunnel in urban area

In this paper, some experimental studies on the impact of effluent from an exhaust tower of an underground tunnel with special construction are reported. By measuring the flow field downstream of the tower in NJU meteorological wind tunnel, some flow characteristics in the make area were established. Based on these, an advanced random\|walk dispersion model was set up and applied successfully to the simulation of dispersion in the wake area. The modelling results were in accordance with wind tunnel measurements. The computed maximum of ground surface concentration in the building case was a factor of 3-4 higher than that in the flat case and appeared much closer to the source. The simulation indicated that random walk modelling is an effective and practical tool for the wake stream impact assessment.

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.

Modelling of the behavior of marine oil spills: applications based on random walk techniques

ＩｎｔｒｏｄｕｃｔｉｏｎＴｈｅｆｒｅｑｕｅｎｃｙｏｆａｃｃｉｄｅｎｔａｌｏｉｌｓｐｉｌｌｓ,ａｎｄｔｈｅａｓｓｏｃｉａｔｅｄａｑｕａｔｉｃｐｏｌｌｕｔｉｏｎ,ａｒｅｇｒｏｗｉｎｇｃｏｎｃｅｒｎｓ.Ｔｈｅｒｅｉｓａｎｅｅｄｆｏｒｍｏｄｅｌｓｙｓｔｅｍｔｈ?..

RENEWAL THEOREM FOR(L,1)-RANDOM WALK IN RANDOM ENVIRONMENT

We consider a random walk on Z in random environment with possible jumps {-L,···,-1,1},in the case that the environment {ωi : i∈Z} are i.i.d..We establish the renewal theorem for the Markov chain of "the environment viewed from the particle" in both annealed probability and quenched probability,which generalize partially the results of Kesten(1977) and Lalley(1986) for the nearest random walk in random environment on Z,respectively.Our method is based on the intrinsic branching structure within the(L,1)-RWRE formulated in Hong and Wang(2013).

Some Probability Properties of Random Walk in Time-Random Environment

A general formulation of the stochastic model for random walk in time-random environment and an equivalent definition is established in this paper. Moreover, some basic probability relations similar to the classical case which are very useful in the corresponding research of fractal properties are given. At the end, a typical example is provided to show the recurrence and transience.

Application of random walk model to fit temperature in 46 gamma world cities from 1901 to 1998

Very recently, we have applied the random walk model to fit the global temperature anomaly, CRUTEM3. With encouraging results, we apply the random walk model to fit the temperature walk that is the conversion of recorded tem-perature and real recorded temperature in 46 gamma world cities from 1901 to 1998 in this study. The results show that the random walk model can fit both temperature walk and real recorded temperature although the fitted results from other climate models are unavailable for comparison in these 46 cities. Therefore, the random walk model can fit not only the global temperature anomaly, but also the real recorded temperatures in various cities around the world.