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.
Zoom link: https://us02web.zoom.us/j/88670406480
Meeting ID: 886 7040 6480