Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

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:
  • Other
Official URL: http://dx.doi.org/10.1145/2746539.2746618

Request Changes to record.

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:
DateEvent
14 June 2015Published
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:
  • Organisation
  • Open Access File
Open Access Version:
  • Other

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item
twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us