2015/04/13 by Czumaj, Artur, Peng, Pan, Sohler, Christian · 2 citations
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1504.03294
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 \widetildeO(√(n)\cdotpoly(ϕ,k,1/ε)) that takes as input a graph with maximum degree bounded by d, parameters k, ϕ, ε, and with probability at least \frac23, 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.