Community detection on Block Models with Geometric Kernels
# 171
Abstract
We consider the community recovery problem on random geometric graphs where every node has two independent labels: a location label and a community label. A geometric kernel maps the locations of pairs of nodes to probabilities. Edges are drawn between pairs of nodes based on their communities and the value of the kernel corresponding to the respective node locations. Given the graph so generated along with the location labels, the latent communities of the nodes is to be inferred. In this talk, we will look into the fundamental statistical limits for recovering the communities in such models. Additionally, we propose a linear time algorithm (in the number of edges) and show that it recovers the communities of nodes exactly up to the information theoretic threshold in the one dimensional case.
Vinay is a post-doctoral researcher at INRIA Sophia Antipolis - Méditerranée working with Konstantin Avrachenkov in the NEO team. He did his Ph.D. in the Department of ECE at the Indian Institute of Science under the guidance of Navin Kashyap. His thesis was titled “Probabilistic Forwarding of Coded Packets for Broadcasting over Networks”. Broadly, Vinay works in the area of random graphs and network science. He is interested in problems that involve a graph structure and complex interactions between the network elements. His research goal is to propose and analyze robust mathematical models that capture different physical phenomena observed on practical networks.