The Distribution of Path Lengths On Directed Weighted Graphs

DOI10.1007/978-3-030-31531-3_20MaRDI QIDQ5118023zbMATH OpenOpenAlexFDO

Authors Avner Kiro, Yotam Smilansky, Uzy Smilansky

Publication date 26 August 2020

Published in Analysis as a Tool in Mathematical Physics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1608.00150

zbMATH Keywords

directed weighted graphspath counting functions

Mathematics Subject Classification ID

Distance in graphs (05C12) Signed and weighted graphs (05C22) Paths and cycles (05C38) Random walks on graphs (05C81)

Abstract: We consider directed weighted graphs and define various families of path counting functions. Our main results are explicit formulas for the main term of the asymptotic growth rate of these counting functions, under some irrationality assumptions on the lengths of all closed orbits on the graph. In addition we assign transition probabilities to such graphs and compute statistics of the corresponding random walks. Some examples and applications are reviewed.

Recommendations

• Limit theorems for the maximal path weight in a directed graph on the line with random weights of edges
• scientific article; zbMATH DE number 19201
• On Shortest Paths in Graphs with Random Weights
• Distributions on graphs and walks
• Shortest paths in random weighted graphs
• On the distribution of typical shortest-path lengths in connected random geometric graphs
• Shortest-weight paths in random regular graphs
• The statistics of random directed graphs
• The diameter of weighted random graphs
• Directed random graphs with given degree distributions

Cites work

• scientific article; zbMATH DE number 3138903 (Why is no real title available?)
• scientific article; zbMATH DE number 5356244 (Why is no real title available?)
• scientific article; zbMATH DE number 49597 (Why is no real title available?)
• scientific article; zbMATH DE number 3565828 (Why is no real title available?)
• A simple condition for bounded displacement
• An analogue of the prime number theorem for closed orbits of Axiom A flows
• An analogue of the prime number theorem for closed orbits of shifts of finite type and their suspensions
• Aperiodic order. Volume 1. A mathematical invitation
• Degeneracies in the length spectra of metric graphs
• Delay-time distribution in the scattering of time-narrow wave packets. I.
• Delay-time distribution in the scattering of time-narrow wave packets. II: Quantum graphs
• Entropies and spectra
• Matrix Analysis
• Multiplicative number theory. I. Classical theory
• Multiscale substitution tilings
• Non-Archimedean equidistribution and group actions on trees
• Non-negative matrices and Markov chains. 2nd ed
• Orbit counting in conjugacy classes for free groups acting on trees
• Some generalizations of the pinwheel tiling
• Substitution tilings and separated nets with similarities to the integer lattice

Cited in

(12)

• scientific article; zbMATH DE number 3961654 (Why is no real title available?)
• THE AVERAGE WEIGHTED PATH LENGTH FOR A CLASS OF HIERARCHICAL NETWORKS
• Path counting on simple graphs: from escape to localization
• Statistics and gap distributions in random Kakutani partitions and multiscale substitution tilings
• The total acquisition number of the randomly weighted path
• Scaling properties of paths on graphs
• Successive shortest paths in complete graphs with random edge weights
• Continuous-time multidimensional walks as an integrable model
• Exponential growth rate of paths and its connection with dynamics
• An FPTAS for Computing the Distribution Function of the Longest Path Length in DAGs with Uniformly Distributed Edge Lengths
• Impulsive processes on the weighted directed graphs
• Uniform distribution of Kakutani partitions generated by substitution schemes

This page was built for publication: The Distribution of Path Lengths On Directed Weighted Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5118023)