Fold maps associated to geodesic random walks on curved spaces.
problem Understanding the behavior of geodesic random walks on curved surfaces.
method Analyzing mappings from the unit tangent sphere to a manifold with non-positive curvature.
result For odd powers of the unit tangent sphere, these mappings are fold maps.
Data-driven methods link graphon limits to random walks and spectral clustering.
problem Clustering signals evolving over time with graphon limits.
method Transfer operators, Koopman and Perron-Frobenius, for estimating graphon from signal data.
result Spectral clustering can be extended to graphons, reconstructing transition densities and graphons.
Random walks on cell complexes link to Laplacians and Novikov-Shubin invariants.
problem Computing Novikov-Shubin invariants for complex cell structures.
method Construct random walks on cell complexes, relate to Laplacians, and use return probabilities.
result Novikov-Shubin invariants can be recovered from random walk return probabilities.
Invariance principle proved for lifted geodesic walks on Riemannian submersions.
problem Proving convergence to horizontal Brownian motion for lifted geodesic walks.
method Appropriate conditions on geodesic random walks' speed; proving invariance principle.
result Convergence to horizontal Brownian motion for lifted geodesic walks.
ParPIC clusters directed graphs using random walks and diffusion operators.
problem Challenges in vertex-level clustering for directed graphs due to edge directionality.
method Parametrized Power-Iteration Clustering (ParPIC) based on reversible random walks and diffusion operators.
result ParPIC achieves competitive clustering accuracy with improved scalability compared to spectral and teleportation-based methods.
Study uniform convergence of random walk Laplacians to diffusion Laplacian on smooth manifolds.
problem Uniform convergence of random walk Laplacians to diffusion Laplacian on smooth manifolds.
method Analysis of random walks on geometric and directed kNN graphs, using concentration tools and differential geometry.
result Uniform convergence of kNN Laplacians to diffusion Laplacian, without continuity of transition kernel. This paper considers a classical question of approximation of Brownian motion by a random walk in the setting of a sub-Riemannian manifold M. To construct such a random walk we first address several issues related to the degeneracy of such a manifold. In particular, we define a family of sub-Laplacian operators natur…
We review statistical properties of models generated by the application of a (positive and negative order) fractional derivative operator to a standard random walk and show that the resulting stochastic walks display slowly-decaying autocorrelation functions. The relation between these correlated walks and the well-kno…
New random walk results on rank one symmetric spaces.
problem Analyzing random walks on noncompact rank one symmetric spaces.
method Unified algebraic framework using Möbius addition and harmonic analysis of spherical functions.
result Renormalized walk converges to heat kernel on Laplace-Beltrami operator.
New methods for calculating curvature in graph theory.
problem Calculating curvature in graphs and random walks.
method Analyzing continuous and discrete-time Ollivier-Ricci curvatures of weighted graphs.
result Generalized existence and properties of Ollivier-Ricci curvature for various random walks.
We introduce a novel harmonic analysis for functions defined on the vertices of a strongly connected directed graph of which the random walk operator is the cornerstone. As a first step, we consider the set of eigenvectors of the random walk operator as a non-orthogonal Fourier-type basis for functions over directed gr…
OpEvo automates tensor operator optimization for better efficiency.
problem Manual optimization of tensor operators is inefficient and limited.
method OpEvo uses evolutionary computation with topology-aware mutation.
result OpEvo finds optimal configurations with less effort and variance.
A methodology is developed to identify, as units of study, each decrease in the value of a stock from a given maximum price level. A critical level in the amount of price declines is found to separate a segment operating under a random walk from a segment operating under a power law. This level is interpreted as a poin…
Study large deviations in random walks on Lie groups.
problem Large deviations in sub-Riemannian random walks.
method Prove large deviation principle for random walks on stratified Lie groups.
result Proved a large deviation principle with a rate function adapted to sub-Riemannian geometry.
We review recent advances on the record statistics of strongly correlated time series, whose entries denote the positions of a random walk or a Lévy flight on a line. After a brief survey of the theory of records for independent and identically distributed random variables, we focus on random walks. During the last few…
This paper presents VEC-NBT, a variation on the unsupervised graph clustering technique VEC, which improves upon the performance of the original algorithm significantly for sparse graphs. VEC employs a novel application of the state-of-the-art word2vec model to embed a graph in Euclidean space via random walks on the n…
Quantum walks blend patterns into splines when averaged.
problem Understanding the asymptotic patterns of quantum random walks.
method Averaging over quantum coins using the Haar measure.
result Patterns blend into splines, showing a unified behavior.
Local limit theorem for random walks on hyperbolic groups with parabolic subgroups.
problem Analyzing the behavior of random walks on relatively hyperbolic groups.
method Study of convergent random walks with finite derivative of Green function at spectral radius.
result Proves a local limit theorem for the probability of returning to the origin.
Study diffusions and random walks on hyperbolic spaces, focusing on their Martin boundaries.
problem Understanding diffusions and random walks on hyperbolic spaces.
method Analyzing specific diffusions and random walks on hyperbolic spaces, examining their Martin boundaries.
result Characterized the Martin boundaries of diffusions and random walks on hyperbolic spaces.
Random walks on metric spaces embed quasi-isometrically into the space.
problem Embedding random subgroups of metric spaces quasi-isometrically.
method Analyzing random walks and contracting elements in metric spaces.
result Random subgroups of isometry groups are quasi-isometrically embedded.
This work estimates edge weights of edge-reinforced random walks using observed data.
problem Statistical estimation of edge weights in edge-reinforced random walks.
method Proposes an estimator based on the generalized method of moments using the magic formula and hyperbolic Gaussian structure.
result Analyzes the sample complexity of the proposed estimator.
We propose a new Quantization algorithm for the approximation of inhomogeneous random walks, which are the key terms for the valuation of CDO-tranches in latent factor models. This approach is based on a dual quantization operator which posses an intrinsic stationarity and therefore automatically leads to a second orde…
Continuous time random walks (CTRWs) are used in physics to model anomalous diffusion, by incorporating a random waiting time between particle jumps. In finance, the particle jumps are log-returns and the waiting times measure delay between transactions. These two random variables (log-return and waiting time) are typi…
New proof shows rapid mixing for random walks on nilmanifolds.
problem Proving rapid mixing for random walks on nilmanifolds.
method Proved rapid mixing for almost all random walks generated by m translations on nilmanifolds under mild assumptions.
result For several classical classes of nilmanifolds, m=2 suffices for rapid mixing.
Random walks on hyperbolic spaces show linear growth in translation lengths.
problem Investigate the growth of translation lengths in random walks on hyperbolic spaces.
method Prove linear growth without moment conditions and apply to Teichmüller spaces.
result Linear growth of translation lengths in random walks on hyperbolic spaces.
Study random walks on groups with superlinear divergent geodesics.
problem Existence of superlinear divergent geodesics in groups.
method Developed theory of superlinear divergence and applied Gouëzel's pivoting technique.
result Established a central limit theorem for random walks on groups with superlinear divergent geodesics.
Study random walks on sub-Riemannian manifolds using retractions.
problem Modeling random walks on sub-Riemannian manifolds.
method Use retractions to approximate normal geodesics and study convergence to Brownian motion.
result Convergence of geodesic random walks defined with different connections.
The paper examines random walks on metric spaces and finds commensurable subgroups.
problem Determining commensurable subgroups via stationary measures in metric spaces.
method Analyzing random walks on isometry groups of metric spaces with non-singular stationary measures.
result Subgroups generated by random walks are commensurable under mild conditions.
Random walks on free groups reveal asymmetric expansion factors.
problem Understanding expansion factors in free groups.
method Random walks and BGIP on metric spaces.
result Generic outer automorphisms have different forward and backward expansion factors.
Survey on random walks on mapping class groups and their properties.
problem Understanding random walks on mapping class groups.
method Analyzing actions on Teichmüller spaces and curve complexes.
result Laws of large numbers and central limit theorems for random walks.
Deviation inequalities and limit laws for random walks on metric spaces.
problem Understanding random walks on metric spaces with contracting isometries.
method Adapting Gouëzel's pivotal time construction to establish deviation inequalities.
result Exponential bounds and limit laws for random walks on mapping class groups and CAT(0) spaces.
Random walks on Fuchsian Schottky groups have harmonic measures with lower dimension.
problem Understanding the dimensionality of harmonic measures for random walks.
method Analyzing finite range random walks on Fuchsian Schottky groups.
result Harmonic measures have dimension strictly less than the limit set's Hausdorff dimension.
UniNet efficiently learns network representations from large graphs.
problem Efficiently learning network representations from large graphs.
method Metropolis-Hastings sampling for efficient edge sampling and random walk model abstraction.
result UniNet outperforms existing NRL models on billion-edge networks.
Unified framework for multi-view diffusion geometries using intertwined diffusion trajectories.
problem Constructing multi-view diffusion geometries with flexible view interaction and fusion.
method Intertwined multi-view diffusion trajectories (MDTs) as a class of inhomogeneous diffusion processes.
result Established theoretical properties and derived diffusion distances and embeddings.
Discrete time random walks on a finite set naturally translate via a one-to-one correspondence to discrete Laplace operators. Typically, Ollivier curvature has been investigated via random walks. We first extend the definition of Ollivier curvature to general weighted graphs and then give a strikingly simple representa…
The study of random walks on hyperbolic spaces and Teichmüller spaces, proving central limit theorems and geodesic tracking.
problem Analyzing random walks on hyperbolic and Teichmüller spaces.
method Proving central limit theorems and geodesic tracking using finite moments and logarithmic moments.
result Translation lengths of random isometries satisfy a central limit theorem if and only if the random walk has finite second moment.
Uniform drift estimates found for random walks on graph products.
problem Finding uniform lower bounds on drift for random walks on graph products.
method Extending Gouëzel's argument and introducing the combinatorial notion of piling.
result Uniform lower bounds on the drift for a family of random walks on graph products.
A random Heegaard splitting is a 3-manifold obtained by using a random walk of length n on the mapping class group as the gluing map between two handlebodies. We show that the joint distribution of random walks of length n and their inverses is asymptotically independent, and converges to the product of the harmonic an…
Unified view on random walk and Weisfeiler-Leman kernels, improving accuracy.
problem Improving graph kernel methods for better classification accuracy.
method Define and analyze walk-based node refinement methods, relate to Weisfeiler-Leman test, and introduce new walk-based kernels.
result Walk-based kernels are as expressive as Weisfeiler-Leman subtree kernel but support non-strict neighborhood comparison.
Geodesic walks converge to Brownian motion on Finsler manifolds.
problem Understanding random walks on Finsler manifolds.
method Analyzing convergence of geodesic random walks to diffusion processes.
result The Brownian motion on a Riemannian metric is a key result.
Hypergraphs are used in machine learning to model higher-order relationships in data. While spectral methods for graphs are well-established, spectral theory for hypergraphs remains an active area of research. In this paper, we use random walks to develop a spectral theory for hypergraphs with edge-dependent vertex wei…
We extend some properties of random walks on hyperbolic groups to random walks on convergence groups. In particular we prove that if a convergence group G acts on a compact metrizable space M with the convergence property then we can provide G∪M with a compact topology such that random walks on G converge a…
For any pseudo-Anosov diffeomorphism on a closed orientable surface S of genus greater than one, it is known by the work of Bers and Thurston that the topological entropy agrees with the translation distance on the Teichmüller space with respect to the Teichmüller metric. In this paper, we consider random walks on th…
Repelling random walks improve graph-based sampling efficiency.
problem Efficient graph-based sampling and statistical estimation.
method Induces correlations between trajectories of an ensemble of walkers on a graph, maintaining unbiasedness.
result Improves concentration of statistical estimators on graphs.
Higher-order proximity preserved network embedding has attracted increasing attention. In particular, due to the superior scalability, random-walk-based network embedding has also been well developed, which could efficiently explore higher-order neighborhoods via multi-hop random walks. However, despite the success of …
Abstract: Nonlinear random walk with distributionally robust transition probabilities.
problem Modeling nonlinear random walks with robust transition probabilities.
method Scaling limit and nonlinear semigroup approach.
result Explicit computation of the generator and corresponding PDE.
Study large deviations and speed of random walks in hyperbolic spaces.
problem Understanding the speed of random walks in hyperbolic spaces.
method Large deviations analysis for random walks with a non-elementary semi-group.
result Established large deviations results for random walk distances.
Random walks and polygons are used to model polymers. In this paper we consider the extension of writhe, self-linking number and linking number to open chains. We then study the average writhe, self-linking and linking number of random walks and polygons over the space of configurations as a function of their length. W…