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

DOI10.1007/S10955-022-02884-9MaRDI QIDQ2116499zbMATH OpenOpenAlexFDO

Authors Clara Stegehuis

Publication date 17 March 2022

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

Copyright license Creative Commons Attribution 4.0 International

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)

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.

Recommendations

• Finding Induced Subgraphs in Scale-Free Inhomogeneous Random Graphs
• Uniform generation of random graphs with power-law degree sequences
• Counting triangles in power-law uniform random graphs
• A comparative power analysis of the maximum degree and size invariants for random graph inference
• Dense subgraphs of power-law random graphs

Cites work

• scientific article; zbMATH DE number 1335045 (Why is no real title available?)
• scientific article; zbMATH DE number 5070369 (Why is no real title available?)
• A critical point for random graphs with a given degree sequence
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Counting triangles in power-law uniform random graphs
• Generating simple random graphs with prescribed degree distribution
• Large cliques in a power-law random graph
• Optimal subgraph structures in scale-free configuration models
• Reducibility among combinatorial problems
• Subgraph probability of random graphs with specified degrees and applications to chromatic number and connectivity
• Subgraphs in preferential attachment models
• The asymptotic distribution of short cycles in random regular graphs
• The average distances in random graphs with given expected degrees
• The probability that a random multigraph is simple

Cited in

(4)

• Finding Induced Subgraphs in Scale-Free Inhomogeneous Random Graphs
• A comparative power analysis of the maximum degree and size invariants for random graph inference
• Asymptotic bounds for clustering problems in random graphs
• Counting triangles in power-law uniform 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)