Every property is testable on a natural class of scale-free multigraphs

Abstract

In this paper, we introduce a natural class of multigraphs called hierarchical-scale-free (HSF) multigraphs, and consider constant-time testability on the class. We show that a very wide subclass, specifically, that in which the power-law exponent is greater than two, of HSF is hyperfinite. Based on this result, an algorithm for a deterministic partitioning oracle can be constructed. We conclude by showing that every property is constant-time testable on the above subclass of HSF. This algorithm utilizes findings by Newman and Sohler of STOC'11. However, their algorithm is based on the bounded-degree model, while it is known that actual scale-free networks usually include hubs, which have a very large degree. HSF is based on scale-free properties and includes such hubs. This is the first universal result of constant-time testability on the general graph model, and it has the potential to be applicable on a very wide range of scale-free networks.

13 pages, one figure. Difference from ver. 1: Definitions of HSF and SF become more general. Typos were fixed