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.

Review text

This paper studies connectivity of inhomogeneous random graphs with intermediate density. Given a separable metric space \(S\) and a Borel probability measure \(\mu\), the random graph has vertex set \([n]\) and edge set \(\{(i,j)\}\) with each pair \((i,j)\) appearing with probability \(\min\{1,\kappa(X_i,X_j)\log n/n\}\). Here, the \(X_i\)s are independent \(\mu\)-distributed random variables on \(S\), and \(\kappa\in L^1(S\times S,\mu\otimes\mu)\) is a non-negative symmetric integrable kernel. The connectivity threshold of the model is presented under some conditions.

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)