Anzeige
Erschienen in:
2015 | OriginalPaper | Buchkapitel
The Impact of Degree Variability on Connectivity Properties of Large Networks
verfasst von : Lasse Leskelä, Hoa Ngo
Erschienen in: Algorithms and Models for the Web Graph
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
The goal of this work 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.