Abstract:
What do real communities in social networks look like? How can we find them efficiently? Community detection plays a key role in understanding the structure of real-life graphs with impact on recommendation systems, load balancing and routing. Previous community detection methods look for uniform blocks in adjacency matrices, but after studying four real networks with ground-truth communities, we provide empirical evidence that communities are best represented as having hyperbolic structure.

Our new matrix decomposition method is able to describe binary data and combines high interpretability and low reconstruction error by finding non-negative factors that are combined in a binary reconstruction.