Faculty Recruiting Make a Gift

Geometric Block Model

13 Feb
Wednesday, 02/13/2019 12:15pm to 1:15pm
Computer Science Building Room 140
Theory Seminar
Speaker: Soumyabrata Pal

To capture the inherent geometric features of many community detection (clustering) 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 Erd os-Renyi random graphs. In this talk, Iwill explain this new model and propose a simple triangle counting algorithm that is order efficient in the sparse regime. The proof of correctness of this algorithm has connections with connectivity properties of Vertex Random Graphs which is a generalization of Random Geometric Graphs. I will talk about some very surprising results that we have regarding the aforementioned connectivity properties and their extension to higher dimensions. This is a joint work with Sainyam Galhotra, Arya Mazumdar and Barna Saha.

Faculty Host