FUNDAMENTAL LIMITS FOR COMMUNITY DETECTION IN LABELLED NETWORKS

Loading...
Thumbnail Image

Date

2020

Journal Title

Journal ISSN

Volume Title

Repository Usage Stats

160
views
184
downloads

Abstract

The problem of detecting the community structure of networks as well as closely related problems involving low-rank matrix factorization arise in applications throughout science and engineering. This dissertation focuses on the the fundamental limits of detection and recovery associated with a broad class of probabilistic network models, that includes the stochastic block model with labeled-edges. The main theoretical results are formulas that describe the asymptotically exact limits of the mutual information and reconstruction error. The formulas are described in terms of low-dimensional estimation problems in additive Gaussian noise.

The analysis builds upon a number of recent theoretical advances at the interface of information theory, random matrix theory, and statistical physics, including concepts such as channel universality and interpolation methods. The theoretical formulas provide insight into the ability to recover the community structure in the network. The analysis is supported by numerical simulations. Numerical simulations for different network models show that the observed performance closely follows the performance predicted by the formulas.

Description

Provenance

Citation

Citation

Mayya, Vaishakhi Sathish (2020). FUNDAMENTAL LIMITS FOR COMMUNITY DETECTION IN LABELLED NETWORKS. Dissertation, Duke University. Retrieved from https://hdl.handle.net/10161/22211.

Collections


Except where otherwise noted, student scholarship that was shared on DukeSpace after 2009 is made available to the public under a Creative Commons Attribution / Non-commercial / No derivatives (CC-BY-NC-ND) license. All rights in student work shared on DukeSpace before 2009 remain with the author and/or their designee, whose permission may be required for reuse.