Authors: Newman, Ilan
Sohler, Christian
Title: Every Property of Hyperfinite Graphs is Testable
Language (ISO): en
Abstract: A k-disc around a vertex v of a graph G=(V,E) is the subgraph induced by all vertices of distance at most k from v. We show that the structure of a planar graph on n vertices, and with constant maximum degree d, is determined, up to the modification (insertion or deletion) of at most εdn edges, by the frequency of k-discs for certain k=k(ε,d) that is independent of the size of the graph. We can replace planar graphs by any hyperfinite class of graphs, which includes, for example, every graph class that does not contain a set of forbidden minors. A pure combinatorial consequence of this result is that two d-bounded degree graphs that have similar frequency vectors (that is, the l_1 difference between the frequency vectors is small) are close to isomorphic (where close here means that by inserting or deleting not too many edges in one of them, it becomes isomorphic to the other). We also obtain the following new results in the area of property testing, which are essentially equivalent to the above statement. We prove that (a) graph isomorphism is testable for every class of hyperfinite graphs, (b) every graph property is testable for every class of hyperfinite graphs, (c) every hyperfinite graph property is testable in the bounded degree graph model, (d) A large class of graph parameters is approximable for hyperfinite graphs. Our results also give a partial explanation of the success of motifs in the analysis of complex networks.
Subject Headings: property testing
graph properties
URI: http://hdl.handle.net/2003/34160
http://dx.doi.org/10.17877/DE290R-7805
Issue Date: 2013-06-13
Provenance: Society for Industrial and Applied Mathematics
Appears in Collections:Sublinear Algorithms for the Analysis of Very Large Graphs

Files in This Item:
File Description SizeFormat 
hyperfinite_sicomp.pdfArtikel361.39 kBAdobe PDFView/Open


This item is protected by original copyright



This item is protected by original copyright rightsstatements.org