Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userShortest Path through Random Points
108
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Let $(M,g_1)$ be a complete $d$-dimensional Riemannian manifold for $d > 1$. Let $mathcal X_n$ be a set of $n$ sample points in $M$ drawn randomly from a smooth Lebesgue density $f$ supported in $M$. Let $x,y$ be two points in $M$. We prove that the normalized length of the power-weighted shortest path between $x, y$ through $mathcal X_n$ converges almost surely to a constant multiple of the Riemannian distance between $x,y$ under the metric tensor $g_p = f^{2(1-p)/d} g_1$, where $p > 1$ is the power parameter.
rate research
Read More
Consider a random regular graph with degree $d$ and of size $n$. Assign to each edge an i.i.d. exponential random variable with mean one. In this paper we establish a precise asymptotic expression for the maximum number of edges on the shortest-weight paths between a fixed vertex and all the other vertices, as well as between any pair of vertices. Namely, for any fixed $d geq 3$, we show that the longest of these shortest-weight paths has about $hat{alpha}log n$ edges where $hat{alpha}$ is the unique solution of the equation $alpha log(frac{d-2}{d-1}alpha) - alpha = frac{d-3}{d-2}$, for $alpha > frac{d-1}{d-2}$.
Given a `cost functional $F$ on paths $gamma$ in a domain $Dsubsetmathbb{R}^d$, in the form $F(gamma) = int_0^1 f(gamma(t),dotgamma(t))dt$, it is of interest to approximate its minimum cost and geodesic paths. Let $X_1,ldots, X_n$ be points drawn independently from $D$ according to a distribution with a density. Form a random geometric graph on the points where $X_i$ and $X_j$ are connected when $0<|X_i - X_j|<epsilon$, and the length scale $epsilon=epsilon_n$ vanishes at a suitable rate. For a general class of functionals $F$, associated to Finsler and other distances on $D$, using a probabilistic form of Gamma convergence, we show that the minimum costs and geodesic paths, with respect to types of approximating discrete `cost functionals, built from the random geometric graph, converge almost surely in various senses to those corresponding to the continuum cost $F$, as the number of sample points diverges. In particular, the geodesic path convergence shown appears to be among the first results of its kind.
This paper is concerned with the existence of multiple points of Gaussian random fields. Under the framework of Dalang et al. (2017), we prove that, for a wide class of Gaussian random fields, multiple points do not exist in critical dimensions. The result is applicable to fractional Brownian sheets and the solutions of systems of stochastic heat and wave equations.
We consider vector fixed point (FP) equations in large dimensional spaces involving random variables, and study their realization-wise solutions. We have an underlying directed random graph, that defines the connections between various components of the FP equations. Existence of an edge between nodes i, j implies the i th FP equation depends on the j th component. We consider a special case where any component of the FP equation depends upon an appropriate aggregate of that of the random neighbor components. We obtain finite dimensional limit FP equations (in a much smaller dimensional space), whose solutions approximate the solution of the random FP equations for almost all realizations, in the asymptotic limit (number of components increase). Our techniques are different from the traditional mean-field methods, which deal with stochastic FP equations in the space of distributions to describe the stationary distributions of the systems. In contrast our focus is on realization-wise FP solutions. We apply the results to study systemic risk in a large financial heterogeneous network with many small institutions and one big institution, and demonstrate some interesting phenomenon.
We present two complementary analytical approaches for calculating the distribution of shortest path lengths in Erdos-Renyi networks, based on recursion equations for the shells around a reference node and for the paths originating from it. The results are in agreement with numerical simulations for a broad range of network sizes and connectivities. The average and standard deviation of the distribution are also obtained. In the case that the mean degree scales as $N^{alpha}$ with the network size, the distribution becomes extremely narrow in the asymptotic limit, namely almost all pairs of nodes are equidistant, at distance $d=lfloor 1/alpha rfloor$ from each other. The distribution of shortest path lengths between nodes of degree $m$ and the rest of the network is calculated. Its average is shown to be a monotonically decreasing function of $m$, providing an interesting relation between a local property and a global property of the network. The methodology presented here can be applied to more general classes of networks.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
