Testing Cluster Structure of Graphs

We study the problem of recognizing the spectral cluster structure of a graph in the framework of property testing in the bounded degree model. A 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 \(φₒᵤₜ\) . Our main result is a sublinear algorithm with the running time \({O}d,k(√n(φ,1/ε))\) that takes as input an \( n \) -vertex graph with maximum degree bounded by \( d \) , parameters \( k \) , \(φ\) , \(ε\) , and with probability at least \(2/3\) , accepts the graph if it is \((k,φ,Od,k(ε⁴φ²))\) -clusterable, and rejects the graph if it is \(ε\) -far from \((k,φ*,ψ*)\) -clusterable for \(φ*=Od,k({φ²ε⁴}{log n})\) and any \(ψ*≥ 0\) . 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.