Phase Transitions for Detecting Latent Geometry in Random Graphs

          @misc{ scivideos_16873,
            doi = {},
            url = {https://simons.berkeley.edu/talks/tbd-254},
            author = {},
            keywords = {},
            language = {en},
            title = {Phase Transitions for Detecting Latent Geometry in Random Graphs},
            publisher = {The Simons Institute for the Theory of Computing},
            year = {2020},
            month = {dec},
            note = {16873 see, \url{https://scivideos.org/index.php/Simons-Institute/16873}}
          }
          

Abstract

Random graphs with latent geometric structure are popular models of social and biological networks, with applications ranging from network user profiling to circuit design. These graphs are also of purely theoretical interest within computer science, probability and statistics. A fundamental initial question regarding these models is: when are these random graphs affected by their latent geometry and when are they indistinguishable from simpler models without latent structure, such as the Erdős-Rényi graph G(n,p)? We address this question for two of the most well-studied models of random graphs with latent geometry -- the random intersection and random geometric graph. Joint work with Matt Brennan and Dheeraj Nagaraj.