(2022). Survey on Sparse Graph Limits + A Toy Example. The Simons Institute for the Theory of Computing. https://old.simons.berkeley.edu/node/22616
MLA
Survey on Sparse Graph Limits + A Toy Example. The Simons Institute for the Theory of Computing, Sep. 30, 2022, https://old.simons.berkeley.edu/node/22616
BibTex
@misc{ scivideos_22616,
doi = {},
url = {https://old.simons.berkeley.edu/node/22616},
author = {},
keywords = {},
language = {en},
title = {Survey on Sparse Graph Limits + A Toy Example},
publisher = {The Simons Institute for the Theory of Computing},
year = {2022},
month = {sep},
note = {22616 see, \url{https://scivideos.org/simons-institute/22616}}
}
Abstract
The theory of graph limits is an important tool in understanding properties of large networks. We begin the talk with a survey of this theory, concentrating in particular on the sparse setting. We then investigate a power-law random graph model and cast it in the sparse graph limit theory framework. The distinctively different structures of the limit graph are explored in detail in the sub-critical and super-critical regimes. In the sub-critical regime, the graph is empty with high probability, and in the rare event that it is non-empty, it consists of a single edge. Contrarily, in the super-critical regime, a non-trivial random graph exists in the limit, and it serves as an uncovered boundary case between different types of graph convergence.