Connectivity of a general class of inhomogeneous random digraphs

DOI10.1002/RSA.20892zbMATH Open1453.82005arXiv1712.03319OpenAlexW2982586439MaRDI QIDQ5113954FDOQ5113954

Junyu Cao, Mariana Olvera-Cravioto

Publication date: 19 June 2020

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

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.

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

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

zbMATH Keywords

scale-free graphsmultitype branching processescouplingsinhomogeneous random graphsrandom digraphskernel-based random 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)

Cited In (11)

• Connectivity of Poissonian inhomogeneous random multigraphs
• Efficient presolving methods for the influence maximization problem
• Universality for the directed configuration model: metric space convergence of the strongly connected components at criticality
• Giant components in three-parameter random directed graphs
• SIR model for households
• The Size of the Largest Strongly Connected Component of a Random Digraph with a Given Degree Sequence
• Connectedness of graphs generated by a random d-process
• Modeling household effects in epidemics
• The limiting probability that \(\alpha\)-in, \(\beta\)-out is strongly connected
• Local weak convergence for PageRank
• PageRank's behavior under degree correlations

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)