A new model for overlapping communities with arbitrary internal structure

Research output: Contribution to journalArticleAcademicpeer-review

20 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

Fingerprint

Overlapping
Internal
Arbitrary
Local Structure
Graph in graph theory
Model
Connectivity
Phase transitions
Clustering Coefficient
Intersection Graphs
Community Structure
Degree Distribution
Flip
Community
Random Graphs
Randomness
Building Blocks
Asymptotic distribution
Overlap
Proportion

Keywords

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

Cite this

@article{2489219d41c74dfa8ddba0aff2e6ab05,
title = "A new model for overlapping communities with arbitrary internal structure",
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.",
keywords = "Bipartite configuration model, Community structure, Local weak convergence, Overlapping communities, Percolation, Phase transition, Primary 05C80; 60C05; 90B15; 05C82, Random networks",
author = "Vikt{\'o}ria Vadon and J{\'u}lia Komj{\'a}thy and {van der Hofstad}, Remco",
year = "2019",
month = "6",
day = "27",
doi = "10.1007/s41109-019-0149-9",
language = "English",
volume = "4",
journal = "Applied Network Science",
issn = "2364-8228",
publisher = "Springer",
number = "1",

}

A new model for overlapping communities with arbitrary internal structure. / Vadon, Viktória (Corresponding author); Komjáthy, Júlia; van der Hofstad, Remco.

In: Applied Network Science, Vol. 4, No. 1, 42, 27.06.2019.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - A new model for overlapping communities with arbitrary internal structure

AU - Vadon, Viktória

AU - Komjáthy, Júlia

AU - van der Hofstad, Remco

PY - 2019/6/27

Y1 - 2019/6/27

N2 - 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.

AB - 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.

KW - Bipartite configuration model

KW - Community structure

KW - Local weak convergence

KW - Overlapping communities

KW - Percolation

KW - Phase transition

KW - Primary 05C80; 60C05; 90B15; 05C82

KW - Random networks

UR - http://www.scopus.com/inward/record.url?scp=85068027820&partnerID=8YFLogxK

U2 - 10.1007/s41109-019-0149-9

DO - 10.1007/s41109-019-0149-9

M3 - Article

AN - SCOPUS:85068027820

VL - 4

JO - Applied Network Science

JF - Applied Network Science

SN - 2364-8228

IS - 1

M1 - 42

ER -