2026-07-25T03:00:03Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6393 2024-03-06T10:38:09Z ddc:004 open_access

Every Property Is Testable on a Natural Class of Scale-Free Multigraphs Ito, Hiro constant-time algorithms scale-free networks complex networks isolated cliques hyperfinite 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 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 a 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 a class of graphs made by a model of scale-free networks, and it has the potential to be applicable on a very wide range of scale-free networks. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Hiro Ito 2016 Is Part Of LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2016.51 urn:nbn:de:0030-drops-63937 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.51 eng https://creativecommons.org/licenses/by/3.0/legalcode