Connectivity of inhomogeneous random graphs

DOI10.1002/RSA.20490MaRDI QIDQ2930053zbMATH OpenOpenAlexWikidataFDO

Authors Nicolas Fraiman, Luc Devroye

Publication date 17 November 2014

Published in Random Structures \& Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

connectivityinhomogeneous random graphrandom graph

Mathematics Subject Classification ID

Connectivity (05C40) Density (toughness, etc.) (05C42) Random graphs (graph-theoretic aspects) (05C80)

Abstract: We find conditions for the connectivity of inhomogeneous random graphs with intermediate density. Our results generalize the classical result for G(n, p), when p = c log n/n. We draw n independent points X_i from a general distribution on a separable metric space, and let their indices form the vertex set of a graph. An edge (i,j) is added with probability min(1, K(X_i,X_j) log n/n), where K ge 0 is a fixed kernel. We show that, under reasonably weak assumptions, the connectivity threshold of the model can be determined.

Recommendations

• Connectivity of Poissonian inhomogeneous random multigraphs
• The diameter of inhomogeneous random graphs
• Connectivity for a modified binomial random graph by agglomeration
• Sparse graphs: metrics and random models
• Metrics for sparse graphs

Cites work

• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
• Concentration Inequalities and Martingale Inequalities: A Survey
• Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
• Convergent sequences of dense graphs. II. Multiway cuts and statistical physics
• Limits of dense graph sequences
• Percolation on dense graph sequences
• Probability Inequalities for Sums of Bounded Random Variables
• Random Plane Networks
• The longest edge of the random minimal spanning tree
• The phase transition in inhomogeneous random graphs

Cited in

(25)

• Generalized random dot product graph
• Evolution of a modified binomial random graph by agglomeration
• Mixed connectivity properties of random graphs and some special graphs
• The Fréchet mean of inhomogeneous random graphs
• Cliques in rank-1 random graphs: the role of inhomogeneity
• Nonparametric statistics of dynamic networks with distinguishable nodes
• Connectivity for a modified binomial random graph by agglomeration
• Zero-One Laws for Connectivity in Inhomogeneous Random Key Graphs
• The random connection model: Connectivity, edge lengths, and degree distributions
• Connectivity of random k-nearest-neighbour graphs
• The diameter of inhomogeneous random graphs
• Inhomogeneous random graphs, isolated vertices, and Poisson approximation
• The natural connectivity of colored random graphs
• Sparse graphs: metrics and random models
• The coupling method for inhomogeneous random intersection graphs.
• On connectivity and robustness of random graphs with inhomogeneity
• A large-deviations principle for all the components in a sparse inhomogeneous random graph
• Scaling of the clustering function in spatial inhomogeneous random graphs
• Connectivity of Poissonian inhomogeneous random multigraphs
• Random minimum spanning tree and dense graph limits
• Gaussian fluctuations of generalized U-statistics and subgraph counting in the binomial random-connection model
• Normal to Poisson phase transition for subgraph counting in the random-connection model
• Connectivity threshold for superpositions of Bernoulli random graphs
• Inhomogeneous random graphs with infinite-mean fitness variables
• Limiting spectra of inhomogeneous random graphs

This page was built for publication: Connectivity of inhomogeneous random graphs

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