Title: Community detection on geometric graphs
Speaker: Dr. Vinay Kumar
Venue: Seminar hall, second floor, IEOR Building.
Day, Date, Time: Monday, 19th August 2024, 11:30am to 12:30pm.
Abstract: In many real-world networks, such as co-authorship and social networks, the graph structure is correlated with the locations of the nodes. The geometric dependence is typically evidenced by the absence of long-distance edges and the abundance of triangles. Detecting latent communities on such geometric graphs has been an important direction of research. We consider the community recovery problem on a random geometric graph 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 are to be inferred. In this talk, we will look into the fundamental 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.
Brief Bio: Vinay did his PhD in the Dept. of Electrical Communication Engineering at the Indian Institute of Science, Bangalore, under the guidance of Prof. Navin Kashyap. His thesis was titled "Probabilistic Forwarding of Coded Packets for Broadcasting over Networks". He was a post-doctoral researcher at INRIA Sophia Antipolis - Méditerranée working with Konstantin Avrachenkov in the NEO team prior to joining the NETWORKS-COFUND program in 2024, where he currently works with Nelly Litvak and Remco van der Hofstad. Broadly, his research is in the areas 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 analyse robust mathematical models that capture different physical phenomena observed on practical networks.