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.

THE DIMENSIONS OF THE RANGE OF RANDOM WALKS IN TIME-RANDOM ENVIRONMENTS

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.

Efficiency-Controllable Random Walks on a Class of Recursive Scale-Free Trees with a Deep Trap

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.

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.

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.

The Spread Speed of Multiple Catalytic Branching Random Walks

In this paper we study the asymptotic behavior of the maximal position of a supercritical multiple catalytic branching random walk(X_(n))on Z.If M_(n) is its maximal position at time n,we prove that there is a constantα>0 such that M_(n)/n converges toαalmost surely on the set of infinite number of visits to the set of catalysts.We also derive the asymptotic law of the centered process M_(n)-αn as n→∞.Our results are similar to those in[13].However,our results are proved under the assumption of finite L log L moment instead of finite second moment.We also study the limit of(X_(n))as a measure-valued Markov process.For any function f with compact support,we prove a strong law of large numbers for the process X_(n)(f).

Strong invariance principle for a counterbalanced random walk

We study a counterbalanced random walkS_(n)=X_(1)+…+X_(n),which is a discrete time non-Markovian process andX_(n) are given recursively as follows.For n≥2,X_(n) is a new independent sample from some fixed law̸=0 with a fixed probability p,andX_(n)=−X_(v(n))with probability 1−p,where v(n)is a uniform random variable on{1;…;n−1}.We apply martingale method to obtain a strong invariance principle forS_(n).

Hierarchical Community Detection Based on Partial Matrix Convergence Using Random Walks

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

SOOP: Efficient Distributed Graph Computation Supporting Second-Order Random Walks

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.

Asymptotic Behavior for Random Walks in Time-Random Environment on Z^1

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.

Light-tailed behavior of stationary distribution for state-dependent random walks on a strip

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.

Branching random walks with random environments in time

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）ξ].

On the Monotonicity of the Speed of Random Walks on a Percolation Cluster of Trees

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.

Strong Laws of Large Numbers for Random Walks in Random Sceneries

In this paper, we study strong laws of large numbers for random walks in random sceneries. Some mild sufficient conditions for the validity of strong laws of large numbers are obtained.

Asymptotic entropy of the ranges of random walks on discrete groups

Inspired by Benjamini et al.(2010) and Windisch(2010),we consider the entropy of the random walk ranges Rn formed by the first n steps of a random walk S on a discrete group.In this setting,we show the existence of hR:=limn→∞H(Rn)/n called the asymptotic entropy of the ranges.A sample version of the above statement in the sense of Shannon(1948) is also proved.This answers a question raised by Windisch(2010).We also present a systematic characterization of the vanishing asymptotic entropy of the ranges.Particularly,we show that hR=0 if and only if the random walk either is recurrent or escapes to negative infinity without left jump.By introducing the weighted digraphs Γn formed by the underlying random walk,we can characterize the recurrence property of S as the vanishing property of the quantity limn→∞H(Γn)/n,which is an analogue of hR.

AN INTERSECTION PROPERTY OF THE SIMPLE RANDOM WALKS IN Z^d

Let be the simple random walk in zd, and SupPers f(n) is an integer-valued function and increases to infinity as n tends to infinity, and In this paper,a necessary and sufficient condition to ensure or 1 is derived for d=3,4. This problem was first studied by P. Erdos and S.J. Taylor.

Directional-to-random transition of cell cluster migration

Efficient cell migration is crucial for the functioning of biological processes, e.g., morphogenesis, wound healing, and cancer metastasis. In this study, we monitor the migratory behavior of the 3D fibroblast clusters using live cell microscopy,and find that crowded environment affects cell migration, i.e., crowding leads to directional migration at the cluster’s periphery. The number of cell layers being stacked during seeding determines the directional-to-random transition. Intriguingly,the migratory behavior of cell clusters resembles the dispersion dynamics of clouds of passive particles, indicating that the biological process is driven by physical effects(e.g., entropy) rather than cell communication. Our findings highlight the role of intrinsic physical characteristics, such as crowding, in regulating biological behavior, and suggest new therapeutic approaches targeting at cancer metastasis.

Transport in Astrophysics: VI. Ultra-High Energy Cosmic Rays

Two new solutions of the homogeneous diffusion equation in 1D are derived in the presence of losses and a trigonometric profile for a profile of density. A simulation for the ankle in the energy distribution of cosmic rays (CRs) is provided in the framework of the fine tuning of the involved parameters. A theoretical image for the overall diffusion of CRs in galactic coordinates is provided.

Spatial search weighting information contained in cell velocity distribution

Cell migration plays a significant role in physiological and pathological processes.Understanding the characteristics of cell movement is crucial for comprehending biological processes such as cell functionality,cell migration,and cell–cell interactions.One of the fundamental characteristics of cell movement is the specific distribution of cell speed,containing valuable information that still requires comprehensive understanding.This article investigates the distribution of mean velocities along cell trajectories,with a focus on optimizing the efficiency of cell food search in the context of the entire colony.We confirm that the specific velocity distribution in the experiments corresponds to an optimal search efficiency when spatial weighting is considered.The simulation results indicate that the distribution of average velocity does not align with the optimal search efficiency when employing average spatial weighting.However,when considering the distribution of central spatial weighting,the specific velocity distribution in the experiment is shown to correspond to the optimal search efficiency.Our simulations reveal that for any given distribution of average velocity,a specific central spatial weighting can be identified among the possible central spatial weighting that aligns with the optimal search strategy.Additionally,our work presents a method for determining the spatial weights embedded in the velocity distribution of cell movement.Our results have provided new avenues for further investigation of significant topics,such as relationship between cell behavior and environmental conditions throughout their evolutionary history,and how cells achieve collective cooperation through cell-cell communication.

Enhancing personalized exercise recommendation with student and exercise portraits

The exercise recommendation system is emerging as a promising application in online learning scenarios,providing personalized recommendations to assist students with explicit learning directions.Existing solutions generally follow a collaborative filtering paradigm,while the implicit connections between students(exercises)have been largely ignored.In this study,we aim to propose an exercise recommendation paradigm that can reveal the latent connections between student-student(exercise-exercise).Specifically,a new framework was proposed,namely personalized exercise recommendation with student and exercise portraits(PERP).It consists of three sequential and interdependent modules:Collaborative student exercise graph(CSEG)construction,joint random walk,and recommendation list optimization.Technically,CSEG is created as a unified heterogeneous graph with students’response behaviors and student(exercise)relationships.Then,a joint random walk to take full advantage of the spectral properties of nearly uncoupled Markov chains is performed on CSEG,which allows for full exploration of both similar exercises that students have finished and connections between students(exercises)with similar portraits.Finally,we propose to optimize the recommendation list to obtain different exercise suggestions.After analyses of two public datasets,the results demonstrated that PERP can satisfy novelty,accuracy,and diversity.