Limiting Properties of Random Graph Models with Vertex and Edge Weights

Sergey Foss, Takis Konstantopoulos

Research output: Contribution to journalArticle

17 Downloads (Pure)

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 models. It is the latter set of applications that necessitates the introduction of vertex weights. Finally, we discuss some open problems and research directions.

Original languageEnglish
Pages (from-to)626-643
Number of pages18
JournalJournal of Statistical Physics
Volume173
Issue number3-4
Early online date2 Jul 2018
DOIs
Publication statusPublished - Nov 2018

Keywords

  • Limit theorems
  • Random graphs
  • Stochastic networks

ASJC Scopus subject areas

  • Statistical and Nonlinear Physics
  • Mathematical Physics

Fingerprint Dive into the research topics of 'Limiting Properties of Random Graph Models with Vertex and Edge Weights'. Together they form a unique fingerprint.

  • Cite this