Distinguishing power-law uniform random graphs from inhomogeneous random graphs through small subgraphs

DOI10.1007/S10955-022-02884-9zbMATH Open1484.05190arXiv2102.09315OpenAlexW3130470475MaRDI QIDQ2116499FDOQ2116499

Clara Stegehuis

Publication date: 17 March 2022

Published in: Journal of Statistical Physics (Search for Journal in Brave)

Abstract: We investigate the asymptotic number of induced subgraphs in power-law uniform random graphs. We show that these induced subgraphs appear typically on vertices with specific degrees, which are found by solving an optimization problem. Furthermore, we show that this optimization problem allows to design a linear-time, randomized algorithm that distinguishes between uniform random graphs and random graph models that create graphs with approximately a desired degree sequence: the power-law rank-1 inhomogeneous random graph. This algorithm uses the fact that some specific induced subgraphs appear significantly more often in uniform random graphs than in rank-1 inhomogeneous random graphs.

Full work available at URL: https://arxiv.org/abs/2102.09315

zbMATH Keywords

randomized algorithmssubgraphsuniform random graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Randomized algorithms (68W20) Combinatorial probability (60C05)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• A critical point for random graphs with a given degree sequence
• Reducibility among Combinatorial Problems
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• The Probability That a Random Multigraph is Simple
• The average distances in random graphs with given expected degrees
• Generating simple random graphs with prescribed degree distribution
• Large Cliques in a Power-Law Random Graph
• The asymptotic distribution of short cycles in random regular graphs
• Counting triangles in power-law uniform random graphs
• Optimal subgraph structures in scale-free configuration models
• Subgraphs in preferential attachment models
• Subgraph probability of random graphs with specified degrees and applications to chromatic number and connectivity

Cited In (1)

• Asymptotic bounds for clustering problems in random graphs

This page was built for publication: Distinguishing power-law uniform random graphs from inhomogeneous random graphs through small subgraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2116499)