Giant Component in Random Multipartite Graphs with Given Degree Sequences

Original · EN

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ᵢᵈ(n) which denotes the number of vertices in part i of the multipartite graph with degree given by the vector d. 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.