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 c d,k ε 4 ϕ 2 , where c d,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.
An algorithm for testing the cluster structure of graphs has been proposed in REF .
Testing Cluster Structure of Graphs
STOC '15
Mathematics Computer Science