The impact of degree variability on connectivity properties of large networks

DOI10.1007/978-3-319-26784-5_6MaRDI QIDQ3460740zbMATH OpenOpenAlexFDO

Authors

Publication date 8 January 2016

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1508.03379

zbMATH Keywords

stochastic comparisonsconfiguration modellength-biased distributionsize-biased distributionweighted distributionconvex stochastic order

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Distance in graphs (05C12) Connectivity (05C40)

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.

Recommendations

• The largest component in a subcritical random graph with a power law degree distribution
• The effect of random edge removal on network degree sequence
• The Size of the Largest Strongly Connected Component of a Random Digraph with a Given Degree Sequence
• Degree sequence of configuration model with vertex faults
• Limit theorems for the average distance and the degree distribution of the threshold network model

Cited in

(6)

• The tail does not determine the size of the giant
• The adaptive coupling scheme and the heterogeneity in intrinsic frequency and degree distributions of the complex networks
• Contextual analysis of the bipolar structures connectivity
• A study on the relationship between connecting different types of nodes and disassortativity by degree
• First passage percolation on sparse random graphs with boundary weights
• Connectivity of random graphs after centrality-based vertex removal

This page was built for publication: The impact of degree variability on connectivity properties of large networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3460740)