License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2016.51
URN: urn:nbn:de:0030-drops-63937
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6393/
Go to the corresponding LIPIcs Volume Portal

Ito, Hiro

Every Property Is Testable on a Natural Class of Scale-Free Multigraphs

pdf-format:
LIPIcs-ESA-2016-51.pdf (0.5 MB)

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

BibTeX - Entry

@InProceedings{ito:LIPIcs:2016:6393,
  author =	{Hiro Ito},
  title =	{{Every Property Is Testable on a Natural Class of Scale-Free Multigraphs}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{51:1--51:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Piotr Sankowski and Christos Zaroliagis},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6393},
  URN =		{urn:nbn:de:0030-drops-63937},
  doi =		{10.4230/LIPIcs.ESA.2016.51},
  annote =	{Keywords: constant-time algorithms,  scale-free networks,  complex networks,  isolated cliques,  hyperfinite}
}

Keywords: constant-time algorithms, scale-free networks, complex networks, isolated cliques, hyperfinite
Collection: 24th Annual European Symposium on Algorithms (ESA 2016)
Issue Date: 2016
Date of publication: 18.08.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI