Abstract: Can the structure of a network reveal how it is formed? Community detection, or graph clustering, is an important field in modern data science that studies how to extract useful information from the structure of social networks, citation networks, etc. In recent years, the field has seen important theoretical breakthroughs via the development of algorithms with provable performance guarantees on random graphs. This talk develops on this theme with an exposition of a hitherto unexplored random graph model that better represents real world networks.
A preliminary version of this work was presented at International Symposium on Information Theory, 2018. An extended version can be found at https://arxiv.org/abs/1801.06818
