Testing Cluster Structure of Graphs

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, φ)-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,kvarepsilon4φ2, where cd,k depends only on d,k. Our main result is a sublinear algorithm with the running time widetildeO(√n·poly(φ,k,1/varepsilon)) that takes as input a graph with maximum degree bounded by d, parameters k, φ, varepsilon, and with probability at least frac23, accepts the graph if it is (k,φ)-clusterable and rejects the graph if it is varepsilon-far from (k, φ^*)-clusterable for φ^* = c'd,kfracφ2 varepsilon4log n, where c'd,k depends only on d,k. By the lower bound of Omega(√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.