Testing Cluster Structure of Graphs
University of Warwick · University of Science and Technology of China · +2 more institutions
Abstract
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,\phi_{\textrm{in}},\phi_{\textrm{out}})\) -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 \(\phi_{\textrm{in}}\) and the (outer) conductance of each part is at most \(\phi_{\textrm{out}}\) . Our main result is a sublinear algorithm with the running time \(\widetilde{O}_{d,k}(\sqrt{n}\cdot\mathrm{poly}(\phi,1/\varepsilon))\) that takes as input an \(n\) -vertex graph with maximum degree bounded by \(d\) , parameters \(k\) , \(\phi\) ,…
Citation impact
- FWCI
- 0.00
- Percentile
- 96%
- References
- 42
Authors
3Topics & keywords
- Combinatorics
- Bounded function
- Degree (music)
- Omega
- Graph
- Sublinear function
- Conductance
- Mathematics