{"id":349979,"date":"2017-01-06T00:00:54","date_gmt":"2017-01-06T08:00:54","guid":{"rendered":"https:\/\/www.microsoft.com\/en-us\/research\/?post_type=msr-research-item&#038;p=349979"},"modified":"2017-01-10T09:58:56","modified_gmt":"2017-01-10T17:58:56","slug":"community-detection-stochastic-block-model-approximate-belief-propagation","status":"publish","type":"msr-video","link":"https:\/\/www.microsoft.com\/en-us\/research\/video\/community-detection-stochastic-block-model-approximate-belief-propagation\/","title":{"rendered":"Community Detection in the Stochastic Block Model: Approximate Belief Propagation"},"content":{"rendered":"<p>The stochastic block model is one of the simplest models for a random graph with different types of vertices, known as communities. In this talk I will describe an efficient algorithm that distinguishes between vertices from different communities with nontrivial accuracy whenever the SBM&#8217;s parameters are above the Kesten-Stigum threshold, proving half of a conjecture by Decelle et al. I will also show that given exponential time it is sometimes possible to distinguish between communities with nontrivial accuracy below the KS threshold. Furthermore, I will also discuss how accurately one can classify vertices when the signal to noise ratio of the graph is large.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>The stochastic block model is one of the simplest models for a random graph with different types of vertices, known as communities. In this talk I will describe an efficient algorithm that distinguishes between vertices from different communities with nontrivial accuracy whenever the SBM&#8217;s parameters are above the Kesten-Stigum threshold, proving half of a conjecture [&hellip;]<\/p>\n","protected":false},"featured_media":349994,"template":"","meta":{"msr-url-field":"","msr-podcast-episode":"","msrModifiedDate":"","msrModifiedDateEnabled":false,"ep_exclude_from_search":false,"footnotes":""},"research-area":[13561,13546],"msr-video-type":[],"msr-locale":[268875],"msr-impact-theme":[],"msr-pillar":[],"class_list":["post-349979","msr-video","type-msr-video","status-publish","has-post-thumbnail","hentry","msr-research-area-algorithms","msr-research-area-computational-sciences-mathematics","msr-locale-en_us"],"msr_download_urls":"","msr_external_url":"https:\/\/youtu.be\/nl_sftghluI","msr_secondary_video_url":"","msr_video_file":"","_links":{"self":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-video\/349979"}],"collection":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-video"}],"about":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/types\/msr-video"}],"version-history":[{"count":0,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-video\/349979\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media\/349994"}],"wp:attachment":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media?parent=349979"}],"wp:term":[{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=349979"},{"taxonomy":"msr-video-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-video-type?post=349979"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=349979"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=349979"},{"taxonomy":"msr-pillar","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-pillar?post=349979"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}