Testing Cluster Structure of Graphs

By Christian Sohler (TU Dortmund)
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 eps, a d-bounded degree graph is defined to be (k,F)-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 F and the (outer) conductance of each part is at most cϵ4F2, where c depends only on d,k. Our main result is a sublinear algorithm with the running time O((√n)poly(F,k,1/ϵ)) that takes asinput a graph with maximum degree bounded by d, parameters k, F, ϵ , and with probability at least 2/3, accepts the graph if it is (k,F)-clusterable and rejects the graph if it is ϵ-far from (k,F∗)-clusterable for F∗=cOF2ϵ4logn , where cO depends only on d,k.