|
Activity Number:
|
43
- Statistical Methods for Complex Networks
|
|
Type:
|
Invited
|
|
Date/Time:
|
Sunday, July 30, 2017 : 4:00 PM to 5:50 PM
|
|
Sponsor:
|
IMS
|
|
Abstract #322163
|
|
|
Title:
|
Community Detection and Invariance to Distribution
|
|
Author(s):
|
Guy Bresler* and Wasim Huleihel
|
|
Companies:
|
MIT and MIT
|
|
Keywords:
|
community detection ;
average case complexity ;
random graphs
|
|
Abstract:
|
We consider the problem of recovering a hidden community of size K from a graph where edges between members of the community have label drawn i.i.d. according to P and all other edges have labels drawn i.i.d. according to Q. The information limits for this problem were characterized by Hajek-Wu-Xu in 2016 in terms of the KL-divergence between P and Q. We complement their work by showing that for a broad class of distributions P and Q one may efficiently reduce to the case P = Ber(p) and Q = Ber(q) and vice versa. This implies that the computational difficulty is independent of the choice of distribution within the class.
|
Authors who are presenting talks have a * after their name.
