Testing cluster structure of graphs

DOI10.1145/2746539.2746618MaRDI QIDQ2941567zbMATH OpenOpenAlexFDO

Authors Pan Peng, Christian Sohler, Artur Czumaj

Publication date 21 August 2015

Published in Proceedings of the forty-seventh annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1504.03294

zbMATH Keywords

graph clusteringspectral graph theoryrandom walksgraph property testing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Random walks on graphs (05C81)

Abstract: We study the problem of recognizing the cluster structure of a graph in the framework of property testing in the bounded degree model. Given a parameter $varepsilon$, a $d$-bounded degree graph is defined to be $(k,phi)$-clusterable, if it can be partitioned into no more than $k$ parts, such that the (inner) conductance of the induced subgraph on each part is at least $phi$ and the (outer) conductance of each part is at most $c_{d,k}varepsilo{n}^{4}ph{i}^2$, where $c_{d,k}$ depends only on $d,k$. Our main result is a sublinear algorithm with the running time $widetildeO(sqrtncdotmathrmpoly(phi,k,1/varepsilon))$ that takes as input a graph with maximum degree bounded by $d$, parameters $k$, $phi$, $varepsilon$, and with probability at least $frac23$, accepts the graph if it is $(k,phi)$-clusterable and rejects the graph if it is $varepsilon$-far from $(k,ph{i}^{\ast })$-clusterable for $ph{i}^{\ast }=c{\text{'}}_{d,k}fracph{i}^{2}varepsilo{n}^{4}logn$, where $c{\text{'}}_{d,k}$ depends only on $d,k$. By the lower bound of $Omega(sqrtn)$ on the number of queries needed for testing graph expansion, which corresponds to $k=1$ in our problem, our algorithm is asymptotically optimal up to polylogarithmic factors.

Recommendations

• scientific article; zbMATH DE number 1559556
• Property testing in bounded degree graphs
• An Expansion Tester for Bounded Degree Graphs
• Property testing and its connection to learning and approximation
• Testing the expansion of a graph

Cites work

• Approximate distance oracles
• Approximate distance oracles with constant query time
• Automata, Languages and Programming
• Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
• Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
• Fast C-K-R partitions of sparse graphs
• Near-Linear Time Construction of Sparse Neighborhood Covers
• On approximate distance labels and routing schemes with affine stretch
• On sparse spanners of weighted graphs
• Ramsey partitions and proximity data structures
• Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem
• Shortest-path queries in static networks

Cited in

(14)

• Testing higher-order clusterability on graphs
• Distributed detection of clusters of arbitrary size
• Spectral concentration and greedy \(k\)-clustering
• A two-sided error distributed property tester for conductance
• Assessing the Performance of a Graph-Based Clustering Algorithm
• Testing higher-order clusterability on graphs
• Random walks and forbidden minors. I: An \(n^{1/2+o(1)}\)-query one-sided tester for minor closed properties on bounded degree graphs
• scientific article; zbMATH DE number 7559112 (Why is no real title available?)
• Random Walks and Forbidden Minors I: An $n^{1/2+o(1)}$-Query One-Sided Tester for Minor Closed Properties on Bounded Degree Graphs
• A sublinear time tester for max-cut on clusterable graphs
• On the characterization of 1-sided error strongly testable graph properties for bounded-degree graphs
• Nearly optimal local algorithms for constructing sparse spanners of clusterable graphs
• scientific article; zbMATH DE number 5683074 (Why is no real title available?)
• scientific article; zbMATH DE number 7525446 (Why is no real title available?)

Describes a project that uses

Uses Software

• Graphs

This page was built for publication: Testing cluster structure of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2941567)