Normal and stable approximation to subgraph counts in superpositions of Bernoulli random graphs

Mindaugas Bloznelis*, Joona Karjalainen*, Lasse Leskelä*

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

1 Citation (Scopus)

Abstract

Real networks often exhibit clustering, the tendency to form relatively small groups of nodes with high edge densities. This clustering property can cause large numbers of small and dense subgraphs to emerge in otherwise sparse networks. Subgraph counts are an important and commonly used source of information about the network structure and function. We study probability distributions of subgraph counts in a community affiliation graph. This is a random graph generated as an overlay of m partly overlapping independent Bernoulli random graphs (layers) G1,…,Gm with variable sizes and densities. The model is parameterised by a joint distribution of layer sizes and densities. When m grows linearly in the number of nodes n, the model generates sparse random graphs with a rich statistical structure, admitting a nonvanishing clustering coefficient and a power-law limiting degree distribution. In this paper we establish the normal and alpha -stable approximations to the numbers of small cliques, cycles, and more general 2-connected subgraphs of a community affiliation graph.

Original languageEnglish
JournalJournal of Applied Probability
DOIs
Publication statusE-pub ahead of print - 18 Aug 2023
MoE publication typeA1 Journal article-refereed

Keywords

  • affiliation network
  • clustering
  • complex network
  • Erdös-Rényi graph
  • normal approximation
  • overlapping communities
  • power law
  • random intersection graph
  • Subgraph count

Fingerprint

Dive into the research topics of 'Normal and stable approximation to subgraph counts in superpositions of Bernoulli random graphs'. Together they form a unique fingerprint.

Cite this