THE DIAMETER OF WEIGHTED RANDOM GRAPHS

• 成果类型: Article
• 署名作者: Amini, Hamed; Lelarge, Marc
• 署名单位: Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne; Inria
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/14-AAP1034
• 发表日期: 2015
• 页码: 1686-1727
• 关键词: 1st passage percolation; giant component; k-core; paths; times

摘要

In this paper we study the impact of random exponential edge weights on the distances in a random graph and, in particular, on its diameter. Our main result consists of a precise asymptotic expression for the maximal weight of the shortest weight paths between all vertices (the weighted diameter) of sparse random graphs, when the edge weights are i.i.d. exponential random variables.