Book embedding of complex network with community structure

摘要

Community structure provides useful information for understanding the organization structure of a network and the interaction between different functional modules, as a result, it has been a hot research topic in the study of complex network. In graph theory, a complex network with a community structure is a stochastic block model (SBM). The stochastic block model is a generative model for random graph, and it is widely used in daily life. The book embedding plays an important role in computer science. The main purpose of this paper is to give the book embedding of the stochastic block model by Lovász Local Lemma. This is the first work about book embedding of random graph, and the difference between the upper and lower bounds of the page number of G∈G(n,k,p,q) is only one if p=1.