Scaling properties of paths on graphs

DOI10.13001/1081-3810.1569MaRDI QIDQ5746862zbMATH OpenOpenAlexFDO

Authors Eric Foxall, Theodore J. Perkins, R. Edwards

Publication date 10 February 2014

Published in The Electronic Journal of Linear Algebra (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1306.2917, http://www.math.technion.ac.il/iic/ela/ela-articles/articles/vol23_pp966-988.pdf

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

directed graphsMarkov chainsnon-negative matricesPerron-Frobenius theorypower law scaling

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Paths and cycles (05C38) Positive matrices and their generalizations; cones of matrices (15B48) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10)

Abstract: Let $G$ be a directed graph on finitely many vertices and edges, and assign a positive weight to each edge on $G$. Fix vertices $u$ and $v$ and consider the set of paths that start at $u$ and end at $v$, self-intersecting in any number of places along the way. For each path, sum the weights of its edges, and then list the path weights in increasing order. The asymptotic behaviour of this sequence is described, in terms of the structure and type of strongly connected components on the graph. As a special case, for a Markov chain the asymptotic probability of paths obeys either a power law scaling or a weaker type of scaling, depending on the structure of the transition matrix. This generalizes previous work by Mandelbrot and others, who established asymptotic power law scaling for special classes of Markov chains.

Recommendations

• The Distribution of Path Lengths On Directed Weighted Graphs
• Limit theorems for the maximal path weight in a directed graph on the line with random weights of edges
• Limiting properties of random graph models with vertex and edge weights
• Chain Lengths in Certain Random Directed Graphs
• Convergence to the Tracy-Widom distribution for longest paths in a directed random graph

Cited in

(1)

• Calculation of precise constants in a probability model of Zipf's law generation and asymptotics of sums of multinomial coefficients

This page was built for publication: Scaling properties of paths on graphs

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