We study a finite number of independent random walks with subexponentially distributed increments and negative drifts.We extend the one-dimensional results to finite and fully general stopping times.Assuming that the ...We study a finite number of independent random walks with subexponentially distributed increments and negative drifts.We extend the one-dimensional results to finite and fully general stopping times.Assuming that the distribution of the lengths of these intervals is relatively light compared to the distribution of the increments of the random walks,we derive the asymptotic tail distribution of the partial maximum sum over the random time interval.展开更多
In this paper,large deviations principle(LDP)and moderate deviations principle(MDP)of record numbers in random walks are studied under certain conditions.The results show that the rate functions of LDP and MDP are dif...In this paper,large deviations principle(LDP)and moderate deviations principle(MDP)of record numbers in random walks are studied under certain conditions.The results show that the rate functions of LDP and MDP are different from those of weak record numbers,which are interesting complements of the conclusions by Li and Yao[1].展开更多
Quantum algorithms have demonstrated provable speedups over classical counterparts,yet establishing a comprehensive theoretical framework to understand the quantum advantage remains a core challenge.In this work,we de...Quantum algorithms have demonstrated provable speedups over classical counterparts,yet establishing a comprehensive theoretical framework to understand the quantum advantage remains a core challenge.In this work,we decode the quantum search advantage by investigating the critical role of quantum state properties in random-walk-based algorithms.We propose three distinct variants of quantum random-walk search algorithms and derive exact analytical expressions for their success probabilities.These probabilities are fundamentally determined by specific initial state properties:the coherence fraction governs the first algorithm’s performance,while entanglement and coherence dominate the outcomes of the second and third algorithms,respectively.We show that increased coherence fraction enhances success probability,but greater entanglement and coherence reduce it in the latter two cases.These findings reveal fundamental insights into harnessing quantum properties for advantage and guide algorithm design.Our searches achieve Grover-like speedups and show significant potential for quantum-enhanced machine learning.展开更多
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...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.展开更多
Suppose {Xn} is a random walk in time-random environment with state space Z^d, ｜Xn｜ approaches infinity, then under some reasonable conditions of stability, the upper bound of the discrete Packing dimension of the r...Suppose {Xn} is a random walk in time-random environment with state space Z^d, ｜Xn｜ approaches infinity, then under some reasonable conditions of stability, the upper bound of the discrete Packing dimension of the range of {Xn} is any stability index α. Moreover, if the environment is stationary, a similar result for the lower bound of the discrete Hausdorff dimension is derived. Thus, the range is a fractal set for almost every environment.展开更多
Controls, especially effficiency controls on dynamical processes, have become major challenges in many complex systems. We study an important dynamical process, random walk, due to its wide range of applications for m...Controls, especially effficiency controls on dynamical processes, have become major challenges in many complex systems. We study an important dynamical process, random walk, due to its wide range of applications for modeling the transporting or searching process. For lack of control methods for random walks in various structures, a control technique is presented for a class of weighted treelike scale-free networks with a deep trap at a hub node. The weighted networks are obtained from original models by introducing a weight parameter. We compute analytically the mean first passage time （MFPT） as an indicator for quantitatively measurinM the et^ciency of the random walk process. The results show that the MFPT increases exponentially with the network size, and the exponent varies with the weight parameter. The MFPT, therefore, can be controlled by the weight parameter to behave superlinearly, linearly, or sublinearly with the system size. This work provides further useful insights into controllinM eftlciency in scale-free complex networks.展开更多
Complex networks display community structures. Nodes within groups are densely connected but among groups are sparsely connected. In this paper, an algorithm is presented for community detection named Markov Random Wa...Complex networks display community structures. Nodes within groups are densely connected but among groups are sparsely connected. In this paper, an algorithm is presented for community detection named Markov Random Walks Ants(MRWA). The algorithm is inspired by Markov random walks model theory, and the probability of ants located in any node within a cluster will be greater than that located outside the cluster.Through the random walks, the network structure is revealed. The algorithm is a stochastic method which uses the information collected during the traverses of the ants in the network. The algorithm is validated on different datasets including computer-generated networks and real-world networks. The outcome shows the algorithm performs moderately quickly when providing an acceptable time complexity and its result appears good in practice.展开更多
The recurrence properties of random walks can be characterized by P61ya number, i.e., the probability that the walker has returned to the origin at least once. In this paper, we consider recurrence properties for a ge...The recurrence properties of random walks can be characterized by P61ya number, i.e., the probability that the walker has returned to the origin at least once. In this paper, we consider recurrence properties for a general 1D random walk on a line, in which at each time step the walker can move to the left or right with probabilities l and r, or remain at the same position with probability o （l ＋ r ＋ o = 1）. We calculate Polya number P of this model and find a simple expression for P as, P = 1 - △, where △ is the absolute difference of l and r （△= ｜l - r｜）. We prove this rigorous expression by the method of creative telescoping, and our result suggests that the walk is recurrent if and only if the left-moving probability l equals to the right-moving probability r.展开更多
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 fam...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.展开更多
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 ...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.展开更多
We primarily provide several estimates for the heat kernel defined on the 2-dimensional simple random walk. Additionally, we offer an estimate for the heat kernel on high-dimensional random walks, demonstrating that t...We primarily provide several estimates for the heat kernel defined on the 2-dimensional simple random walk. Additionally, we offer an estimate for the heat kernel on high-dimensional random walks, demonstrating that the heat kernel in higher dimensions converges rapidly. We also compute the constants involved in the estimate for the 1-dimensional heat kernel. Furthermore, we discuss the general case of on-diagonal estimates for the heat kernel.展开更多
The biased random walk on supercritical Galton–Watson trees is known to exhibit a multiscale phenomenon in the slow regime:the maximal displacement of the walk in the first n steps is of order(log n)3,whereas the typ...The biased random walk on supercritical Galton–Watson trees is known to exhibit a multiscale phenomenon in the slow regime:the maximal displacement of the walk in the first n steps is of order(log n)3,whereas the typical displacement of the walk at the n-th step is of order(log n)2.Our main result reveals another multiscale property of biased walks:the maximal potential energy of the biased walks is of order(log n)2 in contrast with its typical size,which is of order log n.The proof relies on analyzing the intricate multiscale structure of the potential energy.展开更多
Given an undirected graph,a specific query,and an cohesiveness parameter,Community Search(CS)aims to identify a cohesive subgraph forming as a community from the undirected graph that includes thequery.For users(ordin...Given an undirected graph,a specific query,and an cohesiveness parameter,Community Search(CS)aims to identify a cohesive subgraph forming as a community from the undirected graph that includes thequery.For users(ordinary or even expert users)with less information of graph structures,setting an suitablecohesiveness parameter is difficult.Even with a large cohesiveness parameter,the resulting size of communitysize is often too large.Compared with the whole community,key-members are more valuable than others inpractice.Therefore,our research focuses on a new problem Community Key-members Search(CKS),shiftingour interest to identify key-members from a community,rather than the community as a whole.To addressCKS,we first develop an exact method grounded in truss decomposition as a benchmark.Then,we proposefour algorithms leveraging random walks to balance efficiency and effectiveness,by using three cohesivenessfeatures for designing an appropriate transition matrix.The key-members are determined based on thestationary distribution.We conduct a theoretical analysis on the rationality of the design of cohesiveness-awaretransition matrix,utilizing Bayesian theory,Box-Cox transformation,and Copula function.Furthermore,wedesign an efficient refinement method to optimize the community key-members with very limited overhead.Then,we adopt it to CKS with multiple query nodes.Experimental studies across real-world datasetsdemonstrate the superiority of our method,which makes the query algorithm speed up by 512×on average andthe highest accuracy reachs 99.3%.展开更多
Random walks are a standard tool for modeling the spreading process in social and biological systems But in the face of large-scale networks, to achieve convergence, iterative calculation of the transition matrix in r...Random walks are a standard tool for modeling the spreading process in social and biological systems But in the face of large-scale networks, to achieve convergence, iterative calculation of the transition matrix in random walk methods consumes a lot of time. In this paper, we propose a three-stage hierarchical community detection algorithm based on Partial Matrix Approximation Convergence （PMAC） using random walks. First, this algorithm identifies the initial core nodes in a network by classical measurement and then utilizes the error function of the partial transition matrix convergence of the core nodes to determine the number of random walks steps. As such, the PMAC of the core nodes replaces the final convergence of all the nodes in the whole matrix. Finally based on the approximation convergence transition matrix, we cluster the communities around core nodes and use a closeness index to merge two communities. By recursively repeating the process, a dendrogram of the communities is eventually constructed. We validated the performance of the PMAC by comparing its results with those of two representative methods for three real-world networks with different scales展开更多
Accurate mass segmentation on mammograms is a critical step in computer-aided diagnosis (CAD) systems. It is also a challenging task since some of the mass lesions are embedded in normal tissues and possess poor contr...Accurate mass segmentation on mammograms is a critical step in computer-aided diagnosis (CAD) systems. It is also a challenging task since some of the mass lesions are embedded in normal tissues and possess poor contrast or ambiguous margins. Besides, the shapes and densities of masses in mammograms are various. In this paper, a hybrid method combining a random walks algorithm and Chan-Vese (CV) active contour is proposed for automatic mass segmentation on mammograms. The data set used in this study consists of 1095 mass regions of interest (ROIs). First, the original ROI is preprocessed to suppress noise and surrounding tissues. Based on the preprocessed ROI, a set of seed points is generated for initial random walks segmentation. Afterward, an initial contour of mass and two probability matrices are produced by the initial random walks segmentation. These two probability matrices are used to modify the energy function of the CV model for prevention of contour leaking. Lastly, the final segmentation result is derived by the modified CV model, during which the probability matrices are updated by inserting several rounds of random walks. The proposed method is tested and compared with other four methods. The segmentation results are evaluated based on four evaluation metrics. Experimental results indicate that the proposed method produces more accurate mass segmentation results than the other four methods.展开更多
The second-order random walk has recently been shown to effectively improve the accuracy in graph analysis tasks.Existing work mainly focuses on centralized second-order random walk(SOW)algorithms.SOW algorithms rely ...The second-order random walk has recently been shown to effectively improve the accuracy in graph analysis tasks.Existing work mainly focuses on centralized second-order random walk(SOW)algorithms.SOW algorithms rely on edge-to-edge transition probabilities to generate next random steps.However,it is prohibitively costly to store all the probabilities for large-scale graphs,and restricting the number of probabilities to consider can negatively impact the accuracy of graph analysis tasks.In this paper,we propose and study an alternative approach,SOOP(second-order random walks with on-demand probability computation),that avoids the space overhead by computing the edge-to-edge transition probabilities on demand during the random walk.However,the same probabilities may be computed multiple times when the same edge appears multiple times in SOW,incurring extra cost for redundant computation and communication.We propose two optimization techniques that reduce the complexity of computing edge-to-edge transition probabilities to generate next random steps,and reduce the cost of communicating out-neighbors for the probability computation,respectively.Our experiments on real-world and synthetic graphs show that SOOP achieves orders of magnitude better performance than baseline precompute solutions,and it can efficiently computes SOW algorithms on billion-scale graphs.展开更多
In this paper, we give a general model of random walks in time-random environment in any countable space. Moreover, when the environment is independently identically distributed, a recurrence-transience criterion and ...In this paper, we give a general model of random walks in time-random environment in any countable space. Moreover, when the environment is independently identically distributed, a recurrence-transience criterion and the law of large numbers are derived in the nearest-neighbor case on Z^1. At last, under regularity conditions, we prove that the RWIRE {Xn} on Z^1 satisfies a central limit theorem, which is similar to the corresponding results in the case of classical random walks.展开更多
We consider a branching random walk on N with a random environment in time （denoted by ξ）. Let Zn be the counting measure of particles of generation n, and let Zn（t） be its Laplace transform. We show the converge...We consider a branching random walk on N with a random environment in time （denoted by ξ）. Let Zn be the counting measure of particles of generation n, and let Zn（t） be its Laplace transform. We show the convergence of the free energy n-llog Zn（t）, large deviation principles, and central limit theorems for the sequence of measures {Zn}, and a necessary and sufficient condition for the existence of moments of the limit of the martingale Zn（t）/E[Zn（t）ξ].展开更多
We consider the state-dependent reflecting random walk on a half- strip. We provide explicit criteria for （positive） recurrence, and an explicit expression for the stationary distribution. As a consequence, the ligh...We consider the state-dependent reflecting random walk on a half- strip. We provide explicit criteria for （positive） recurrence, and an explicit expression for the stationary distribution. As a consequence, the light-tailed behavior of the stationary distribution is proved under appropriate conditions. The key idea of the method employed here is the decomposition of the trajectory of the random walk and the main tool is the intrinsic branching structure buried in the random walk on a strip, which is different from the matrix-analytic method.展开更多
The authors consider the simple random walk on the infinite cluster of the Bernoulli bond percolation of trees, and investigate the relation between the speed of the simple random walk and the retaining probability p ...The authors consider the simple random walk on the infinite cluster of the Bernoulli bond percolation of trees, and investigate the relation between the speed of the simple random walk and the retaining probability p by studying three classes of trees. A sufficient condition is established for Galton-Watson trees.展开更多
基金supported by Xinjiang Normal University Outstanding Young Teacher Research Launch Fund Project(Grant No.XJNU202116)。
文摘We study a finite number of independent random walks with subexponentially distributed increments and negative drifts.We extend the one-dimensional results to finite and fully general stopping times.Assuming that the distribution of the lengths of these intervals is relatively light compared to the distribution of the increments of the random walks,we derive the asymptotic tail distribution of the partial maximum sum over the random time interval.
基金supported by the National Natural Science Foundation of China(Grant No.11671145)the Science and Technology Commission of Shanghai Municipality(Grant No.18dz2271000).
文摘In this paper,large deviations principle(LDP)and moderate deviations principle(MDP)of record numbers in random walks are studied under certain conditions.The results show that the rate functions of LDP and MDP are different from those of weak record numbers,which are interesting complements of the conclusions by Li and Yao[1].
基金supported by the Fundamental Research Funds for the Central Universities,the National Natural Science Foundation of China(Grant Nos.12371132,12075159,12171044,12071179,and 12405006)the specific research fund of the Innovation Platform for Academicians of Hainan Province.
文摘Quantum algorithms have demonstrated provable speedups over classical counterparts,yet establishing a comprehensive theoretical framework to understand the quantum advantage remains a core challenge.In this work,we decode the quantum search advantage by investigating the critical role of quantum state properties in random-walk-based algorithms.We propose three distinct variants of quantum random-walk search algorithms and derive exact analytical expressions for their success probabilities.These probabilities are fundamentally determined by specific initial state properties:the coherence fraction governs the first algorithm’s performance,while entanglement and coherence dominate the outcomes of the second and third algorithms,respectively.We show that increased coherence fraction enhances success probability,but greater entanglement and coherence reduce it in the latter two cases.These findings reveal fundamental insights into harnessing quantum properties for advantage and guide algorithm design.Our searches achieve Grover-like speedups and show significant potential for quantum-enhanced machine learning.
基金Project supported by the Research Foundation of Hangzhou Dianzi University,China (Grant Nos. KYF075610032 andzx100204004-7)the Hong Kong Research Grants Council,China (Grant No. CityU 1114/11E)
文摘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.
基金Project supported by NNSF of China (10371092)Foundation of Wuhan University
文摘Suppose {Xn} is a random walk in time-random environment with state space Z^d, ｜Xn｜ approaches infinity, then under some reasonable conditions of stability, the upper bound of the discrete Packing dimension of the range of {Xn} is any stability index α. Moreover, if the environment is stationary, a similar result for the lower bound of the discrete Hausdorff dimension is derived. Thus, the range is a fractal set for almost every environment.
基金Supported by the National Natural Science Foundation of China under Grant Nos 61173118,61373036 and 61272254
文摘Controls, especially effficiency controls on dynamical processes, have become major challenges in many complex systems. We study an important dynamical process, random walk, due to its wide range of applications for modeling the transporting or searching process. For lack of control methods for random walks in various structures, a control technique is presented for a class of weighted treelike scale-free networks with a deep trap at a hub node. The weighted networks are obtained from original models by introducing a weight parameter. We compute analytically the mean first passage time （MFPT） as an indicator for quantitatively measurinM the et^ciency of the random walk process. The results show that the MFPT increases exponentially with the network size, and the exponent varies with the weight parameter. The MFPT, therefore, can be controlled by the weight parameter to behave superlinearly, linearly, or sublinearly with the system size. This work provides further useful insights into controllinM eftlciency in scale-free complex networks.
基金the National High Technology Research and Development(863)Program of China(No.2015AA043701)
文摘Complex networks display community structures. Nodes within groups are densely connected but among groups are sparsely connected. In this paper, an algorithm is presented for community detection named Markov Random Walks Ants(MRWA). The algorithm is inspired by Markov random walks model theory, and the probability of ants located in any node within a cluster will be greater than that located outside the cluster.Through the random walks, the network structure is revealed. The algorithm is a stochastic method which uses the information collected during the traverses of the ants in the network. The algorithm is validated on different datasets including computer-generated networks and real-world networks. The outcome shows the algorithm performs moderately quickly when providing an acceptable time complexity and its result appears good in practice.
基金Supported by National Natural Science Foundation of China under Grant No. 10975057Doctor Fund Project of Ministry of Education under Contract 20103201120003+1 种基金the New Teacher Foundation of Soochow University under Contracts Q3108908, Q4108910the Extracurricular Pesearch Foundation of Undergraduates under Grant No. KY2010056A
文摘The recurrence properties of random walks can be characterized by P61ya number, i.e., the probability that the walker has returned to the origin at least once. In this paper, we consider recurrence properties for a general 1D random walk on a line, in which at each time step the walker can move to the left or right with probabilities l and r, or remain at the same position with probability o （l ＋ r ＋ o = 1）. We calculate Polya number P of this model and find a simple expression for P as, P = 1 - △, where △ is the absolute difference of l and r （△= ｜l - r｜）. We prove this rigorous expression by the method of creative telescoping, and our result suggests that the walk is recurrent if and only if the left-moving probability l equals to the right-moving probability r.
基金Project supported by the National Natural Science Foundation of China (Grant Nos.61203155 and 11232005)the Natural Science Foundation of Zhejiang Province,China (Grant No.LQ12F03003)the Hong Kong Research Grants Council under the GRF Grant CityU (Grant No.1109/12)
文摘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.
文摘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.
文摘We primarily provide several estimates for the heat kernel defined on the 2-dimensional simple random walk. Additionally, we offer an estimate for the heat kernel on high-dimensional random walks, demonstrating that the heat kernel in higher dimensions converges rapidly. We also compute the constants involved in the estimate for the 1-dimensional heat kernel. Furthermore, we discuss the general case of on-diagonal estimates for the heat kernel.
文摘The biased random walk on supercritical Galton–Watson trees is known to exhibit a multiscale phenomenon in the slow regime:the maximal displacement of the walk in the first n steps is of order(log n)3,whereas the typical displacement of the walk at the n-th step is of order(log n)2.Our main result reveals another multiscale property of biased walks:the maximal potential energy of the biased walks is of order(log n)2 in contrast with its typical size,which is of order log n.The proof relies on analyzing the intricate multiscale structure of the potential energy.
文摘Given an undirected graph,a specific query,and an cohesiveness parameter,Community Search(CS)aims to identify a cohesive subgraph forming as a community from the undirected graph that includes thequery.For users(ordinary or even expert users)with less information of graph structures,setting an suitablecohesiveness parameter is difficult.Even with a large cohesiveness parameter,the resulting size of communitysize is often too large.Compared with the whole community,key-members are more valuable than others inpractice.Therefore,our research focuses on a new problem Community Key-members Search(CKS),shiftingour interest to identify key-members from a community,rather than the community as a whole.To addressCKS,we first develop an exact method grounded in truss decomposition as a benchmark.Then,we proposefour algorithms leveraging random walks to balance efficiency and effectiveness,by using three cohesivenessfeatures for designing an appropriate transition matrix.The key-members are determined based on thestationary distribution.We conduct a theoretical analysis on the rationality of the design of cohesiveness-awaretransition matrix,utilizing Bayesian theory,Box-Cox transformation,and Copula function.Furthermore,wedesign an efficient refinement method to optimize the community key-members with very limited overhead.Then,we adopt it to CKS with multiple query nodes.Experimental studies across real-world datasetsdemonstrate the superiority of our method,which makes the query algorithm speed up by 512×on average andthe highest accuracy reachs 99.3%.
基金supported by the National Natural Science Foundation of China(Nos.61272422,61572260,61373017,and 61572261)
文摘Random walks are a standard tool for modeling the spreading process in social and biological systems But in the face of large-scale networks, to achieve convergence, iterative calculation of the transition matrix in random walk methods consumes a lot of time. In this paper, we propose a three-stage hierarchical community detection algorithm based on Partial Matrix Approximation Convergence （PMAC） using random walks. First, this algorithm identifies the initial core nodes in a network by classical measurement and then utilizes the error function of the partial transition matrix convergence of the core nodes to determine the number of random walks steps. As such, the PMAC of the core nodes replaces the final convergence of all the nodes in the whole matrix. Finally based on the approximation convergence transition matrix, we cluster the communities around core nodes and use a closeness index to merge two communities. By recursively repeating the process, a dendrogram of the communities is eventually constructed. We validated the performance of the PMAC by comparing its results with those of two representative methods for three real-world networks with different scales
基金Project (Nos. 60772092 and 81101903) supported by the National Natural Science Foundation of China
文摘Accurate mass segmentation on mammograms is a critical step in computer-aided diagnosis (CAD) systems. It is also a challenging task since some of the mass lesions are embedded in normal tissues and possess poor contrast or ambiguous margins. Besides, the shapes and densities of masses in mammograms are various. In this paper, a hybrid method combining a random walks algorithm and Chan-Vese (CV) active contour is proposed for automatic mass segmentation on mammograms. The data set used in this study consists of 1095 mass regions of interest (ROIs). First, the original ROI is preprocessed to suppress noise and surrounding tissues. Based on the preprocessed ROI, a set of seed points is generated for initial random walks segmentation. Afterward, an initial contour of mass and two probability matrices are produced by the initial random walks segmentation. These two probability matrices are used to modify the energy function of the CV model for prevention of contour leaking. Lastly, the final segmentation result is derived by the modified CV model, during which the probability matrices are updated by inserting several rounds of random walks. The proposed method is tested and compared with other four methods. The segmentation results are evaluated based on four evaluation metrics. Experimental results indicate that the proposed method produces more accurate mass segmentation results than the other four methods.
文摘The second-order random walk has recently been shown to effectively improve the accuracy in graph analysis tasks.Existing work mainly focuses on centralized second-order random walk(SOW)algorithms.SOW algorithms rely on edge-to-edge transition probabilities to generate next random steps.However,it is prohibitively costly to store all the probabilities for large-scale graphs,and restricting the number of probabilities to consider can negatively impact the accuracy of graph analysis tasks.In this paper,we propose and study an alternative approach,SOOP(second-order random walks with on-demand probability computation),that avoids the space overhead by computing the edge-to-edge transition probabilities on demand during the random walk.However,the same probabilities may be computed multiple times when the same edge appears multiple times in SOW,incurring extra cost for redundant computation and communication.We propose two optimization techniques that reduce the complexity of computing edge-to-edge transition probabilities to generate next random steps,and reduce the cost of communicating out-neighbors for the probability computation,respectively.Our experiments on real-world and synthetic graphs show that SOOP achieves orders of magnitude better performance than baseline precompute solutions,and it can efficiently computes SOW algorithms on billion-scale graphs.
基金the Natural Science Foundation of Anhui Province （No. KJ2007B122） the Youth Teachers Aid Item of Anhui Province （No. 2007jq1117）.
文摘In this paper, we give a general model of random walks in time-random environment in any countable space. Moreover, when the environment is independently identically distributed, a recurrence-transience criterion and the law of large numbers are derived in the nearest-neighbor case on Z^1. At last, under regularity conditions, we prove that the RWIRE {Xn} on Z^1 satisfies a central limit theorem, which is similar to the corresponding results in the case of classical random walks.
基金Acknowledgements The authors would like to thank the anonymous referees for valuable comments and remarks. This work was partially supported by the Natural Scientific Research Innovation Foundation in Harbin Institute of Technology （HIT. NSRIF. 2015102）, the National Natural Science Foundation of China （Grant Nos. 11171044, 11101039）, and by the Natural Science Foundation of Hunan Province （Grant No. 11JJ2001）.
文摘We consider a branching random walk on N with a random environment in time （denoted by ξ）. Let Zn be the counting measure of particles of generation n, and let Zn（t） be its Laplace transform. We show the convergence of the free energy n-llog Zn（t）, large deviation principles, and central limit theorems for the sequence of measures {Zn}, and a necessary and sufficient condition for the existence of moments of the limit of the martingale Zn（t）/E[Zn（t）ξ].
基金Acknowledgements The authors would like to thank Drs. Hongyan Sun and Ke Zhou for their stimulating discussion. Also they would like to express their gratitude to the referees for their careful reading of the first version of paper and useful suggestions for revising the paper. This work was partially supported by the National Natural Science Foundation of China （Grant No. 11131003）, the 985 Project, and the Natural Sciences and Engineering Research Council of Canada （Grant No. 315660）.
文摘We consider the state-dependent reflecting random walk on a half- strip. We provide explicit criteria for （positive） recurrence, and an explicit expression for the stationary distribution. As a consequence, the light-tailed behavior of the stationary distribution is proved under appropriate conditions. The key idea of the method employed here is the decomposition of the trajectory of the random walk and the main tool is the intrinsic branching structure buried in the random walk on a strip, which is different from the matrix-analytic method.
基金Supported in part by Grant G1999075106 from the Ministry of Science and Technology of China
文摘The authors consider the simple random walk on the infinite cluster of the Bernoulli bond percolation of trees, and investigate the relation between the speed of the simple random walk and the retaining probability p by studying three classes of trees. A sufficient condition is established for Galton-Watson trees.
