Giant component in random multipartite graphs with given degree sequences

DOI10.1214/13-SSY135MaRDI QIDQ3466715zbMATH OpenFDO

Authors David Gamarnik, Sidhant Misra

Publication date 25 January 2016

Full work available at URL https://arxiv.org/abs/1306.0597, https://projecteuclid.org/euclid.ssy/1450879458

zbMATH Keywords

degree sequencesgiant componentrandom graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Branching processes (Galton-Watson, birth-and-death, etc.) (60J80)

Abstract: We study the problem of the existence of a giant component in a random multipartite graph. We consider a random multipartite graph with $p$ parts generated according to a given degree sequence $n_i^{mathbfd}(n)$ which denotes the number of vertices in part $i$ of the multipartite graph with degree given by the vector $mathbfd$. We assume that the empirical distribution of the degree sequence converges to a limiting probability distribution. Under certain mild regularity assumptions, we characterize the conditions under which, with high probability, there exists a component of linear size. The characterization involves checking whether the Perron-Frobenius norm of the matrix of means of a certain associated edge-biased distribution is greater than unity. We also specify the size of the giant component when it exists. We use the exploration process of Molloy and Reed combined with techniques from the theory of multidimensional Galton-Watson processes to establish this result.

Recommendations

• A new approach to the giant component problem
• The Size of the Giant Component of a Random Graph with a Given Degree Sequence
• The Critical Phase for Random Graphs with a Given Degree Sequence
• How to determine if a random graph with a fixed degree sequence has a giant component
• A general critical condition for the emergence of a giant component in random graphs with given degrees

Cites work

• A critical point for random graphs with a given degree sequence
• A Limit Theorem for Multidimensional Galton-Watson Processes
• A new approach to the giant component problem
• An old approach to the giant component problem
• Differential equations for random processes and random graphs
• Directed random graphs with given degree distributions
• Distances in random graphs with finite mean and infinite variance degrees
• Distances in random graphs with finite variance degrees
• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 3904630 (Why is no real title available?)
• Social and economic networks.
• The asymptotic number of labeled graphs with given degree sequences
• The Critical Phase for Random Graphs with a Given Degree Sequence
• The phase transition in inhomogeneous random graphs
• The phase transition in the configuration model
• The Size of the Giant Component of a Random Graph with a Given Degree Sequence

Cited in

(10)

• Connected components in random graphs with given expected degree sequences
• Giant components in random graphs
• The order of the giant component of random hypergraphs
• A new approach to the giant component problem
• scientific article; zbMATH DE number 1361486 (Why is no real title available?)
• The component sizes of a critical random graph with given degree sequence
• Pandemic spread in communities via random graphs
• On local weak limit and subgraph counts for sparse random graphs
• scientific article; zbMATH DE number 7651057 (Why is no real title available?)
• How to determine if a random graph with a fixed degree sequence has a giant component

This page was built for publication: Giant component in random multipartite graphs with given degree sequences

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