Limiting properties of random graph models with vertex and edge weights

Foss, Sergey and Konstantopoulos, Takis (2018) Limiting properties of random graph models with vertex and edge weights. Journal of Statistical Physics, 173 (3-4). pp. 626-648.

Access the full-text of this item by clicking on the Open Access link.

Official URL: https://link.springer.com/article/10.1007%2Fs10955...

Abstract

This paper provides an overview of results, concerning longest or heaviest paths, in the area of random directed graphs on the integers along with some extensions. We study first-order asymptotics of heaviest paths allowing weights both on edges and vertices and assuming that weights on edges are signed. We aim at an exposition that summarizes, simplifies, and extends proof ideas. We also study sparse graph asymptotics, showing convergence of the weighted random graphs to a certain weighted graph that can be constructed in terms of Poisson processes. We are motivated by numerous applications, ranging from ecology to parallel computing model. It is the latter set of applications that necessitates the introduction of vertex weights. Finally, we discuss some open problems and research directions.

Item Type:	Article
Uncontrolled Keywords:	math.PR, math.PR
Depositing User:	Symplectic Admin
Date Deposited:	26 Nov 2018 15:43
Last Modified:	19 Jan 2023 01:11
DOI:	10.1007/s10955-018-2080-3
Open Access URL:	https://link.springer.com/content/pdf/10.1007/s109...
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3029070