A new model for overlapping communities with arbitrary internal structure

Viktória Vadon (Corresponding author), Júlia Komjáthy, Remco van der Hofstad

Research output: Contribution to journalArticleAcademicpeer-review

5 Citations (Scopus)
67 Downloads (Pure)

Abstract

We introduce the random intersection graph with communities, a new model for networks with overlapping communities with arbitrary internal structure. We construct the model from a list of arbitrary community graphs that are the building blocks, and a separate list of individuals, each with a prescribed number of community membership tokens. Randomness is introduced by matching these tokens uniformly at random to vertices of the community graphs. We then identify the community members assigned to the same individual, thus overlaps arise due to individuals having several tokens. This gives a highly flexible model for networks with community structure. We are able to derive a wide range of analytic results on this model. We derive an asymptotic description of the local structure of the graph, which further yields the asymptotic degree distribution, local clustering coefficient, and results on the overlapping structure of the communities. For the global connectivity structure, we identify a phase transition in the size of the largest component. When the largest component constitutes a positive proportion of the graph, we can further characterize its asymptotic local structure. Finally, we study how the connectivity structure changes under a randomized attack, where we remove edges randomly, according to independent coin flips.

Original languageEnglish
Article number42
Number of pages19
JournalApplied Network Science
Volume4
Issue number1
DOIs
Publication statusPublished - 27 Jun 2019

Keywords

  • Bipartite configuration model
  • Community structure
  • Local weak convergence
  • Overlapping communities
  • Percolation
  • Phase transition
  • Primary 05C80; 60C05; 90B15; 05C82
  • Random networks

Fingerprint

Dive into the research topics of 'A new model for overlapping communities with arbitrary internal structure'. Together they form a unique fingerprint.

Cite this