Distinguishing Power-Law Uniform Random Graphs from Inhomogeneous Random Graphs Through Small Subgraphs

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

Full description

Saved in:
Bibliographic Details
Published in:Journal of statistical physics 2022-03, Vol.186 (3), Article 37
Main Author: Stegehuis, Clara
Format: Article
Language:English
Subjects:
Algorithms
Analysis
Apexes
Design optimization
Electrical engineering
Graph theory
Graphs
Laws, regulations and rules
Mathematical and Computational Physics
Physical Chemistry
Physics
Physics and Astronomy
Power law
Quantum Physics
Statistical Physics and Dynamical Systems
Theoretical
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0022-4715
1572-9613
DOI:10.1007/s10955-022-02884-9