`

Timezone: »

Poster
Bipartite Stochastic Block Models with Tiny Clusters
Stefan Neumann

Thu Dec 06 02:00 PM -- 04:00 PM (PST) @ Room 210 #52
We study the problem of finding clusters in random bipartite graphs. We present a simple two-step algorithm which provably finds even tiny clusters of size $O(n^\epsilon)$, where $n$ is the number of vertices in the graph and $\epsilon > 0$. Previous algorithms were only able to identify clusters of size $\Omega(\sqrt{n})$. We evaluate the algorithm on synthetic and on real-world data; the experiments show that the algorithm can find extremely small clusters even in presence of high destructive noise.