TY - GEN
T1 - How to determine if a random graph with a fixed degree sequence has a giant component
AU - Joos, Felix
AU - Perarnau, Guillem
AU - Rautenbach, Dieter
AU - Reed, Bruce
PY - 2016/12/14
Y1 - 2016/12/14
N2 - 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.
AB - 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.
KW - Complex networks
KW - Degree sequences
KW - Giant component
KW - Random graphs
UR - http://www.scopus.com/inward/record.url?scp=85009371839&partnerID=8YFLogxK
U2 - 10.1109/FOCS.2016.79
DO - 10.1109/FOCS.2016.79
M3 - Conference contribution
AN - SCOPUS:85009371839
SN - 978-1-5090-3934-0 (PoD)
VL - 2016-December
T3 - Symposium on Foundations of Computer Science. Annual Proceedings
SP - 695
EP - 703
BT - 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS)
PB - IEEE Computer Society
T2 - 57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016
Y2 - 9 October 2016 through 11 October 2016
ER -