The impact of degree variability on connectivity properties of large networks
- Long version (24 pages)
- Internet Mathematics 13, 2017
- Short version (12 pages)
- 12th Workshop on Algorithms and Models for the Web Graph (WAW) 2015
- Lecture Notes in Computer Science 9479, pp. 66–77, Springer 2015
- doi:10.1007/978-3-319-26784-5
Abstract
The goal of is to study how increased variability in the degree distribution impacts the global connectivity properties of a large network. We approach this question by modeling the network as a uniform random graph with a given degree sequence. We analyze the effect of the degree variability on the approximate size of the largest connected component using stochastic ordering techniques. A counterexample shows that a higher degree variability may lead to a larger connected component, contrary to basic intuition about branching processes. When certain extremal cases are ruled out, the higher degree variability is shown to decrease the limiting approximate size of the largest connected component.