Scale-free graphs with many edges

Clara Stegehuis; Bert Zwart

doi:10.48550/arXiv.2212.05907

Scale-free graphs with many edges

Clara Stegehuis
, Bert Zwart

Mathematics of Operations Research

Research output: Working paper › Preprint › Academic

54 Downloads (Pure)

Abstract

We develop tail estimates for the number of edges in a Chung-Lu random graph with regularly varying weight distribution. Our results show that the most likely way to have an unusually large number of edges is through the presence of one or more hubs, i.e.\ edges with degree $O(n)$.

Original language	English
Publisher	ArXiv.org
DOIs	https://doi.org/10.48550/arXiv.2212.05907
Publication status	Published - 12 Dec 2022

Keywords

math.PR

Access to Document

10.48550/arXiv.2212.05907

ArticleFinal published version, 143 KB

Cite this

@techreport{8f97fce34e7c4929b9b267a8fee7291a,

title = "Scale-free graphs with many edges",

abstract = "We develop tail estimates for the number of edges in a Chung-Lu random graph with regularly varying weight distribution. Our results show that the most likely way to have an unusually large number of edges is through the presence of one or more hubs, i.e.\textbackslash{} edges with degree \$O(n)\$.",

keywords = "math.PR",

author = "Clara Stegehuis and Bert Zwart",

note = "8 pages",

year = "2022",

month = dec,

day = "12",

doi = "10.48550/arXiv.2212.05907",

language = "English",

publisher = "ArXiv.org",

type = "WorkingPaper",

institution = "ArXiv.org",

}

TY - UNPB

T1 - Scale-free graphs with many edges

AU - Stegehuis, Clara

AU - Zwart, Bert

N1 - 8 pages

PY - 2022/12/12

Y1 - 2022/12/12

N2 - We develop tail estimates for the number of edges in a Chung-Lu random graph with regularly varying weight distribution. Our results show that the most likely way to have an unusually large number of edges is through the presence of one or more hubs, i.e.\ edges with degree $O(n)$.

AB - We develop tail estimates for the number of edges in a Chung-Lu random graph with regularly varying weight distribution. Our results show that the most likely way to have an unusually large number of edges is through the presence of one or more hubs, i.e.\ edges with degree $O(n)$.

KW - math.PR

U2 - 10.48550/arXiv.2212.05907

DO - 10.48550/arXiv.2212.05907

M3 - Preprint

BT - Scale-free graphs with many edges

PB - ArXiv.org

ER -

Scale-free graphs with many edges

Abstract

Keywords

Access to Document

Fingerprint

Cite this