The impact of degree variability on connectivity properties of large networks

DOI10.1007/978-3-319-26784-5_6zbMATH Open1342.05167arXiv1508.03379OpenAlexW2246550683MaRDI QIDQ3460740FDOQ3460740

Authors:

Publication date: 8 January 2016

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

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.

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

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

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)

Cited In (6)

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

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)