Phase transition in random intersection graphs with communities

Remco van der Hofstad, Júlia Komjáthy*, Viktória Vadon

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

11 Downloads (Pure)

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.

Original languageEnglish
Pages (from-to)406-461
Number of pages56
JournalRandom Structures and Algorithms
Volume60 (2022)
Issue number3
DOIs
Publication statusPublished - 2021

Keywords

  • bipartite configuration model
  • community structure
  • overlapping communities
  • percolation
  • phase transition
  • random intersection graphs
  • random networks

Fingerprint

Dive into the research topics of 'Phase transition in random intersection graphs with communities'. Together they form a unique fingerprint.

Cite this