Publication

Shortest-Weight Paths In Random Regular Graphs

Léo Hamed Amini
2014
Journal Articles

Abstract

Consider a random regular graph with degree d and of size n. Assign to each edge an independent and identically distributed 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 >= 3, we show that the longest of these shortest-weight paths has about (alpha) over cap log n edges, where (alpha) over cap is the unique solution of the equation alpha log (d-2/d-1 alpha) -alpha = d-3/d-2 for alpha > d-1/d-2.

Official source

https://infoscience.epfl.ch/entities/publication/b1d8c6e3-3e4c-4a63-8d27-75d7d8f36296

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Léo Hamed Amini
2014
Journal Articles

Abstract

Official source

https://infoscience.epfl.ch/entities/publication/b1d8c6e3-3e4c-4a63-8d27-75d7d8f36296

About this result

Related concepts (25)

Random graph

In mathematics, random graph is the general term to refer to probability distributions over graphs. Random graphs may be described simply by a probability distribution, or by a random process which generates them. The theory of random graphs lies at the intersection between graph theory and probability theory. From a mathematical perspective, random graphs are used to answer questions about the properties of typical graphs.

Exponential distribution

In probability theory and statistics, the exponential distribution or negative exponential distribution is the probability distribution of the time between events in a Poisson point process, i.e., a process in which events occur continuously and independently at a constant average rate. It is a particular case of the gamma distribution. It is the continuous analogue of the geometric distribution, and it has the key property of being memoryless. In addition to being used for the analysis of Poisson point processes it is found in various other contexts.

Independent and identically distributed random variables

In probability theory and statistics, a collection of random variables is independent and identically distributed if each random variable has the same probability distribution as the others and all are mutually independent. This property is usually abbreviated as i.i.d., iid, or IID. IID was first defined in statistics and finds application in different fields such as data mining and signal processing. Statistics commonly deals with random samples. A random sample can be thought of as a set of objects that are chosen randomly.

Related publications (32)

Shortest-Weight Paths In Random Regular Graphs

Chat with Graph Search

The Power of Two Matrices in Spectral Algorithms for Community Recovery

Random matrix methods for high-dimensional machine learning models

Information Spectrum Converse for Minimum Entropy Couplings and Functional Representations