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

    2 Citations (Scopus)
    51 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