The Geometric Block Model
Preprint
Abstract
To capture the inherent geometric features of many community detection problems, we propose to use a new random graph model of communities that we call a Geometric Block Model. The geometric block model generalizes the random geometric graphs in the same way that the well-studied stochastic block model generalizes the Erdos-Renyi random graphs. It is also a natural extension of random community models inspired by the recent theoretical and practical advancement in community detection. While being a topic of fundamental theoretical interest, our main contribution is to show that many practical community structures are better explained by the geometric block model. We also show that a simple triangle-counting algorithm to detect communities in the geometric block model is near-optimal. Indeed, even in the regime where the average degree of the graph grows only logarithmically with the number of vertices (sparse-graph), we show that this algorithm performs extremely well, both theoretically and practically. In contrast, the triangle-counting algorithm is far from being optimum for the stochastic block model. We simulate our results on both real and synthetic datasets to show superior performance of both the new model as well as our algorithm.Keywords
All Related Versions
This publication has 13 references indexed in Scilit:
- Achieving Exact Cluster Recovery Threshold via Semidefinite ProgrammingIEEE Transactions on Information Theory, 2016
- Testing for high‐dimensional geometry in random graphsRandom Structures & Algorithms, 2016
- Exact Recovery in the Stochastic Block ModelIEEE Transactions on Information Theory, 2015
- Defining and evaluating network communities based on ground-truthKnowledge and Information Systems, 2013
- Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applicationsPhysical Review E, 2011
- Stochastic geometry and random graphs for the analysis and design of wireless networksIEEE Journal on Selected Areas in Communications, 2009
- On the cover time and mixing time of random geometric graphsTheoretical Computer Science, 2007
- Monotone properties of random geometric graphs have sharp thresholdsThe Annals of Applied Probability, 2005
- The solution of some random NP-hard problems in polynomial expected timeJournal of Algorithms, 1989
- Stochastic blockmodels: First stepsSocial Networks, 1983