How to determine if a random graph with a fixed degree sequence has a giant component

• 成果类型: Article
• 署名作者: Joos, Felix; Perarnau, Guillem; Rautenbach, Dieter; Reed, Bruce
• 署名单位: University of Birmingham; Ulm University; Centre National de la Recherche Scientifique (CNRS); Research Organization of Information & Systems (ROIS); National Institute of Informatics (NII) - Japan; Instituto Nacional de Matematica Pura e Aplicada (IMPA)
• 刊物名称: PROBABILITY THEORY AND RELATED FIELDS
• ISSN/ISSBN: 0178-8051
• DOI: 10.1007/s00440-017-0757-1
• 发表日期: 2018
• 页码: 263-310
• 关键词: sparse random graphs; complex networks; percolation; phase

摘要

For a fixed degree sequence , let be a uniformly chosen (simple) graph on where the vertex i has degree . In this paper we determine whether has a giant component with high probability, essentially imposing no conditions on . We simply insist that the sum of the degrees in which are not 2 is at least for some function going to infinity with n. This is a relatively minor technical condition, and when does not satisfy it, both the probability that has a giant component and the probability that has no giant component are bounded away from 1.