Skip to content
DraconiticResearch
Search Sources API
182,549 studies31 sourcesUpdated 10 min ago
PreprintarXiv licencearXiv

Tests of graph homogeneity, subgraph counts, and quasirandomness

  • Rudolf Grübel
Open at sourcePDFDOICite

Abstract

Homogeneous random graphs, also known as Erd{\H os}-Rényi graphs, are a subset of the family of dense random graphs, specified by a graphon. We analyze several goodness-of-fit tests for these models that are based on subgraph counts. To obtain the limiting null distribution of the test statistics we use a decomposition of graph functionals, which reveals a cancellation effect. Motivated by a quasirandomness result we obtain a test that is consistent against all alternatives, and we use two popular parametric subfamilies to evaluate the other tests. The theoretical results refer to the limit n→ ∞ of the size n of the graph, the behavior for finite n is illustrated by simulations.

Related

  1. Quasirandomness from balanced and repeated subgraph counts
    Guoqing Wang, Linlin Wang, Jun Yue
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  2. Normal approximation for subgraph counts in random intersection graphs: the case of cliques
    Katarzyna Rybarczyk, Grzegorz Serafin
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  3. Exact Realization of Edge and Induced Three-Vertex Subgraph Counts
    Hillel Schein
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsProbabilityarXiv
  4. Fluctuations of subgraph counts in exponential random graphs
    Hui-Lin Liu, Song-Hao Liu, Dawei Lu
    arXivPreprintarXiv licenceFull textProbabilityarXiv
  5. Transposition Cayley Spectra and Subgraph Counts
    Boris Shapiro
    arXivPreprintCC BY 4.0Full textAlgebra & number theoryCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{grubel2026tests,
  title = {{Tests of graph homogeneity, subgraph counts, and quasirandomness}},
  author = {Rudolf Grübel},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.02214},
  eprint = {2609.02214},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.02214},
}
RIS
TY  - UNPB
TI  - Tests of graph homogeneity, subgraph counts, and quasirandomness
AU  - Rudolf Grübel
PY  - 2026
DA  - 2026/09/02
PB  - arXiv
DO  - 10.48550/arxiv.2609.02214
UR  - https://arxiv.org/abs/2609.02214
AB  - Homogeneous random graphs, also known as Erd{\H os}-Rényi graphs, are a subset of the family of dense random graphs, specified by a graphon. We analyze several goodness-of-fit tests for these models that are based on subgraph counts. To obtain the limiting null distribution of the test statistics we use a decomposition of graph functionals, which reveals a cancellation effect. Motivated by a quasirandomness result we obtain a test that is consistent against all alternatives, and we use two popular parametric subfamilies to evaluate the other tests. The theoretical results refer to the limit n→ ∞ of the size n of the graph, the behavior for finite n is illustrated by simulations.
ER  -