Loading...
Please wait, while we are loading the content...
Similar Documents
Learning Communities in the Presence of Errors
| Content Provider | Semantic Scholar |
|---|---|
| Author | Makarychev, Konstantin Vijayaraghavan, Aravindan |
| Copyright Year | 2018 |
| Abstract | We study the problem of learning communities in the presence of modeling errors and give robust recovery algorithms for the Stochastic Block Model (SBM). T his model, which is also known as the Planted Partition Model, is widely used for community detec tion and graph partitioning in various fields, including machine learning, statistics, and social scienc es. Many algorithms exist for learning communities in the Stochastic Block Model, but they do not work wel l in the presence of errors. In this paper, we initiate the study of robust algorithms for pa tial recovery in SBM with modeling errors or noise. We consider graphs generated according to t he Stochastic Block Model and then modified by an adversary. We allow two types of adversarial error s, Feige–Kilian or monotone errors, and edge outlier errors. Mossel, Neeman and Sly (STOC 2015) pose d an open question about whether an almost exact recovery is possible when the adversary is allo wed to addo(n) edges. Our work answers this question affirmatively even in the case of k > 2 communities. We then show that our algorithms work not only when the instan ces come from SBM, but also work when the instances come from any distribution of graphs that is εm close to SBM in the Kullback–Leibler divergence. This result also works in the presence of advers arial errors. Finally, we present almost tight lower bounds for two communities. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://export.arxiv.org/pdf/1511.03229 |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
