Poster
Bipartite Stochastic Block Models with Tiny Clusters
Stefan Neumann
Room 210 #52
Keywords: [ Clustering ] [ Spectral Methods ] [ Computational Complexity ]
[
Abstract
]
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ϵ), where n is the number of vertices in the graph and ϵ>0. Previous algorithms were only able to identify clusters of size Ω(√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