Connectivity of a general class of inhomogeneous random digraphs

DOI10.1002/RSA.20892MaRDI QIDQ5113954zbMATH OpenOpenAlexFDO

Authors Junyu Cao, Mariana Olvera-Cravioto

Publication date 19 June 2020

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

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

zbMATH Keywords

couplingsinhomogeneous random graphskernel-based random graphsmultitype branching processesrandom digraphsscale-free graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20) Phase transitions (general) in equilibrium statistical mechanics (82B26)

Abstract: We study a family of directed random graphs whose arcs are sampled independently of each other, and are present in the graph with a probability that depends on the attributes of the vertices involved. In particular, this family of models includes as special cases the directed versions of the Erdos-Renyi model, graphs with given expected degrees, the generalized random graph, and the Poissonian random graph. We establish the phase transition for the existence of a giant strongly connected component and provide some other basic properties, including the limiting joint distribution of the degrees and the mean number of arcs. In particular, we show that by choosing the joint distribution of the vertex attributes according to a multivariate regularly varying distribution, one can obtain scale-free graphs with arbitrary in-degree/out-degree dependence.

Recommendations

• Birth of a strongly connected giant in an inhomogeneous random digraph
• The Size of the Largest Strongly Connected Component of a Random Digraph with a Given Degree Sequence
• scientific article; zbMATH DE number 4029600
• The phase transition in inhomogeneous random graphs
• The strong giant in a random digraph

Cited in

(19)

• On the degree properties of generalized random graphs
• Local weak convergence for PageRank
• PageRank's behavior under degree correlations
• Large dicliques in a directed inhomogeneous random graph
• Birth of a strongly connected giant in an inhomogeneous random digraph
• Giant components in three-parameter random directed graphs
• Connectedness of graphs generated by a random d-process
• The Size of the Largest Strongly Connected Component of a Random Digraph with a Given Degree Sequence
• A classification of isomorphism-invariant random digraphs
• A note on thresholds and connectivity in random directed graphs
• Efficient presolving methods for the influence maximization problem
• Connectivity of Poissonian inhomogeneous random multigraphs
• Universality for the directed configuration model: metric space convergence of the strongly connected components at criticality
• SIR model for households
• Modeling household effects in epidemics
• From inhomogeneous random digraphs to random graphs with fixed arc counts
• Inter-city infections and the role of size heterogeneity in containment strategies
• Mixing cutoff for simple random walks on the Chung-Lu digraph
• The limiting probability that \(\alpha\)-in, \(\beta\)-out is strongly connected

This page was built for publication: Connectivity of a general class of inhomogeneous random digraphs

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