View article

We develop sublinear time algorithms for analyzing the cluster structure of graphs with noisy partial information. A graph G with maximum degree at most d is called (k, φ_in, φ_out)-clusterable, if it can be partitioned into at most k parts, such that each part has inner conductance at least φ_in and outer conductance at most φ_out, where d is assumed to be constant. A graph G is called to be an ∊-perturbation of a (k,φ_in, φ_out)-clusterable graph if there is partition of G with at most k parts (called clusters), such that one can insert/delete at most ϵdn intra-cluster edges to make it a (k,φ_in,φ_out)-clusterable graph. We are given query access to the adjacency list of such a graph.

We show that one can construct in time a robust clustering oracle for a bounded-degree graph G that is an ∊-perturbation of a -clusterable graph. Using such an oracle, a typical clustering query (e.g., IsOutlier(s), SameCluster(s, t)) can be answered in …