Spectral methods for testing cluster structure of graphs

Abstract

In the framework of graph property testing, we study the problem of determining if a graph admits a cluster structure. We say that a graph is $(k,\varphi )$-clusterable if it can be partitioned into at most $k$ parts such that each part has conductance at least $\varphi$. We present an algorithm that accepts all graphs that are $(2,\varphi )$-clusterable with probability at least $\frac{2}{3}$ and rejects all graphs that are $\epsilon$-far from $(2,{\varphi }^{\ast })$-clusterable for ${\varphi }^{\ast }\le \mu {\varphi }^2{\epsilon }^2$ with probability at least $\frac{2}{3}$ where $\mu >0$ is a parameter that affects the query complexity. This improves upon the work of Czumaj, Peng, and Sohler by removing a $\log n$ factor from the denominator of the bound on ${\varphi }^{\ast }$ for the case of $k=2$. Our work was concurrent with the work of Chiplunkar et al.\@ who achieved the same improvement for all values of $k$. Our approach for the case $k=2$ relies on the geometric structure of the eigenvectors of the graph Laplacian and results in an algorithm with query complexity $O(n^{1/2+O(1)\mu }\cdot \text{poly}(1/\epsilon ,1/\varphi ,\log n))$.

21 pages, 7 figures