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

Research output: Working paperProfessional

7 Downloads (Pure)

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.
Original languageEnglish
PublisherarXiv.org
Publication statusPublished - 18 Feb 2021

Keywords

  • math.CO
  • math.PR

Fingerprint Dive into the research topics of 'Distinguishing power-law uniform random graphs from inhomogeneous random graphs through small subgraphs'. Together they form a unique fingerprint.

Cite this