Phase transition in random intersection graphs with communities. Issue 3 (14th December 2021)

• Record Type: Journal Article
• Authors: van der Hofstad, Remco; Komjáthy, Júlia; Vadon, Viktória
• Is Part Of: Random structures & algorithms. Volume 60:Issue 3(2022)
• Page Start: 406
• Page End: 461
• Publication Date: 2021-12-14
• Subjects: bipartite configuration model -- community structure -- overlapping communities -- percolation -- phase transition -- random intersection graphs -- random networks; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.21063
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: The "random intersection graph with communities" (RIGC) models networks with communities, assuming an underlying bipartite structure of groups and individuals. Each group has its own internal structure described by a (small) graph, while groups may overlap. The group memberships are generated by a bipartite configuration model. The model generalizes the classical random intersection graph model, a special case where each community is a complete graph. The RIGC model is analytically tractable. We prove a phase transition in the size of the largest connected component in terms of the model parameters. We prove that percolation on RIGC produces a graph within the RIGC family, also undergoing a phase transition with respect to size of the largest component. Our proofs rely on the connection to the bipartite configuration model. Our related results on the bipartite configuration model are of independent interest, since they shed light on interesting differences from the unipartite case.