Skip to yearly menu bar Skip to main content


Poster

Bipartite Stochastic Block Models with Tiny Clusters

Stefan Neumann

Room 210 #52

Keywords: [ Clustering ] [ Spectral Methods ] [ Computational Complexity ]


Abstract: 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.

Live content is unavailable. Log in and register to view live content