- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- BIRS Workshop Lecture Videos /
- Learning Communities in the Presence of Errors
Open Collections
BIRS Workshop Lecture Videos
BIRS Workshop Lecture Videos
Learning Communities in the Presence of Errors Makarychev, Konstantin
Description
I will talk about learning hidden communities in the presence of modeling errors in the Stochastic Block Model. This model, which is also known as the Planted Partition Model, is widely used for community detection and graph partitioning in various fields, including machine learning, statistics, and social sciences. We consider graphs generated according to the Stochastic Block Model and then modified by an adversary. We allow two types of adversarial errors, Feige—Kilian or monotone errors, and edge outlier errors. In the talk, I will present a simple SDP-based algorithm for finding planted communities in sparse graphs from the Stochastic Block Model and prove that this algorithm is robust to adversarial errors. The talk is based on a joint work with Yury Makarychev and Aravindan Vijayaraghavan (COLT 2016).
Item Metadata
| Title |
Learning Communities in the Presence of Errors
|
| Creator | |
| Publisher |
Banff International Research Station for Mathematical Innovation and Discovery
|
| Date Issued |
2017-11-15T11:03
|
| Description |
I will talk about learning hidden communities in the presence of modeling errors in the Stochastic Block Model. This model, which is also known as the Planted Partition Model, is widely used for community detection and graph partitioning in various fields, including machine learning, statistics, and social sciences. We consider graphs generated according to the Stochastic Block Model and then modified by an adversary. We allow two types of adversarial errors, Feige—Kilian or monotone errors, and edge outlier errors. In the talk, I will present a simple SDP-based algorithm for finding planted communities in sparse graphs from the Stochastic Block Model and prove that this algorithm is robust to adversarial errors.
The talk is based on a joint work with Yury Makarychev and Aravindan Vijayaraghavan (COLT 2016).
|
| Extent |
29 minutes
|
| Subject | |
| Type | |
| File Format |
video/mp4
|
| Language |
eng
|
| Notes |
Author affiliation: Northwestern University
|
| Series | |
| Date Available |
2018-05-15
|
| Provider |
Vancouver : University of British Columbia Library
|
| Rights |
Attribution-NonCommercial-NoDerivatives 4.0 International
|
| DOI |
10.14288/1.0366308
|
| URI | |
| Affiliation | |
| Peer Review Status |
Unreviewed
|
| Scholarly Level |
Faculty
|
| Rights URI | |
| Aggregated Source Repository |
DSpace
|
Item Media
Item Citations and Data
Rights
Attribution-NonCommercial-NoDerivatives 4.0 International