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

Felix Joos, Guillem Perarnau, Dieter Rautenbach, Bruce Reed

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Citations (Scopus)

Abstract

The traditional Erdos-Renyi model of a random network is of little use in modelling the type of complex networks which modern researchers study. In this graph, every pair of vertices is equally likely to be connected by an edge. However, 21st century networks are of diverse nature and usually exhibit inhomogeneity among their nodes. This motivates the study, for a fixed degree sequence D=(d1,..., dn), of a uniformly chosen simple graph G(D) on {1,..., n} where the vertex i has degree di. In this paper, we study the existence of a giant component in G(D). A heuristic argument suggests that a giant component in G(D) will exist provided that the sum of the squares of the degrees is larger than twice the sum of the degrees. In 1995, Molloy and Reed essentially proved this to be the case when the degree sequence D under consideration satisfies certain technical conditions [Random Structures & Algorithms, 6:161-180]. This work has attracted considerable attention, has been extended to degree sequences under weaker conditions and has been applied to random models of a wide range of complex networks such as the World Wide Web or biological systems operating at a sub-molecular level. Nevertheless, the technical conditions on D restrict the applicability of the result to sequences where the vertices of high degree play no important role. This is a major problem since it is observed in many real-world networks, such as scale-free networks, that vertices of high degree (the so-called hubs) are present and play a crucial role. In this paper we characterize when a uniformly random graph with a fixed degree sequence has a giant component. Our main result holds for every degree sequence of length n provided that a minor technical condition is satisfied. The typical structure of G(D) when D does not satisfy this condition is relatively simple and easy to understand. Our result gives a unified criterion that implies all the known results on the existence of a giant component in G(D), including both the generalizations of the Molloy-Reed result and results on more restrictive models. Moreover, it turns out that the heuristic argument used in all the previous works on the topic, does not extend to general degree sequences.

Original languageEnglish
Title of host publication2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS)
PublisherIEEE Computer Society
Pages695-703
Number of pages9
Volume2016-December
ISBN (Electronic)978-1-5090-3933-3
ISBN (Print)978-1-5090-3934-0 (PoD)
DOIs
Publication statusPublished - 14 Dec 2016
Event57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016 - New Brunswick, United States
Duration: 9 Oct 201611 Oct 2016

Publication series

NameSymposium on Foundations of Computer Science. Annual Proceedings
PublisherIEEE Computer Society
ISSN (Print)1523-8288

Conference

Conference57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016
Country/TerritoryUnited States
CityNew Brunswick
Period9/10/1611/10/16

Keywords

  • Complex networks
  • Degree sequences
  • Giant component
  • Random graphs

ASJC Scopus subject areas

  • Computer Science(all)

Fingerprint

Dive into the research topics of 'How to determine if a random graph with a fixed degree sequence has a giant component'. Together they form a unique fingerprint.

Cite this