Sabyasachi Basu, Suman Kalyan Bera, and C. Seshadhri
05/26/2023 05:56 PM
Computer Science and Engineering
Partitioning a graph into clusters of vertices is a fundamental problem in computer science and applied mathematics. Arguably, the most important tool for graph partitioning is the Fielder vector or discrete Cheeger inequality. This result relates the eigenvalues of the normalized adjacency matrix to the low conductance cuts of the graph. However, the Cheeger inequality has little relevance on an important contemporary graph partitioning problem, that of community detection in massive real-world graphs. There are numerous, small, dense clusters in real-world graphs, while Cheeger inequalities focus on partitioning a graph into a few, large clusters. Inspired by the structure of real-world graphs, we define the \emph{spectral transitivity}, a ratio of powers of eigenvalues of the normalized adjacency matrix $\mathcal A$. We discover that constant spectral transitivity implies that a constant fraction of $\mathcal A$ is contained in nearly uniform submatrices. Our result is a new spectral theorem that relates the eigenvalues of $\mathcal A$ to a cluster structure in $\mathcal A$. The latter structure mimics the observed cluster structure of real-world graphs.
