Phase transition in random intersection graphs with communities
Remco van der Hofstad (Eindhoven University of Technology)
Júlia Komjáthy (TU Delft - Applied Probability)
Viktória Vadon (University of Miskolc)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
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.
help_outline