The Library
Testing cluster structure of graphs
Tools
Tools
Tools
Czumaj, Artur, Peng, Pan and Sohler, Christian (2015) Testing cluster structure of graphs. In: Forty-Seventh Annual ACM on Symposium on Theory of Computing, Portland, Oregon, 15-17 Jun 2015. Published in: Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing pp. 723-732. ISBN 9781450335362. doi:10.1145/2746539.2746618
An open access version can be found in:
Official URL: http://dx.doi.org/10.1145/2746539.2746618
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 ε, a d-bounded degree graph is defined to be (k, φ)-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 φ and the (outer) conductance of each part is at most cd,kε4φ2, where cd,k depends only on d,k. Our main result is a sublinear algorithm with the running time ~O(√n ⋅ poly(φ,k,1/ε)) that takes as input a graph with maximum degree bounded by d, parameters k, φ, ε, and with probability at least 2/3, accepts the graph if it is (k,φ)-clusterable and rejects the graph if it is ε-far from (k, φ*)-clusterable for φ* = c'd,kφ2 ε4}/log n, where c'd,k depends only on d,k. By the lower bound of Ω(√n) 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.
| Item Type: | Conference Item (Paper) | ||||
|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics | ||||
| Divisions: | Faculty of Science > Computer Science | ||||
| Library of Congress Subject Headings (LCSH): | Random walks (Mathematics) , Graph theory, Cluster analysis | ||||
| Series Name: | STOC: ACM Symposium on Theory of Computing | ||||
| Journal or Publication Title: | Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing | ||||
| Publisher: | Association for Computing Machinery | ||||
| ISBN: | 9781450335362 | ||||
| Official Date: | 14 June 2015 | ||||
| Dates: |
|
||||
| Page Range: | pp. 723-732 | ||||
| DOI: | 10.1145/2746539.2746618 | ||||
| Status: | Peer Reviewed | ||||
| Publication Status: | Published | ||||
| Access rights to Published version: | Open Access | ||||
| Funder: | University of Warwick. Centre for Discrete Mathematics and Its Applications, Engineering and Physical Sciences Research Council (EPSRC) | ||||
| Grant number: | EP/J021814/1(EPSRC) ; 307696 (EPSRC) ; 307696 (EPSRC) | ||||
| Conference Paper Type: | Paper | ||||
| Title of Event: | Forty-Seventh Annual ACM on Symposium on Theory of Computing | ||||
| Type of Event: | Other | ||||
| Location of Event: | Portland, Oregon | ||||
| Date(s) of Event: | 15-17 Jun 2015 | ||||
| Related URLs: | |||||
| Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
