Information theoretic, message passing, and spectral method for inference in stochastic and censored block models
Event details
| Date | 05.07.2016 |
| Hour | 08:00 › 10:00 |
| Speaker | Chun Lam Chan |
| Location | |
| Category | Conferences - Seminars |
EDIC Candidacy Exam
Exam President: Prof. Patrick Thiran
Thesis Director: Dr. Nicolas Macris
Co-examiner: Dr. Olivier Leveque
Background papers:
Asymptotic Mutual Information for the Two-Groups Stochastic Block Model, by Y. Deshpande; E. Abbe; A. Montanari.
Spectral Detection in the Censored Block Model, by Alaa Saade; Florent Krzakala; Marc Lelarge; Lenka Zdeborova.
Spectral redemption: clustering sparse networks, by Florent Krzakala; Cristopher Moore; Elchanan Mossel; Joe Neeman; Allan Sly; Lenka
Zdeborova; Pan Zhang.
Abstract
The stochastic block model (SBM) and censored
block model (CBM) are two statistical models for the task of
identifying the hidden partition of vertices from an undirected
graph. This problem is also known as community detection for
network science. In this proposal, we survey three papers that
have demonstrated the use of theoretical tools listed in the title.
In a sufficiently dense graph regime of SBM, [1] has provided
an explicit characterization of the asymptotic mutual information
and revealed a phase transition for partial recovery. In a sparse
graph regime, [2] and [3] have proposed spectral algorithms
for SBM and CBM, respectively. The algorithms have an origin
from message-passing algorithms and are observed to successfully
provide partial recovery as long as it is information-theoretically
possible. Finally, we discuss the connection of these inference
problems and coding theory.
Exam President: Prof. Patrick Thiran
Thesis Director: Dr. Nicolas Macris
Co-examiner: Dr. Olivier Leveque
Background papers:
Asymptotic Mutual Information for the Two-Groups Stochastic Block Model, by Y. Deshpande; E. Abbe; A. Montanari.
Spectral Detection in the Censored Block Model, by Alaa Saade; Florent Krzakala; Marc Lelarge; Lenka Zdeborova.
Spectral redemption: clustering sparse networks, by Florent Krzakala; Cristopher Moore; Elchanan Mossel; Joe Neeman; Allan Sly; Lenka
Zdeborova; Pan Zhang.
Abstract
The stochastic block model (SBM) and censored
block model (CBM) are two statistical models for the task of
identifying the hidden partition of vertices from an undirected
graph. This problem is also known as community detection for
network science. In this proposal, we survey three papers that
have demonstrated the use of theoretical tools listed in the title.
In a sufficiently dense graph regime of SBM, [1] has provided
an explicit characterization of the asymptotic mutual information
and revealed a phase transition for partial recovery. In a sparse
graph regime, [2] and [3] have proposed spectral algorithms
for SBM and CBM, respectively. The algorithms have an origin
from message-passing algorithms and are observed to successfully
provide partial recovery as long as it is information-theoretically
possible. Finally, we discuss the connection of these inference
problems and coding theory.
Practical information
- General public
- Free
Contact
- Cecilia Chapuis EDIC