CINXE.COM

<!DOCTYPE html> <html class="client-nojs vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-sticky-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-toc-available" lang="en" dir="ltr"> <head> <meta charset="UTF-8"> <title>Stochastic block model - Wikipedia</title> <script>(function(){var className="client-js vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-sticky-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-toc-available";var cookie=document.cookie.match(/(?:^|; )enwikimwclientpreferences=([^;]+)/);if(cookie){cookie[1].split('%2C').forEach(function(pref){className=className.replace(new RegExp('(^| )'+pref.replace(/-clientpref-\w+$|[^\w-]+/g,'')+'-clientpref-\\w+( |$)'),'$1'+pref+'$2');});}document.documentElement.className=className;}());RLCONF={"wgBreakFrames":false,"wgSeparatorTransformTable":["",""],"wgDigitTransformTable":["",""],"wgDefaultDateFormat":"dmy", "wgMonthNames":["","January","February","March","April","May","June","July","August","September","October","November","December"],"wgRequestId":"03ba4d54-28c2-44c2-afa4-1a12717bae42","wgCanonicalNamespace":"","wgCanonicalSpecialPageName":false,"wgNamespaceNumber":0,"wgPageName":"Stochastic_block_model","wgTitle":"Stochastic block model","wgCurRevisionId":1230624135,"wgRevisionId":1230624135,"wgArticleId":47845063,"wgIsArticle":true,"wgIsRedirect":false,"wgAction":"view","wgUserName":null,"wgUserGroups":["*"],"wgCategories":["Webarchive template wayback links","Pages displaying short descriptions with no spaces via Module:Annotated link","Random graphs","Networks","Blockmodeling"],"wgPageViewLanguage":"en","wgPageContentLanguage":"en","wgPageContentModel":"wikitext","wgRelevantPageName":"Stochastic_block_model","wgRelevantArticleId":47845063,"wgIsProbablyEditable":true,"wgRelevantPageIsProbablyEditable":true,"wgRestrictionEdit":[],"wgRestrictionMove":[],"wgNoticeProject":"wikipedia", "wgCiteReferencePreviewsActive":false,"wgFlaggedRevsParams":{"tags":{"status":{"levels":1}}},"wgMediaViewerOnClick":true,"wgMediaViewerEnabledByDefault":true,"wgPopupsFlags":0,"wgVisualEditor":{"pageLanguageCode":"en","pageLanguageDir":"ltr","pageVariantFallbacks":"en"},"wgMFDisplayWikibaseDescriptions":{"search":true,"watchlist":true,"tagline":false,"nearby":true},"wgWMESchemaEditAttemptStepOversample":false,"wgWMEPageLength":20000,"wgRelatedArticlesCompat":[],"wgEditSubmitButtonLabelPublish":true,"wgULSPosition":"interlanguage","wgULSisCompactLinksEnabled":false,"wgVector2022LanguageInHeader":true,"wgULSisLanguageSelectorEmpty":false,"wgWikibaseItemId":"Q25053762","wgCheckUserClientHintsHeadersJsApi":["brands","architecture","bitness","fullVersionList","mobile","model","platform","platformVersion"],"GEHomepageSuggestedEditsEnableTopics":true,"wgGETopicsMatchModeEnabled":false,"wgGEStructuredTaskRejectionReasonTextInputEnabled":false,"wgGELevelingUpEnabledForUser":false};RLSTATE={ "ext.globalCssJs.user.styles":"ready","site.styles":"ready","user.styles":"ready","ext.globalCssJs.user":"ready","user":"ready","user.options":"loading","ext.cite.styles":"ready","ext.math.styles":"ready","skins.vector.search.codex.styles":"ready","skins.vector.styles":"ready","skins.vector.icons":"ready","ext.wikimediamessages.styles":"ready","ext.visualEditor.desktopArticleTarget.noscript":"ready","ext.uls.interlanguage":"ready","wikibase.client.init":"ready","ext.wikimediaBadges":"ready"};RLPAGEMODULES=["ext.cite.ux-enhancements","mediawiki.page.media","site","mediawiki.page.ready","mediawiki.toc","skins.vector.js","ext.centralNotice.geoIP","ext.centralNotice.startUp","ext.gadget.ReferenceTooltips","ext.gadget.switcher","ext.urlShortener.toolbar","ext.centralauth.centralautologin","mmv.bootstrap","ext.popups","ext.visualEditor.desktopArticleTarget.init","ext.visualEditor.targetLoader","ext.echo.centralauth","ext.eventLogging","ext.wikimediaEvents","ext.navigationTiming", "ext.uls.interface","ext.cx.eventlogging.campaigns","ext.cx.uls.quick.actions","wikibase.client.vector-2022","ext.checkUser.clientHints","ext.growthExperiments.SuggestedEditSession"];</script> <script>(RLQ=window.RLQ||[]).push(function(){mw.loader.impl(function(){return["user.options@12s5i",function($,jQuery,require,module){mw.user.tokens.set({"patrolToken":"+\\","watchToken":"+\\","csrfToken":"+\\"}); }];});});</script> <link rel="stylesheet" href="/w/load.php?lang=en&modules=ext.cite.styles%7Cext.math.styles%7Cext.uls.interlanguage%7Cext.visualEditor.desktopArticleTarget.noscript%7Cext.wikimediaBadges%7Cext.wikimediamessages.styles%7Cskins.vector.icons%2Cstyles%7Cskins.vector.search.codex.styles%7Cwikibase.client.init&only=styles&skin=vector-2022"> <script async="" src="/w/load.php?lang=en&modules=startup&only=scripts&raw=1&skin=vector-2022"></script> <meta name="ResourceLoaderDynamicStyles" content=""> <link rel="stylesheet" href="/w/load.php?lang=en&modules=site.styles&only=styles&skin=vector-2022"> <meta name="generator" content="MediaWiki 1.44.0-wmf.6"> <meta name="referrer" content="origin"> <meta name="referrer" content="origin-when-cross-origin"> <meta name="robots" content="max-image-preview:standard"> <meta name="format-detection" content="telephone=no"> <meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/thumb/d/d2/Internet_map_1024.jpg/1200px-Internet_map_1024.jpg"> <meta property="og:image:width" content="1200"> <meta property="og:image:height" content="1200"> <meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/thumb/d/d2/Internet_map_1024.jpg/800px-Internet_map_1024.jpg"> <meta property="og:image:width" content="800"> <meta property="og:image:height" content="800"> <meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/thumb/d/d2/Internet_map_1024.jpg/640px-Internet_map_1024.jpg"> <meta property="og:image:width" content="640"> <meta property="og:image:height" content="640"> <meta name="viewport" content="width=1120"> <meta property="og:title" content="Stochastic block model - Wikipedia"> <meta property="og:type" content="website"> <link rel="preconnect" href="//upload.wikimedia.org"> <link rel="alternate" media="only screen and (max-width: 640px)" href="//en.m.wikipedia.org/wiki/Stochastic_block_model"> <link rel="alternate" type="application/x-wiki" title="Edit this page" href="/w/index.php?title=Stochastic_block_model&action=edit"> <link rel="apple-touch-icon" href="/static/apple-touch/wikipedia.png"> <link rel="icon" href="/static/favicon/wikipedia.ico"> <link rel="search" type="application/opensearchdescription+xml" href="/w/rest.php/v1/search" title="Wikipedia (en)"> <link rel="EditURI" type="application/rsd+xml" href="//en.wikipedia.org/w/api.php?action=rsd"> <link rel="canonical" href="https://en.wikipedia.org/wiki/Stochastic_block_model"> <link rel="license" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en"> <link rel="alternate" type="application/atom+xml" title="Wikipedia Atom feed" href="/w/index.php?title=Special:RecentChanges&feed=atom"> <link rel="dns-prefetch" href="//meta.wikimedia.org" /> <link rel="dns-prefetch" href="login.wikimedia.org"> </head> <body class="skin--responsive skin-vector skin-vector-search-vue mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject mw-editable page-Stochastic_block_model rootpage-Stochastic_block_model skin-vector-2022 action-view"><a class="mw-jump-link" href="#bodyContent">Jump to content</a> <div class="vector-header-container"> <header class="vector-header mw-header"> <div class="vector-header-start"> <nav class="vector-main-menu-landmark" aria-label="Site"> <div id="vector-main-menu-dropdown" class="vector-dropdown vector-main-menu-dropdown vector-button-flush-left vector-button-flush-right" > <input type="checkbox" id="vector-main-menu-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-main-menu-dropdown" class="vector-dropdown-checkbox " aria-label="Main menu" > <label id="vector-main-menu-dropdown-label" for="vector-main-menu-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-menu mw-ui-icon-wikimedia-menu"></span> <span class="vector-dropdown-label-text">Main menu</span> </label> <div class="vector-dropdown-content"> <div id="vector-main-menu-unpinned-container" class="vector-unpinned-container"> <div id="vector-main-menu" class="vector-main-menu vector-pinnable-element"> <div class="vector-pinnable-header vector-main-menu-pinnable-header vector-pinnable-header-unpinned" data-feature-name="main-menu-pinned" data-pinnable-element-id="vector-main-menu" data-pinned-container-id="vector-main-menu-pinned-container" data-unpinned-container-id="vector-main-menu-unpinned-container" > <div class="vector-pinnable-header-label">Main menu</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-main-menu.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-main-menu.unpin">hide</button> </div> <div id="p-navigation" class="vector-menu mw-portlet mw-portlet-navigation" > <div class="vector-menu-heading"> Navigation </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-mainpage-description" class="mw-list-item"><a href="/wiki/Main_Page" title="Visit the main page [z]" accesskey="z"><span>Main page</span></a></li><li id="n-contents" class="mw-list-item"><a href="/wiki/Wikipedia:Contents" title="Guides to browsing Wikipedia"><span>Contents</span></a></li><li id="n-currentevents" class="mw-list-item"><a href="/wiki/Portal:Current_events" title="Articles related to current events"><span>Current events</span></a></li><li id="n-randompage" class="mw-list-item"><a href="/wiki/Special:Random" title="Visit a randomly selected article [x]" accesskey="x"><span>Random article</span></a></li><li id="n-aboutsite" class="mw-list-item"><a href="/wiki/Wikipedia:About" title="Learn about Wikipedia and how it works"><span>About Wikipedia</span></a></li><li id="n-contactpage" class="mw-list-item"><a href="//en.wikipedia.org/wiki/Wikipedia:Contact_us" title="How to contact Wikipedia"><span>Contact us</span></a></li> </ul> </div> </div> <div id="p-interaction" class="vector-menu mw-portlet mw-portlet-interaction" > <div class="vector-menu-heading"> Contribute </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-help" class="mw-list-item"><a href="/wiki/Help:Contents" title="Guidance on how to use and edit Wikipedia"><span>Help</span></a></li><li id="n-introduction" class="mw-list-item"><a href="/wiki/Help:Introduction" title="Learn how to edit Wikipedia"><span>Learn to edit</span></a></li><li id="n-portal" class="mw-list-item"><a href="/wiki/Wikipedia:Community_portal" title="The hub for editors"><span>Community portal</span></a></li><li id="n-recentchanges" class="mw-list-item"><a href="/wiki/Special:RecentChanges" title="A list of recent changes to Wikipedia [r]" accesskey="r"><span>Recent changes</span></a></li><li id="n-upload" class="mw-list-item"><a href="/wiki/Wikipedia:File_upload_wizard" title="Add images or other media for use on Wikipedia"><span>Upload file</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> <a href="/wiki/Main_Page" class="mw-logo"> <img class="mw-logo-icon" src="/static/images/icons/wikipedia.png" alt="" aria-hidden="true" height="50" width="50"> <span class="mw-logo-container skin-invert"> <img class="mw-logo-wordmark" alt="Wikipedia" src="/static/images/mobile/copyright/wikipedia-wordmark-en.svg" style="width: 7.5em; height: 1.125em;"> <img class="mw-logo-tagline" alt="The Free Encyclopedia" src="/static/images/mobile/copyright/wikipedia-tagline-en.svg" width="117" height="13" style="width: 7.3125em; height: 0.8125em;"> </span> </a> </div> <div class="vector-header-end"> <div id="p-search" role="search" class="vector-search-box-vue vector-search-box-collapses vector-search-box-show-thumbnail vector-search-box-auto-expand-width vector-search-box"> <a href="/wiki/Special:Search" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only search-toggle" title="Search Wikipedia [f]" accesskey="f"><span class="vector-icon mw-ui-icon-search mw-ui-icon-wikimedia-search"></span> <span>Search</span> </a> <div class="vector-typeahead-search-container"> <div class="cdx-typeahead-search cdx-typeahead-search--show-thumbnail cdx-typeahead-search--auto-expand-width"> <form action="/w/index.php" id="searchform" class="cdx-search-input cdx-search-input--has-end-button"> <div id="simpleSearch" class="cdx-search-input__input-wrapper" data-search-loc="header-moved"> <div class="cdx-text-input cdx-text-input--has-start-icon"> <input class="cdx-text-input__input" type="search" name="search" placeholder="Search Wikipedia" aria-label="Search Wikipedia" autocapitalize="sentences" title="Search Wikipedia [f]" accesskey="f" id="searchInput" > <span class="cdx-text-input__icon cdx-text-input__start-icon"></span> </div> <input type="hidden" name="title" value="Special:Search"> </div> <button class="cdx-button cdx-search-input__end-button">Search</button> </form> </div> </div> </div> <nav class="vector-user-links vector-user-links-wide" aria-label="Personal tools"> <div class="vector-user-links-main"> <div id="p-vector-user-menu-preferences" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-userpage" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <nav class="vector-appearance-landmark" aria-label="Appearance"> <div id="vector-appearance-dropdown" class="vector-dropdown " title="Change the appearance of the page's font size, width, and color" > <input type="checkbox" id="vector-appearance-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-appearance-dropdown" class="vector-dropdown-checkbox " aria-label="Appearance" > <label id="vector-appearance-dropdown-label" for="vector-appearance-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-appearance mw-ui-icon-wikimedia-appearance"></span> <span class="vector-dropdown-label-text">Appearance</span> </label> <div class="vector-dropdown-content"> <div id="vector-appearance-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <div id="p-vector-user-menu-notifications" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-overflow" class="vector-menu mw-portlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="https://donate.wikimedia.org/?wmf_source=donate&wmf_medium=sidebar&wmf_campaign=en.wikipedia.org&uselang=en" class=""><span>Donate</span></a> </li> <li id="pt-createaccount-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Special:CreateAccount&returnto=Stochastic+block+model" title="You are encouraged to create an account and log in; however, it is not mandatory" class=""><span>Create account</span></a> </li> <li id="pt-login-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Special:UserLogin&returnto=Stochastic+block+model" title="You're encouraged to log in; however, it's not mandatory. [o]" accesskey="o" class=""><span>Log in</span></a> </li> </ul> </div> </div> </div> <div id="vector-user-links-dropdown" class="vector-dropdown vector-user-menu vector-button-flush-right vector-user-menu-logged-out" title="Log in and more options" > <input type="checkbox" id="vector-user-links-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-user-links-dropdown" class="vector-dropdown-checkbox " aria-label="Personal tools" > <label id="vector-user-links-dropdown-label" for="vector-user-links-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-ellipsis mw-ui-icon-wikimedia-ellipsis"></span> <span class="vector-dropdown-label-text">Personal tools</span> </label> <div class="vector-dropdown-content"> <div id="p-personal" class="vector-menu mw-portlet mw-portlet-personal user-links-collapsible-item" title="User menu" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport" class="user-links-collapsible-item mw-list-item"><a href="https://donate.wikimedia.org/?wmf_source=donate&wmf_medium=sidebar&wmf_campaign=en.wikipedia.org&uselang=en"><span>Donate</span></a></li><li id="pt-createaccount" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Special:CreateAccount&returnto=Stochastic+block+model" title="You are encouraged to create an account and log in; however, it is not mandatory"><span class="vector-icon mw-ui-icon-userAdd mw-ui-icon-wikimedia-userAdd"></span> <span>Create account</span></a></li><li id="pt-login" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Special:UserLogin&returnto=Stochastic+block+model" title="You're encouraged to log in; however, it's not mandatory. [o]" accesskey="o"><span class="vector-icon mw-ui-icon-logIn mw-ui-icon-wikimedia-logIn"></span> <span>Log in</span></a></li> </ul> </div> </div> <div id="p-user-menu-anon-editor" class="vector-menu mw-portlet mw-portlet-user-menu-anon-editor" > <div class="vector-menu-heading"> Pages for logged out editors <a href="/wiki/Help:Introduction" aria-label="Learn more about editing"><span>learn more</span></a> </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-anoncontribs" class="mw-list-item"><a href="/wiki/Special:MyContributions" title="A list of edits made from this IP address [y]" accesskey="y"><span>Contributions</span></a></li><li id="pt-anontalk" class="mw-list-item"><a href="/wiki/Special:MyTalk" title="Discussion about edits from this IP address [n]" accesskey="n"><span>Talk</span></a></li> </ul> </div> </div> </div> </div> </nav> </div> </header> </div> <div class="mw-page-container"> <div class="mw-page-container-inner"> <div class="vector-sitenotice-container"> <div id="siteNotice"></div> </div> <div class="vector-column-start"> <div class="vector-main-menu-container"> <div id="mw-navigation"> <nav id="mw-panel" class="vector-main-menu-landmark" aria-label="Site"> <div id="vector-main-menu-pinned-container" class="vector-pinned-container"> </div> </nav> </div> </div> <div class="vector-sticky-pinned-container"> <nav id="mw-panel-toc" aria-label="Contents" data-event-name="ui.sidebar-toc" class="mw-table-of-contents-container vector-toc-landmark"> <div id="vector-toc-pinned-container" class="vector-pinned-container"> <div id="vector-toc" class="vector-toc vector-pinnable-element"> <div class="vector-pinnable-header vector-toc-pinnable-header vector-pinnable-header-pinned" data-feature-name="toc-pinned" data-pinnable-element-id="vector-toc" > <h2 class="vector-pinnable-header-label">Contents</h2> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-toc.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-toc.unpin">hide</button> </div> <ul class="vector-toc-contents" id="mw-panel-toc-list"> <li id="toc-mw-content-text" class="vector-toc-list-item vector-toc-level-1"> <a href="#" class="vector-toc-link"> <div class="vector-toc-text">(Top)</div> </a> </li> <li id="toc-Definition" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Definition"> <div class="vector-toc-text"> <span class="vector-toc-numb">1</span> <span>Definition</span> </div> </a> <ul id="toc-Definition-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Special_cases" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Special_cases"> <div class="vector-toc-text"> <span class="vector-toc-numb">2</span> <span>Special cases</span> </div> </a> <ul id="toc-Special_cases-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Typical_statistical_tasks" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Typical_statistical_tasks"> <div class="vector-toc-text"> <span class="vector-toc-numb">3</span> <span>Typical statistical tasks</span> </div> </a> <button aria-controls="toc-Typical_statistical_tasks-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Toggle Typical statistical tasks subsection</span> </button> <ul id="toc-Typical_statistical_tasks-sublist" class="vector-toc-list"> <li id="toc-Detection" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Detection"> <div class="vector-toc-text"> <span class="vector-toc-numb">3.1</span> <span>Detection</span> </div> </a> <ul id="toc-Detection-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Partial_recovery" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Partial_recovery"> <div class="vector-toc-text"> <span class="vector-toc-numb">3.2</span> <span>Partial recovery</span> </div> </a> <ul id="toc-Partial_recovery-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Exact_recovery" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Exact_recovery"> <div class="vector-toc-text"> <span class="vector-toc-numb">3.3</span> <span>Exact recovery</span> </div> </a> <ul id="toc-Exact_recovery-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Statistical_lower_bounds_and_threshold_behavior" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Statistical_lower_bounds_and_threshold_behavior"> <div class="vector-toc-text"> <span class="vector-toc-numb">4</span> <span>Statistical lower bounds and threshold behavior</span> </div> </a> <ul id="toc-Statistical_lower_bounds_and_threshold_behavior-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Algorithms" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Algorithms"> <div class="vector-toc-text"> <span class="vector-toc-numb">5</span> <span>Algorithms</span> </div> </a> <ul id="toc-Algorithms-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Variants" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Variants"> <div class="vector-toc-text"> <span class="vector-toc-numb">6</span> <span>Variants</span> </div> </a> <ul id="toc-Variants-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Topic_models" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Topic_models"> <div class="vector-toc-text"> <span class="vector-toc-numb">7</span> <span>Topic models</span> </div> </a> <ul id="toc-Topic_models-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Extensions_to_signed_graphs" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Extensions_to_signed_graphs"> <div class="vector-toc-text"> <span class="vector-toc-numb">8</span> <span>Extensions to signed graphs</span> </div> </a> <ul id="toc-Extensions_to_signed_graphs-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-DARPA/MIT/AWS_Graph_Challenge:_streaming_stochastic_block_partition" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#DARPA/MIT/AWS_Graph_Challenge:_streaming_stochastic_block_partition"> <div class="vector-toc-text"> <span class="vector-toc-numb">9</span> <span>DARPA/MIT/AWS Graph Challenge: streaming stochastic block partition</span> </div> </a> <ul id="toc-DARPA/MIT/AWS_Graph_Challenge:_streaming_stochastic_block_partition-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-See_also" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#See_also"> <div class="vector-toc-text"> <span class="vector-toc-numb">10</span> <span>See also</span> </div> </a> <ul id="toc-See_also-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-References" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#References"> <div class="vector-toc-text"> <span class="vector-toc-numb">11</span> <span>References</span> </div> </a> <ul id="toc-References-sublist" class="vector-toc-list"> </ul> </li> </ul> </div> </div> </nav> </div> </div> <div class="mw-content-container"> <main id="content" class="mw-body"> <header class="mw-body-header vector-page-titlebar"> <nav aria-label="Contents" class="vector-toc-landmark"> <div id="vector-page-titlebar-toc" class="vector-dropdown vector-page-titlebar-toc vector-button-flush-left" > <input type="checkbox" id="vector-page-titlebar-toc-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-titlebar-toc" class="vector-dropdown-checkbox " aria-label="Toggle the table of contents" > <label id="vector-page-titlebar-toc-label" for="vector-page-titlebar-toc-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-listBullet mw-ui-icon-wikimedia-listBullet"></span> <span class="vector-dropdown-label-text">Toggle the table of contents</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-titlebar-toc-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Stochastic block model</span></h1> <div id="p-lang-btn" class="vector-dropdown mw-portlet mw-portlet-lang" > <input type="checkbox" id="p-lang-btn-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-p-lang-btn" class="vector-dropdown-checkbox mw-interlanguage-selector" aria-label="Go to an article in another language. Available in 5 languages" > <label id="p-lang-btn-label" for="p-lang-btn-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--action-progressive mw-portlet-lang-heading-5" aria-hidden="true" ><span class="vector-icon mw-ui-icon-language-progressive mw-ui-icon-wikimedia-language-progressive"></span> <span class="vector-dropdown-label-text">5 languages</span> </label> <div class="vector-dropdown-content"> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="interlanguage-link interwiki-ca mw-list-item"><a href="https://ca.wikipedia.org/wiki/Model_de_blocs_estoc%C3%A0stics" title="Model de blocs estocàstics – Catalan" lang="ca" hreflang="ca" data-title="Model de blocs estocàstics" data-language-autonym="Català" data-language-local-name="Catalan" class="interlanguage-link-target"><span>Català</span></a></li><li class="interlanguage-link interwiki-es mw-list-item"><a href="https://es.wikipedia.org/wiki/Modelo_de_bloque_estoc%C3%A1stico" title="Modelo de bloque estocástico – Spanish" lang="es" hreflang="es" data-title="Modelo de bloque estocástico" data-language-autonym="Español" data-language-local-name="Spanish" class="interlanguage-link-target"><span>Español</span></a></li><li class="interlanguage-link interwiki-fa mw-list-item"><a href="https://fa.wikipedia.org/wiki/%D9%85%D8%AF%D9%84_%D8%A8%D9%84%D9%88%DA%A9%DB%8C_%D8%AA%D8%B5%D8%A7%D8%AF%D9%81%DB%8C" title="مدل بلوکی تصادفی – Persian" lang="fa" hreflang="fa" data-title="مدل بلوکی تصادفی" data-language-autonym="فارسی" data-language-local-name="Persian" class="interlanguage-link-target"><span>فارسی</span></a></li><li class="interlanguage-link interwiki-he mw-list-item"><a href="https://he.wikipedia.org/wiki/%D7%9E%D7%95%D7%93%D7%9C_%D7%91%D7%9C%D7%95%D7%A7%D7%99%D7%9D_%D7%A1%D7%98%D7%95%D7%9B%D7%A1%D7%98%D7%99" title="מודל בלוקים סטוכסטי – Hebrew" lang="he" hreflang="he" data-title="מודל בלוקים סטוכסטי" data-language-autonym="עברית" data-language-local-name="Hebrew" class="interlanguage-link-target"><span>עברית</span></a></li><li class="interlanguage-link interwiki-zh-yue mw-list-item"><a href="https://zh-yue.wikipedia.org/wiki/%E9%9A%A8%E6%A9%9F%E5%A1%8A%E6%A8%A1%E5%9E%8B" title="隨機塊模型 – Cantonese" lang="yue" hreflang="yue" data-title="隨機塊模型" data-language-autonym="粵語" data-language-local-name="Cantonese" class="interlanguage-link-target"><span>粵語</span></a></li> </ul> <div class="after-portlet after-portlet-lang"><span class="wb-langlinks-edit wb-langlinks-link"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q25053762#sitelinks-wikipedia" title="Edit interlanguage links" class="wbc-editpage">Edit links</a></span></div> </div> </div> </div> </header> <div class="vector-page-toolbar"> <div class="vector-page-toolbar-container"> <div id="left-navigation"> <nav aria-label="Namespaces"> <div id="p-associated-pages" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-associated-pages" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-nstab-main" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/Stochastic_block_model" title="View the content page [c]" accesskey="c"><span>Article</span></a></li><li id="ca-talk" class="vector-tab-noicon mw-list-item"><a href="/wiki/Talk:Stochastic_block_model" rel="discussion" title="Discuss improvements to the content page [t]" accesskey="t"><span>Talk</span></a></li> </ul> </div> </div> <div id="vector-variants-dropdown" class="vector-dropdown emptyPortlet" > <input type="checkbox" id="vector-variants-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-variants-dropdown" class="vector-dropdown-checkbox " aria-label="Change language variant" > <label id="vector-variants-dropdown-label" for="vector-variants-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">English</span> </label> <div class="vector-dropdown-content"> <div id="p-variants" class="vector-menu mw-portlet mw-portlet-variants emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> </div> </div> </nav> </div> <div id="right-navigation" class="vector-collapsible"> <nav aria-label="Views"> <div id="p-views" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-views" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-view" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/Stochastic_block_model"><span>Read</span></a></li><li id="ca-edit" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Stochastic_block_model&action=edit" title="Edit this page [e]" accesskey="e"><span>Edit</span></a></li><li id="ca-history" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Stochastic_block_model&action=history" title="Past revisions of this page [h]" accesskey="h"><span>View history</span></a></li> </ul> </div> </div> </nav> <nav class="vector-page-tools-landmark" aria-label="Page tools"> <div id="vector-page-tools-dropdown" class="vector-dropdown vector-page-tools-dropdown" > <input type="checkbox" id="vector-page-tools-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-tools-dropdown" class="vector-dropdown-checkbox " aria-label="Tools" > <label id="vector-page-tools-dropdown-label" for="vector-page-tools-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">Tools</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-tools-unpinned-container" class="vector-unpinned-container"> <div id="vector-page-tools" class="vector-page-tools vector-pinnable-element"> <div class="vector-pinnable-header vector-page-tools-pinnable-header vector-pinnable-header-unpinned" data-feature-name="page-tools-pinned" data-pinnable-element-id="vector-page-tools" data-pinned-container-id="vector-page-tools-pinned-container" data-unpinned-container-id="vector-page-tools-unpinned-container" > <div class="vector-pinnable-header-label">Tools</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-page-tools.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-page-tools.unpin">hide</button> </div> <div id="p-cactions" class="vector-menu mw-portlet mw-portlet-cactions emptyPortlet vector-has-collapsible-items" title="More options" > <div class="vector-menu-heading"> Actions </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-more-view" class="selected vector-more-collapsible-item mw-list-item"><a href="/wiki/Stochastic_block_model"><span>Read</span></a></li><li id="ca-more-edit" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Stochastic_block_model&action=edit" title="Edit this page [e]" accesskey="e"><span>Edit</span></a></li><li id="ca-more-history" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Stochastic_block_model&action=history"><span>View history</span></a></li> </ul> </div> </div> <div id="p-tb" class="vector-menu mw-portlet mw-portlet-tb" > <div class="vector-menu-heading"> General </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="t-whatlinkshere" class="mw-list-item"><a href="/wiki/Special:WhatLinksHere/Stochastic_block_model" title="List of all English Wikipedia pages containing links to this page [j]" accesskey="j"><span>What links here</span></a></li><li id="t-recentchangeslinked" class="mw-list-item"><a href="/wiki/Special:RecentChangesLinked/Stochastic_block_model" rel="nofollow" title="Recent changes in pages linked from this page [k]" accesskey="k"><span>Related changes</span></a></li><li id="t-upload" class="mw-list-item"><a href="/wiki/Wikipedia:File_Upload_Wizard" title="Upload files [u]" accesskey="u"><span>Upload file</span></a></li><li id="t-specialpages" class="mw-list-item"><a href="/wiki/Special:SpecialPages" title="A list of all special pages [q]" accesskey="q"><span>Special pages</span></a></li><li id="t-permalink" class="mw-list-item"><a href="/w/index.php?title=Stochastic_block_model&oldid=1230624135" title="Permanent link to this revision of this page"><span>Permanent link</span></a></li><li id="t-info" class="mw-list-item"><a href="/w/index.php?title=Stochastic_block_model&action=info" title="More information about this page"><span>Page information</span></a></li><li id="t-cite" class="mw-list-item"><a href="/w/index.php?title=Special:CiteThisPage&page=Stochastic_block_model&id=1230624135&wpFormIdentifier=titleform" title="Information on how to cite this page"><span>Cite this page</span></a></li><li id="t-urlshortener" class="mw-list-item"><a href="/w/index.php?title=Special:UrlQ%C4%B1sald%C4%B1c%C4%B1s%C4%B1&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FStochastic_block_model"><span>Get shortened URL</span></a></li><li id="t-urlshortener-qrcode" class="mw-list-item"><a href="/w/index.php?title=Special:QrKodu&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FStochastic_block_model"><span>Download QR code</span></a></li> </ul> </div> </div> <div id="p-coll-print_export" class="vector-menu mw-portlet mw-portlet-coll-print_export" > <div class="vector-menu-heading"> Print/export </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="coll-download-as-rl" class="mw-list-item"><a href="/w/index.php?title=Special:DownloadAsPdf&page=Stochastic_block_model&action=show-download-screen" title="Download this page as a PDF file"><span>Download as PDF</span></a></li><li id="t-print" class="mw-list-item"><a href="/w/index.php?title=Stochastic_block_model&printable=yes" title="Printable version of this page [p]" accesskey="p"><span>Printable version</span></a></li> </ul> </div> </div> <div id="p-wikibase-otherprojects" class="vector-menu mw-portlet mw-portlet-wikibase-otherprojects" > <div class="vector-menu-heading"> In other projects </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="t-wikibase" class="wb-otherproject-link wb-otherproject-wikibase-dataitem mw-list-item"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q25053762" title="Structured data on this page hosted by Wikidata [g]" accesskey="g"><span>Wikidata item</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> </div> </div> </div> <div class="vector-column-end"> <div class="vector-sticky-pinned-container"> <nav class="vector-page-tools-landmark" aria-label="Page tools"> <div id="vector-page-tools-pinned-container" class="vector-pinned-container"> </div> </nav> <nav class="vector-appearance-landmark" aria-label="Appearance"> <div id="vector-appearance-pinned-container" class="vector-pinned-container"> <div id="vector-appearance" class="vector-appearance vector-pinnable-element"> <div class="vector-pinnable-header vector-appearance-pinnable-header vector-pinnable-header-pinned" data-feature-name="appearance-pinned" data-pinnable-element-id="vector-appearance" data-pinned-container-id="vector-appearance-pinned-container" data-unpinned-container-id="vector-appearance-unpinned-container" > <div class="vector-pinnable-header-label">Appearance</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-appearance.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-appearance.unpin">hide</button> </div> </div> </div> </nav> </div> </div> <div id="bodyContent" class="vector-body" aria-labelledby="firstHeading" data-mw-ve-target-container> <div class="vector-body-before-content"> <div class="mw-indicators"> </div> <div id="siteSub" class="noprint">From Wikipedia, the free encyclopedia</div> </div> <div id="contentSub"><div id="mw-content-subtitle"></div></div> <div id="mw-content-text" class="mw-body-content"><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr"><style data-mw-deduplicate="TemplateStyles:r1129693374">.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}</style><style data-mw-deduplicate="TemplateStyles:r1246091330">.mw-parser-output .sidebar{width:22em;float:right;clear:right;margin:0.5em 0 1em 1em;background:var(--background-color-neutral-subtle,#f8f9fa);border:1px solid var(--border-color-base,#a2a9b1);padding:0.2em;text-align:center;line-height:1.4em;font-size:88%;border-collapse:collapse;display:table}body.skin-minerva .mw-parser-output .sidebar{display:table!important;float:right!important;margin:0.5em 0 1em 1em!important}.mw-parser-output .sidebar-subgroup{width:100%;margin:0;border-spacing:0}.mw-parser-output .sidebar-left{float:left;clear:left;margin:0.5em 1em 1em 0}.mw-parser-output .sidebar-none{float:none;clear:both;margin:0.5em 1em 1em 0}.mw-parser-output .sidebar-outer-title{padding:0 0.4em 0.2em;font-size:125%;line-height:1.2em;font-weight:bold}.mw-parser-output .sidebar-top-image{padding:0.4em}.mw-parser-output .sidebar-top-caption,.mw-parser-output .sidebar-pretitle-with-top-image,.mw-parser-output .sidebar-caption{padding:0.2em 0.4em 0;line-height:1.2em}.mw-parser-output .sidebar-pretitle{padding:0.4em 0.4em 0;line-height:1.2em}.mw-parser-output .sidebar-title,.mw-parser-output .sidebar-title-with-pretitle{padding:0.2em 0.8em;font-size:145%;line-height:1.2em}.mw-parser-output .sidebar-title-with-pretitle{padding:0.1em 0.4em}.mw-parser-output .sidebar-image{padding:0.2em 0.4em 0.4em}.mw-parser-output .sidebar-heading{padding:0.1em 0.4em}.mw-parser-output .sidebar-content{padding:0 0.5em 0.4em}.mw-parser-output .sidebar-content-with-subgroup{padding:0.1em 0.4em 0.2em}.mw-parser-output .sidebar-above,.mw-parser-output .sidebar-below{padding:0.3em 0.8em;font-weight:bold}.mw-parser-output .sidebar-collapse .sidebar-above,.mw-parser-output .sidebar-collapse .sidebar-below{border-top:1px solid #aaa;border-bottom:1px solid #aaa}.mw-parser-output .sidebar-navbar{text-align:right;font-size:115%;padding:0 0.4em 0.4em}.mw-parser-output .sidebar-list-title{padding:0 0.4em;text-align:left;font-weight:bold;line-height:1.6em;font-size:105%}.mw-parser-output .sidebar-list-title-c{padding:0 0.4em;text-align:center;margin:0 3.3em}@media(max-width:640px){body.mediawiki .mw-parser-output .sidebar{width:100%!important;clear:both;float:none!important;margin-left:0!important;margin-right:0!important}}body.skin--responsive .mw-parser-output .sidebar a>img{max-width:none!important}@media screen{html.skin-theme-clientpref-night .mw-parser-output .sidebar:not(.notheme) .sidebar-list-title,html.skin-theme-clientpref-night .mw-parser-output .sidebar:not(.notheme) .sidebar-title-with-pretitle{background:transparent!important}html.skin-theme-clientpref-night .mw-parser-output .sidebar:not(.notheme) .sidebar-title-with-pretitle a{color:var(--color-progressive)!important}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .sidebar:not(.notheme) .sidebar-list-title,html.skin-theme-clientpref-os .mw-parser-output .sidebar:not(.notheme) .sidebar-title-with-pretitle{background:transparent!important}html.skin-theme-clientpref-os .mw-parser-output .sidebar:not(.notheme) .sidebar-title-with-pretitle a{color:var(--color-progressive)!important}}@media print{body.ns-0 .mw-parser-output .sidebar{display:none!important}}</style><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1129693374"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1129693374"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1129693374"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1246091330"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1246091330"><table class="sidebar nomobile nowraplinks"><tbody><tr><td class="sidebar-pretitle" style="padding-bottom:0.15em;">Part of <a href="/wiki/Category:Network_science" title="Category:Network science">a series</a> on</td></tr><tr><th class="sidebar-title-with-pretitle" style="font-size:175%;"><a href="/wiki/Network_science" title="Network science">Network science</a></th></tr><tr><td class="sidebar-image"><div class="center"><div class="center"> <div style="width: 250px; height: 250px; overflow: hidden;"> <div style="position: relative; top: -0px; left: -0px; width: 250px"><div class="noresize"><span typeof="mw:File"><a href="/wiki/File:Internet_map_1024.jpg" class="mw-file-description"><img alt="Internet_map_1024.jpg" src="//upload.wikimedia.org/wikipedia/commons/thumb/d/d2/Internet_map_1024.jpg/250px-Internet_map_1024.jpg" decoding="async" width="250" height="250" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/d/d2/Internet_map_1024.jpg/375px-Internet_map_1024.jpg 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/d/d2/Internet_map_1024.jpg/500px-Internet_map_1024.jpg 2x" data-file-width="1280" data-file-height="1280" /></a></span></div></div> </div> </div></div></td></tr><tr><th class="sidebar-heading"> <div class="hlist"><ul><li><a href="/wiki/Network_theory" title="Network theory">Theory</a></li></ul></div></th></tr><tr><td class="sidebar-content hlist" style="padding-top:0.2em;padding-bottom:0.5em;"> <ul><li><a href="/wiki/Graph_(discrete_mathematics)" title="Graph (discrete mathematics)">Graph</a></li> <li><a href="/wiki/Complex_network" title="Complex network">Complex network</a></li> <li><a href="/wiki/Complex_contagion" title="Complex contagion">Contagion</a></li> <li><a href="/wiki/Small-world_network" title="Small-world network">Small-world</a></li> <li><a href="/wiki/Scale-free_network" title="Scale-free network">Scale-free</a></li> <li><a href="/wiki/Community_structure" title="Community structure">Community structure</a></li> <li><a href="/wiki/Percolation_theory" title="Percolation theory">Percolation</a></li> <li><a href="/wiki/Evolving_networks" class="mw-redirect" title="Evolving networks">Evolution</a></li> <li><a href="/wiki/Network_controllability" title="Network controllability">Controllability</a></li> <li><a href="/wiki/Graph_drawing" title="Graph drawing">Graph drawing</a></li> <li><a href="/wiki/Social_capital" title="Social capital">Social capital</a></li> <li><a href="/wiki/Link_analysis" title="Link analysis">Link analysis</a></li> <li><a href="/wiki/Combinatorial_optimization" title="Combinatorial optimization">Optimization</a></li> <li><a href="/wiki/Reciprocity_(network_science)" title="Reciprocity (network science)">Reciprocity</a></li> <li><a href="/wiki/Triadic_closure" title="Triadic closure">Closure</a></li> <li><a href="/wiki/Homophily" title="Homophily">Homophily</a></li> <li><a href="/wiki/Transitive_relation" title="Transitive relation">Transitivity</a></li> <li><a href="/wiki/Preferential_attachment" title="Preferential attachment">Preferential attachment</a></li> <li><a href="/wiki/Balance_theory" title="Balance theory">Balance theory</a></li> <li><a href="/wiki/Network_effect" title="Network effect">Network effect</a></li> <li><a href="/wiki/Social_influence" title="Social influence">Social influence</a></li></ul></td> </tr><tr><th class="sidebar-heading"> Network types</th></tr><tr><td class="sidebar-content hlist" style="padding-top:0.2em;padding-bottom:0.5em;"> <ul><li><a href="/wiki/Computer_network" title="Computer network">Informational (computing)</a></li> <li><a href="/wiki/Telecommunications_network" title="Telecommunications network">Telecommunication</a></li> <li><a href="/wiki/Transport_network" class="mw-redirect" title="Transport network">Transport</a></li> <li><a href="/wiki/Social_network" title="Social network">Social</a></li> <li><a href="/wiki/Scientific_collaboration_network" title="Scientific collaboration network">Scientific collaboration</a></li> <li><a href="/wiki/Biological_network" title="Biological network">Biological</a></li> <li><a href="/wiki/Artificial_neural_network" class="mw-redirect" title="Artificial neural network">Artificial neural</a></li> <li><a href="/wiki/Interdependent_networks" title="Interdependent networks">Interdependent</a></li> <li><a href="/wiki/Semantic_network" title="Semantic network">Semantic</a></li> <li><a href="/wiki/Spatial_network" title="Spatial network">Spatial</a></li> <li><a href="/wiki/Dependency_network" title="Dependency network">Dependency</a></li> <li><a href="/wiki/Flow_network" title="Flow network">Flow</a></li> <li><a href="/wiki/Network_on_a_chip" title="Network on a chip">on-Chip</a></li></ul></td> </tr><tr><th class="sidebar-heading"> <a href="/wiki/Graph_(discrete_mathematics)" title="Graph (discrete mathematics)">Graphs</a></th></tr><tr><td class="sidebar-content hlist" style="padding-top:0.2em;padding-bottom:0.5em;"> <table class="sidebar nomobile nowraplinks" style="background-color: transparent; color: var( --color-base ); border-collapse:collapse; border-spacing:0px; border:none; width:100%; margin:0px; font-size:100%; clear:none; float:none"><tbody><tr><th class="sidebar-heading" style="font-weight:normal;font-style:italic;"> Features</th></tr><tr><td class="sidebar-content"> <ul><li><a href="/wiki/Clique_(graph_theory)" title="Clique (graph theory)">Clique</a></li> <li><a href="/wiki/Connected_component_(graph_theory)" class="mw-redirect" title="Connected component (graph theory)">Component</a></li> <li><a href="/wiki/Cut_(graph_theory)" title="Cut (graph theory)">Cut</a></li> <li><a href="/wiki/Cycle_(graph_theory)" title="Cycle (graph theory)">Cycle</a></li> <li><a href="/wiki/Graph_(abstract_data_type)" title="Graph (abstract data type)">Data structure</a></li> <li><a href="/wiki/Edge_(graph_theory)" class="mw-redirect" title="Edge (graph theory)">Edge</a></li> <li><a href="/wiki/Loop_(graph_theory)" title="Loop (graph theory)">Loop</a></li> <li><a href="/wiki/Neighbourhood_(graph_theory)" title="Neighbourhood (graph theory)">Neighborhood</a></li> <li><a href="/wiki/Path_(graph_theory)" title="Path (graph theory)">Path</a></li> <li><a href="/wiki/Vertex_(graph_theory)" title="Vertex (graph theory)">Vertex</a></li> <li><span class="nowrap"><a href="/wiki/Adjacency_list" title="Adjacency list">Adjacency list</a> / <a href="/wiki/Adjacency_matrix" title="Adjacency matrix">matrix</a></span></li> <li><span class="nowrap"><a href="/wiki/Incidence_list" class="mw-redirect" title="Incidence list">Incidence list</a> / <a href="/wiki/Incidence_matrix" title="Incidence matrix">matrix</a></span></li></ul></td> </tr><tr><th class="sidebar-heading" style="font-weight:normal;font-style:italic;"> Types</th></tr><tr><td class="sidebar-content"> <ul><li><a href="/wiki/Bipartite_graph" title="Bipartite graph">Bipartite</a></li> <li><a href="/wiki/Complete_graph" title="Complete graph">Complete</a></li> <li><a href="/wiki/Directed_graph" title="Directed graph">Directed</a></li> <li><a href="/wiki/Hypergraph" title="Hypergraph">Hyper</a></li> <li><a href="/wiki/Labeled_graph" class="mw-redirect" title="Labeled graph">Labeled</a></li> <li><a href="/wiki/Multigraph" title="Multigraph">Multi</a></li> <li><a href="/wiki/Random_graph" title="Random graph">Random</a></li> <li><a href="/wiki/Weighted_graph" class="mw-redirect" title="Weighted graph">Weighted</a></li></ul></td> </tr></tbody></table></td> </tr><tr><th class="sidebar-heading"> <div class="hlist"><ul><li><a href="/wiki/Metrics_(networking)" title="Metrics (networking)">Metrics</a></li><li><a href="/wiki/List_of_algorithms#Networking" title="List of algorithms">Algorithms</a></li></ul></div></th></tr><tr><td class="sidebar-content hlist" style="padding-top:0.2em;padding-bottom:0.5em;"> <ul><li><a href="/wiki/Centrality" title="Centrality">Centrality</a></li> <li><a href="/wiki/Degree_(graph_theory)" title="Degree (graph theory)">Degree</a></li> <li><a href="/wiki/Network_motif" title="Network motif">Motif</a></li> <li><a href="/wiki/Clustering_coefficient" title="Clustering coefficient">Clustering</a></li> <li><a href="/wiki/Degree_distribution" title="Degree distribution">Degree distribution</a></li> <li><a href="/wiki/Assortativity" title="Assortativity">Assortativity</a></li> <li><a href="/wiki/Distance_(graph_theory)" title="Distance (graph theory)">Distance</a></li> <li><a href="/wiki/Modularity_(networks)" title="Modularity (networks)">Modularity</a></li> <li><a href="/wiki/Efficiency_(network_science)" title="Efficiency (network science)">Efficiency</a></li></ul></td> </tr><tr><th class="sidebar-heading"> Models</th></tr><tr><td class="sidebar-content hlist" style="padding-top:0.2em;padding-bottom:0.5em;"> <table class="sidebar nomobile nowraplinks" style="background-color: transparent; color: var( --color-base ); border-collapse:collapse; border-spacing:0px; border:none; width:100%; margin:0px; font-size:100%; clear:none; float:none"><tbody><tr><th class="sidebar-heading" style="font-weight:normal;font-style:italic;"> Topology</th></tr><tr><td class="sidebar-content"> <ul><li><a href="/wiki/Random_graph" title="Random graph">Random graph</a></li> <li><a href="/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model" title="Erdős–Rényi model">Erdős–Rényi</a></li> <li><a href="/wiki/Barab%C3%A1si%E2%80%93Albert_model" title="Barabási–Albert model">Barabási–Albert</a></li> <li><a href="/wiki/Bianconi%E2%80%93Barab%C3%A1si_model" title="Bianconi–Barabási model">Bianconi–Barabási</a></li> <li><a href="/wiki/Fitness_model_(network_theory)" title="Fitness model (network theory)">Fitness model</a></li> <li><a href="/wiki/Watts%E2%80%93Strogatz_model" title="Watts–Strogatz model">Watts–Strogatz</a></li> <li><a href="/wiki/Exponential_random_graph_models" class="mw-redirect" title="Exponential random graph models">Exponential random (ERGM)</a></li> <li><a href="/wiki/Random_geometric_graph" title="Random geometric graph">Random geometric (RGG)</a></li> <li><a href="/wiki/Hyperbolic_geometric_graph" title="Hyperbolic geometric graph">Hyperbolic (HGN)</a></li> <li><a href="/wiki/Hierarchical_network_model" title="Hierarchical network model">Hierarchical</a></li> <li><a class="mw-selflink selflink">Stochastic block</a></li> <li><a href="/wiki/Blockmodeling" title="Blockmodeling">Blockmodeling</a></li> <li><a href="/wiki/Maximum-entropy_random_graph_model" title="Maximum-entropy random graph model">Maximum entropy</a></li> <li><a href="/wiki/Soft_configuration_model" title="Soft configuration model">Soft configuration</a></li> <li><a href="/wiki/Lancichinetti%E2%80%93Fortunato%E2%80%93Radicchi_benchmark" title="Lancichinetti–Fortunato–Radicchi benchmark">LFR Benchmark</a></li></ul></td> </tr><tr><th class="sidebar-heading" style="font-weight:normal;font-style:italic;"> Dynamics</th></tr><tr><td class="sidebar-content"> <ul><li><a href="/wiki/Boolean_network" title="Boolean network">Boolean network</a></li> <li><a href="/wiki/Agent-based_model" title="Agent-based model">agent based</a></li> <li><a href="/wiki/Epidemic_model" class="mw-redirect" title="Epidemic model">Epidemic</a>/<a href="/wiki/SIR_model" class="mw-redirect" title="SIR model">SIR</a></li></ul></td> </tr></tbody></table></td> </tr><tr><th class="sidebar-heading"> <div class="hlist"><ul><li>Lists</li><li>Categories</li></ul></div></th></tr><tr><td class="sidebar-content hlist" style="padding-top:0.2em;padding-bottom:0.5em;"> <ul><li><a href="/wiki/List_of_network_theory_topics" title="List of network theory topics">Topics</a></li> <li><a href="/wiki/Social_network_analysis_software" title="Social network analysis software">Software</a></li> <li><a href="/wiki/List_of_network_scientists" title="List of network scientists">Network scientists</a></li></ul> <ul><li><a href="/wiki/Category:Network_theory" title="Category:Network theory">Category:Network theory</a></li> <li><a href="/wiki/Category:Graph_theory" title="Category:Graph theory">Category:Graph theory</a></li></ul></td> </tr><tr><td class="sidebar-navbar"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1129693374"><style data-mw-deduplicate="TemplateStyles:r1239400231">.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}</style><div class="navbar plainlinks hlist navbar-mini"><ul><li class="nv-view"><a href="/wiki/Template:Network_science" title="Template:Network science"><abbr title="View this template">v</abbr></a></li><li class="nv-talk"><a href="/wiki/Template_talk:Network_science" title="Template talk:Network science"><abbr title="Discuss this template">t</abbr></a></li><li class="nv-edit"><a href="/wiki/Special:EditPage/Template:Network_science" title="Special:EditPage/Template:Network science"><abbr title="Edit this template">e</abbr></a></li></ul></div></td></tr></tbody></table> <p>The <b>stochastic <a href="/wiki/Blockmodel" class="mw-redirect" title="Blockmodel">block model</a></b> is a <a href="/wiki/Generative_model" title="Generative model">generative model</a> for random <a href="/wiki/Graph_(discrete_mathematics)" title="Graph (discrete mathematics)">graphs</a>. This model tends to produce graphs containing <i>communities</i>, subsets of nodes characterized by being connected with one another with particular edge densities. For example, edges may be more common within communities than between communities. Its mathematical formulation was first introduced in 1983 in the field of social network analysis by <a href="/wiki/Paul_W._Holland" title="Paul W. Holland">Paul W. Holland</a> et al.<sup id="cite_ref-hol_1-0" class="reference"><a href="#cite_note-hol-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> The stochastic block model is important in <a href="/wiki/Statistics" title="Statistics">statistics</a>, <a href="/wiki/Machine_learning" title="Machine learning">machine learning</a>, and <a href="/wiki/Network_science" title="Network science">network science</a>, where it serves as a useful benchmark for the task of recovering <a href="/wiki/Community_structure" title="Community structure">community structure</a> in graph data. </p> <meta property="mw:PageProp/toc" /> <div class="mw-heading mw-heading2"><h2 id="Definition">Definition</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Stochastic_block_model&action=edit&section=1" title="Edit section: Definition"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The stochastic block model takes the following parameters: </p> <ul><li>The number <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}"></span> of vertices;</li> <li>a partition of the vertex set <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{1,\ldots ,n\}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo fence="false" stretchy="false">{</mo> <mn>1</mn> <mo>,</mo> <mo>…</mo> <mo>,</mo> <mi>n</mi> <mo fence="false" stretchy="false">}</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \{1,\ldots ,n\}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/0401c38cf1a2e51b30b38f4b93b5285aa77f8fad" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.06ex; height:2.843ex;" alt="{\displaystyle \{1,\ldots ,n\}}"></span> into disjoint subsets <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C_{1},\ldots ,C_{r}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>C</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>,</mo> <mo>…</mo> <mo>,</mo> <msub> <mi>C</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>r</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle C_{1},\ldots ,C_{r}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ea48991a0db877bf2b03adda419a85fb67aa80bb" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:10.53ex; height:2.509ex;" alt="{\displaystyle C_{1},\ldots ,C_{r}}"></span>, called <i>communities</i>;</li> <li>a symmetric <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r\times r}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>r</mi> <mo>×</mo> <mi>r</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle r\times r}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8cafa6704e1fd8023c39b942b2158f07f9bf1fc5" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.938ex; height:1.676ex;" alt="{\displaystyle r\times r}"></span> matrix <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>P</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle P}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b4dc73bf40314945ff376bd363916a738548d40a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}"></span> of edge probabilities.</li></ul> <p>The edge set is then sampled at random as follows: any two vertices <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle u\in C_{i}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>u</mi> <mo>∈</mo> <msub> <mi>C</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle u\in C_{i}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/57e4e25b2cbc01159fe6286abc7690a1eaa10d7d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.632ex; height:2.509ex;" alt="{\displaystyle u\in C_{i}}"></span> and <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v\in C_{j}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>v</mi> <mo>∈</mo> <msub> <mi>C</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>j</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle v\in C_{j}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2da0495637390b212d04c4bc76004e7d3329edb3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:6.54ex; height:2.843ex;" alt="{\displaystyle v\in C_{j}}"></span> are connected by an edge with probability <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P_{ij}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>P</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> <mi>j</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle P_{ij}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/43ef37c239b6d38f1e951a31eb1a3bd295271b40" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.969ex; height:2.843ex;" alt="{\displaystyle P_{ij}}"></span>. An example problem is: given a graph with <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}"></span> vertices, where the edges are sampled as described, recover the groups <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C_{1},\ldots ,C_{r}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>C</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>,</mo> <mo>…</mo> <mo>,</mo> <msub> <mi>C</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>r</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle C_{1},\ldots ,C_{r}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ea48991a0db877bf2b03adda419a85fb67aa80bb" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:10.53ex; height:2.509ex;" alt="{\displaystyle C_{1},\ldots ,C_{r}}"></span>. </p> <div class="mw-heading mw-heading2"><h2 id="Special_cases">Special cases</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Stochastic_block_model&action=edit&section=2" title="Edit section: Special cases"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <figure typeof="mw:File/Thumb"><a href="/wiki/File:Assortative_Case_of_the_SBM.png" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/c/c7/Assortative_Case_of_the_SBM.png/149px-Assortative_Case_of_the_SBM.png" decoding="async" width="149" height="124" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/c/c7/Assortative_Case_of_the_SBM.png/224px-Assortative_Case_of_the_SBM.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/c/c7/Assortative_Case_of_the_SBM.png/298px-Assortative_Case_of_the_SBM.png 2x" data-file-width="2700" data-file-height="2250" /></a><figcaption>An example of the assortative case for the stochastic block model.</figcaption></figure> <p>If the probability matrix is a constant, in the sense that <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P_{ij}=p}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>P</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> <mi>j</mi> </mrow> </msub> <mo>=</mo> <mi>p</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle P_{ij}=p}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4e88adf8ec84bf231ed001abcc3eb88ffa30bb30" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:7.237ex; height:2.843ex;" alt="{\displaystyle P_{ij}=p}"></span> for all <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i,j}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>i</mi> <mo>,</mo> <mi>j</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle i,j}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f4cbf8bbc622154cda8208d6e339495fe16a1f9a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.794ex; height:2.509ex;" alt="{\displaystyle i,j}"></span>, then the result is the <a href="/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model" title="Erdős–Rényi model">Erdős–Rényi model</a> <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G(n,p)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>G</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo>,</mo> <mi>p</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle G(n,p)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ad8d6ba8bbe18701bed34c2d5106de6a56e35e08" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.234ex; height:2.843ex;" alt="{\displaystyle G(n,p)}"></span>. This case is degenerate—the partition into communities becomes irrelevant—but it illustrates a close relationship to the Erdős–Rényi model. </p><p>The <i>planted partition model</i> is the special case that the values of the probability matrix <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>P</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle P}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b4dc73bf40314945ff376bd363916a738548d40a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}"></span> are a constant <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>p</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle p}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/81eac1e205430d1f40810df36a0edffdc367af36" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:1.259ex; height:2.009ex;" alt="{\displaystyle p}"></span> on the diagonal and another constant <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>q</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle q}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/06809d64fa7c817ffc7e323f85997f783dbdf71d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.07ex; height:2.009ex;" alt="{\displaystyle q}"></span> off the diagonal. Thus two vertices within the same community share an edge with probability <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>p</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle p}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/81eac1e205430d1f40810df36a0edffdc367af36" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:1.259ex; height:2.009ex;" alt="{\displaystyle p}"></span>, while two vertices in different communities share an edge with probability <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>q</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle q}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/06809d64fa7c817ffc7e323f85997f783dbdf71d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.07ex; height:2.009ex;" alt="{\displaystyle q}"></span>. Sometimes it is this restricted model that is called the stochastic block model. The case where <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p>q}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>p</mi> <mo>></mo> <mi>q</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle p>q}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/3988956bbb7d322230b1aedcf7c5e3121da6edf4" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:5.427ex; height:2.176ex;" alt="{\displaystyle p>q}"></span> is called an <i>assortative</i> model, while the case <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p<q}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>p</mi> <mo><</mo> <mi>q</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle p<q}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9f86c7ea4068f76f93c6a2a92c849c27303c9ba9" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:5.427ex; height:2.176ex;" alt="{\displaystyle p<q}"></span> is called <i>disassortative</i>. </p><p>Returning to the general stochastic block model, a model is called <i>strongly assortative</i> if <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P_{ii}>P_{jk}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>P</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> <mi>i</mi> </mrow> </msub> <mo>></mo> <msub> <mi>P</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>j</mi> <mi>k</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle P_{ii}>P_{jk}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/32ab8b73e3f0a52e4c31ac79c41f11b29534085c" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:9.216ex; height:2.843ex;" alt="{\displaystyle P_{ii}>P_{jk}}"></span> whenever <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle j\neq k}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>j</mi> <mo>≠</mo> <mi>k</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle j\neq k}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a08a8f7e7c65621ea80f6989770e39aa591d0886" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; margin-left: -0.027ex; width:5.294ex; height:2.676ex;" alt="{\displaystyle j\neq k}"></span>: all diagonal entries dominate all off-diagonal entries. A model is called <i>weakly assortative</i> if <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P_{ii}>P_{ij}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>P</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> <mi>i</mi> </mrow> </msub> <mo>></mo> <msub> <mi>P</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> <mi>j</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle P_{ii}>P_{ij}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/bf7f7890d7deb67f517b74404eb9003dcd64d84e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:8.927ex; height:2.843ex;" alt="{\displaystyle P_{ii}>P_{ij}}"></span> whenever <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i\neq j}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>i</mi> <mo>≠</mo> <mi>j</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle i\neq j}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d95aeb406bb427ac96806bc00c30c91d31b858be" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.859ex; height:2.676ex;" alt="{\displaystyle i\neq j}"></span>: each diagonal entry is only required to dominate the rest of its own row and column.<sup id="cite_ref-al14_2-0" class="reference"><a href="#cite_note-al14-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> <i>Disassortative</i> forms of this terminology exist, by reversing all inequalities. For some algorithms, recovery might be easier for block models with assortative or disassortative conditions of this form.<sup id="cite_ref-al14_2-1" class="reference"><a href="#cite_note-al14-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading2"><h2 id="Typical_statistical_tasks">Typical statistical tasks</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Stochastic_block_model&action=edit&section=3" title="Edit section: Typical statistical tasks"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Much of the literature on algorithmic community detection addresses three statistical tasks: detection, partial recovery, and exact recovery. </p> <div class="mw-heading mw-heading3"><h3 id="Detection">Detection</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Stochastic_block_model&action=edit&section=4" title="Edit section: Detection"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The goal of detection algorithms is simply to determine, given a sampled graph, whether the graph has latent community structure. More precisely, a graph might be generated, with some known prior probability, from a known stochastic block model, and otherwise from a similar <a href="/wiki/Erdos-Renyi_model" class="mw-redirect" title="Erdos-Renyi model">Erdos-Renyi model</a>. The algorithmic task is to correctly identify which of these two underlying models generated the graph.<sup id="cite_ref-mns12_3-0" class="reference"><a href="#cite_note-mns12-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading3"><h3 id="Partial_recovery">Partial recovery</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Stochastic_block_model&action=edit&section=5" title="Edit section: Partial recovery"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>In partial recovery, the goal is to approximately determine the latent partition into communities, in the sense of finding a partition that is correlated with the true partition significantly better than a random guess.<sup id="cite_ref-mas13_4-0" class="reference"><a href="#cite_note-mas13-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading3"><h3 id="Exact_recovery">Exact recovery</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Stochastic_block_model&action=edit&section=6" title="Edit section: Exact recovery"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>In exact recovery, the goal is to recover the latent partition into communities exactly. The community sizes and probability matrix may be known<sup id="cite_ref-as15a_5-0" class="reference"><a href="#cite_note-as15a-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> or unknown.<sup id="cite_ref-as15b_6-0" class="reference"><a href="#cite_note-as15b-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading2"><h2 id="Statistical_lower_bounds_and_threshold_behavior">Statistical lower bounds and threshold behavior</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Stochastic_block_model&action=edit&section=7" title="Edit section: Statistical lower bounds and threshold behavior"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Stochastic block models exhibit a sharp threshold effect reminiscent of <a href="/wiki/Percolation_threshold" title="Percolation threshold">percolation thresholds</a>.<sup id="cite_ref-decelle11_7-0" class="reference"><a href="#cite_note-decelle11-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-mns12_3-1" class="reference"><a href="#cite_note-mns12-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-abh14_8-0" class="reference"><a href="#cite_note-abh14-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup> Suppose that we allow the size <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}"></span> of the graph to grow, keeping the community sizes in fixed proportions. If the probability matrix remains fixed, tasks such as partial and exact recovery become feasible for all non-degenerate parameter settings. However, if we scale down the probability matrix at a suitable rate as <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}"></span> increases, we observe a sharp phase transition: for certain settings of the parameters, it will become possible to achieve recovery with probability tending to 1, whereas on the opposite side of the parameter threshold, the probability of recovery tends to 0 no matter what algorithm is used. </p><p>For partial recovery, the appropriate scaling is to take <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P_{ij}={\tilde {P}}_{ij}/n}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>P</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> <mi>j</mi> </mrow> </msub> <mo>=</mo> <msub> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mover> <mi>P</mi> <mo stretchy="false">~</mo> </mover> </mrow> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> <mi>j</mi> </mrow> </msub> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle P_{ij}={\tilde {P}}_{ij}/n}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e46e2cbb525c6e5f769aa2bc1064b0553260fec8" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:11.914ex; height:3.343ex;" alt="{\displaystyle P_{ij}={\tilde {P}}_{ij}/n}"></span> for fixed <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\tilde {P}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mover> <mi>P</mi> <mo stretchy="false">~</mo> </mover> </mrow> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\tilde {P}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/35fe26950ee93b159b4a231946709804af1f5963" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.812ex; height:2.676ex;" alt="{\displaystyle {\tilde {P}}}"></span>, resulting in graphs of constant average degree. In the case of two equal-sized communities, in the assortative planted partition model with probability matrix <span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P=\left({\begin{array}{cc}{\tilde {p}}/n&{\tilde {q}}/n\\{\tilde {q}}/n&{\tilde {p}}/n\end{array}}\right),}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>P</mi> <mo>=</mo> <mrow> <mo>(</mo> <mrow class="MJX-TeXAtom-ORD"> <mtable columnalign="center center" rowspacing="4pt" columnspacing="1em"> <mtr> <mtd> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mover> <mi>p</mi> <mo stretchy="false">~</mo> </mover> </mrow> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mi>n</mi> </mtd> <mtd> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mover> <mi>q</mi> <mo stretchy="false">~</mo> </mover> </mrow> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mi>n</mi> </mtd> </mtr> <mtr> <mtd> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mover> <mi>q</mi> <mo stretchy="false">~</mo> </mover> </mrow> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mi>n</mi> </mtd> <mtd> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mover> <mi>p</mi> <mo stretchy="false">~</mo> </mover> </mrow> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mi>n</mi> </mtd> </mtr> </mtable> </mrow> <mo>)</mo> </mrow> <mo>,</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle P=\left({\begin{array}{cc}{\tilde {p}}/n&{\tilde {q}}/n\\{\tilde {q}}/n&{\tilde {p}}/n\end{array}}\right),}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/1192fd62b3abe33ddf7b411e254d60366bcb8630" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:20.242ex; height:6.176ex;" alt="{\displaystyle P=\left({\begin{array}{cc}{\tilde {p}}/n&{\tilde {q}}/n\\{\tilde {q}}/n&{\tilde {p}}/n\end{array}}\right),}"></span> partial recovery is feasible<sup id="cite_ref-mas13_4-1" class="reference"><a href="#cite_note-mas13-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup> with probability <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1-o(1)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mn>1</mn> <mo>−</mo> <mi>o</mi> <mo stretchy="false">(</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 1-o(1)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/58661cb7ecc1c0b8a99a821365f8c179fdaabbec" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.102ex; height:2.843ex;" alt="{\displaystyle 1-o(1)}"></span> whenever <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle ({\tilde {p}}-{\tilde {q}})^{2}>2({\tilde {p}}+{\tilde {q}})}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mover> <mi>p</mi> <mo stretchy="false">~</mo> </mover> </mrow> </mrow> <mo>−</mo> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mover> <mi>q</mi> <mo stretchy="false">~</mo> </mover> </mrow> </mrow> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo>></mo> <mn>2</mn> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mover> <mi>p</mi> <mo stretchy="false">~</mo> </mover> </mrow> </mrow> <mo>+</mo> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mover> <mi>q</mi> <mo stretchy="false">~</mo> </mover> </mrow> </mrow> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle ({\tilde {p}}-{\tilde {q}})^{2}>2({\tilde {p}}+{\tilde {q}})}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/0b1bcda4cb09552d1d7eed185ae5f83fcee9b5ff" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:20.088ex; height:3.176ex;" alt="{\displaystyle ({\tilde {p}}-{\tilde {q}})^{2}>2({\tilde {p}}+{\tilde {q}})}"></span>, whereas any <a href="/wiki/Estimator" title="Estimator">estimator</a> fails<sup id="cite_ref-mns12_3-2" class="reference"><a href="#cite_note-mns12-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> partial recovery with probability <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1-o(1)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mn>1</mn> <mo>−</mo> <mi>o</mi> <mo stretchy="false">(</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 1-o(1)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/58661cb7ecc1c0b8a99a821365f8c179fdaabbec" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.102ex; height:2.843ex;" alt="{\displaystyle 1-o(1)}"></span> whenever <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle ({\tilde {p}}-{\tilde {q}})^{2}<2({\tilde {p}}+{\tilde {q}})}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mover> <mi>p</mi> <mo stretchy="false">~</mo> </mover> </mrow> </mrow> <mo>−</mo> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mover> <mi>q</mi> <mo stretchy="false">~</mo> </mover> </mrow> </mrow> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo><</mo> <mn>2</mn> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mover> <mi>p</mi> <mo stretchy="false">~</mo> </mover> </mrow> </mrow> <mo>+</mo> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mover> <mi>q</mi> <mo stretchy="false">~</mo> </mover> </mrow> </mrow> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle ({\tilde {p}}-{\tilde {q}})^{2}<2({\tilde {p}}+{\tilde {q}})}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/45234998f69299f08a69ff50d712505bd2dabd0b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:20.088ex; height:3.176ex;" alt="{\displaystyle ({\tilde {p}}-{\tilde {q}})^{2}<2({\tilde {p}}+{\tilde {q}})}"></span>. </p><p>For exact recovery, the appropriate scaling is to take <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P_{ij}={\tilde {P}}_{ij}\log n/n}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>P</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> <mi>j</mi> </mrow> </msub> <mo>=</mo> <msub> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mover> <mi>P</mi> <mo stretchy="false">~</mo> </mover> </mrow> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> <mi>j</mi> </mrow> </msub> <mi>log</mi> <mo>⁡</mo> <mi>n</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle P_{ij}={\tilde {P}}_{ij}\log n/n}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d4659b51a3b14a4cee92dcbd3d3911d884194d17" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:17.055ex; height:3.343ex;" alt="{\displaystyle P_{ij}={\tilde {P}}_{ij}\log n/n}"></span>, resulting in graphs of logarithmic average degree. Here a similar threshold exists: for the assortative planted partition model with <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>r</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle r}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/0d1ecb613aa2984f0576f70f86650b7c2a132538" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.049ex; height:1.676ex;" alt="{\displaystyle r}"></span> equal-sized communities, the threshold lies at <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\sqrt {\tilde {p}}}-{\sqrt {\tilde {q}}}={\sqrt {r}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <msqrt> <mrow class="MJX-TeXAtom-ORD"> <mover> <mi>p</mi> <mo stretchy="false">~</mo> </mover> </mrow> </msqrt> </mrow> <mo>−</mo> <mrow class="MJX-TeXAtom-ORD"> <msqrt> <mrow class="MJX-TeXAtom-ORD"> <mover> <mi>q</mi> <mo stretchy="false">~</mo> </mover> </mrow> </msqrt> </mrow> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <msqrt> <mi>r</mi> </msqrt> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\sqrt {\tilde {p}}}-{\sqrt {\tilde {q}}}={\sqrt {r}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/66a5437aaaac2291f2cfd27b137ec64fa4722458" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:16.307ex; height:3.509ex;" alt="{\displaystyle {\sqrt {\tilde {p}}}-{\sqrt {\tilde {q}}}={\sqrt {r}}}"></span>. In fact, the exact recovery threshold is known for the fully general stochastic block model.<sup id="cite_ref-as15a_5-1" class="reference"><a href="#cite_note-as15a-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading2"><h2 id="Algorithms">Algorithms</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Stochastic_block_model&action=edit&section=8" title="Edit section: Algorithms"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>In principle, exact recovery can be solved in its feasible range using <a href="/wiki/Maximum_likelihood" class="mw-redirect" title="Maximum likelihood">maximum likelihood</a>, but this amounts to solving a constrained or <a href="/wiki/Regularization_(mathematics)" title="Regularization (mathematics)">regularized</a> cut problem such as minimum bisection that is typically <a href="/wiki/NP-complete" class="mw-redirect" title="NP-complete">NP-complete</a>. Hence, no known efficient algorithms will correctly compute the maximum-likelihood estimate in the worst case. </p><p>However, a wide variety of algorithms perform well in the average case, and many high-probability performance guarantees have been proven for algorithms in both the partial and exact recovery settings. Successful algorithms include <a href="/wiki/Spectral_clustering" title="Spectral clustering">spectral clustering</a> of the vertices,<sup id="cite_ref-krzakala-pnas_9-0" class="reference"><a href="#cite_note-krzakala-pnas-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-mas13_4-2" class="reference"><a href="#cite_note-mas13-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-as15a_5-2" class="reference"><a href="#cite_note-as15a-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-lr15_10-0" class="reference"><a href="#cite_note-lr15-10"><span class="cite-bracket">[</span>10<span class="cite-bracket">]</span></a></sup> <a href="/wiki/Semidefinite_programming" title="Semidefinite programming">semidefinite programming</a>,<sup id="cite_ref-al14_2-2" class="reference"><a href="#cite_note-al14-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-abh14_8-1" class="reference"><a href="#cite_note-abh14-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup> forms of <a href="/wiki/Belief_propagation" title="Belief propagation">belief propagation</a>,<sup id="cite_ref-decelle11_7-1" class="reference"><a href="#cite_note-decelle11-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-mns13_11-0" class="reference"><a href="#cite_note-mns13-11"><span class="cite-bracket">[</span>11<span class="cite-bracket">]</span></a></sup> and community detection<sup id="cite_ref-fat19_12-0" class="reference"><a href="#cite_note-fat19-12"><span class="cite-bracket">[</span>12<span class="cite-bracket">]</span></a></sup> among others. </p> <div class="mw-heading mw-heading2"><h2 id="Variants">Variants</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Stochastic_block_model&action=edit&section=9" title="Edit section: Variants"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Several variants of the model exist. One minor tweak allocates vertices to communities randomly, according to a <a href="/wiki/Categorical_distribution" title="Categorical distribution">categorical distribution</a>, rather than in a fixed partition.<sup id="cite_ref-as15a_5-3" class="reference"><a href="#cite_note-as15a-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> More significant variants include the degree-corrected stochastic block model,<sup id="cite_ref-ker_13-0" class="reference"><a href="#cite_note-ker-13"><span class="cite-bracket">[</span>13<span class="cite-bracket">]</span></a></sup> the hierarchical stochastic block model,<sup id="cite_ref-pei_14-0" class="reference"><a href="#cite_note-pei-14"><span class="cite-bracket">[</span>14<span class="cite-bracket">]</span></a></sup> the geometric block model,<sup id="cite_ref-gbm_15-0" class="reference"><a href="#cite_note-gbm-15"><span class="cite-bracket">[</span>15<span class="cite-bracket">]</span></a></sup> censored block model and the mixed-membership block model.<sup id="cite_ref-ar1_16-0" class="reference"><a href="#cite_note-ar1-16"><span class="cite-bracket">[</span>16<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading2"><h2 id="Topic_models">Topic models</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Stochastic_block_model&action=edit&section=10" title="Edit section: Topic models"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Stochastic block model have been recognised to be a <a href="/wiki/Topic_model" title="Topic model">topic model</a> on bipartite networks.<sup id="cite_ref-gerlachnetwork_17-0" class="reference"><a href="#cite_note-gerlachnetwork-17"><span class="cite-bracket">[</span>17<span class="cite-bracket">]</span></a></sup> In a network of documents and words, Stochastic block model can identify topics: group of words with a similar meaning. </p> <div class="mw-heading mw-heading2"><h2 id="Extensions_to_signed_graphs">Extensions to signed graphs</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Stochastic_block_model&action=edit&section=11" title="Edit section: Extensions to signed graphs"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Signed graphs allow for both favorable and adverse relationships and serve as a common model choice for various data analysis applications, e.g., correlation clustering. The stochastic block model can be trivially extended to signed graphs by assigning both positive and negative edge weights or equivalently using a difference of adjacency matrices of two stochastic block models. <sup id="cite_ref-18" class="reference"><a href="#cite_note-18"><span class="cite-bracket">[</span>18<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading2"><h2 id="DARPA/MIT/AWS_Graph_Challenge:_streaming_stochastic_block_partition"><span id="DARPA.2FMIT.2FAWS_Graph_Challenge:_streaming_stochastic_block_partition"></span>DARPA/MIT/AWS Graph Challenge: streaming stochastic block partition</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Stochastic_block_model&action=edit&section=12" title="Edit section: DARPA/MIT/AWS Graph Challenge: streaming stochastic block partition"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>GraphChallenge<sup id="cite_ref-19" class="reference"><a href="#cite_note-19"><span class="cite-bracket">[</span>19<span class="cite-bracket">]</span></a></sup> encourages community approaches to developing new solutions for analyzing graphs and sparse data derived from social media, sensor feeds, and scientific data to enable relationships between events to be discovered as they unfold in the field. Streaming stochastic block partition is one of the challenges since 2017. <sup id="cite_ref-20" class="reference"><a href="#cite_note-20"><span class="cite-bracket">[</span>20<span class="cite-bracket">]</span></a></sup> <a href="/wiki/Spectral_clustering" title="Spectral clustering">Spectral clustering</a> has demonstrated outstanding performance compared to the original and even improved<sup id="cite_ref-21" class="reference"><a href="#cite_note-21"><span class="cite-bracket">[</span>21<span class="cite-bracket">]</span></a></sup> base algorithm, matching its quality of clusters while being multiple orders of magnitude faster.<sup id="cite_ref-22" class="reference"><a href="#cite_note-22"><span class="cite-bracket">[</span>22<span class="cite-bracket">]</span></a></sup> <sup id="cite_ref-23" class="reference"><a href="#cite_note-23"><span class="cite-bracket">[</span>23<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading2"><h2 id="See_also">See also</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Stochastic_block_model&action=edit&section=13" title="Edit section: See also"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><a href="/wiki/Blockmodeling" title="Blockmodeling">blockmodeling</a></li> <li><a href="/wiki/Girvan%E2%80%93Newman_algorithm" title="Girvan–Newman algorithm">Girvan–Newman algorithm</a> – Community detection algorithm</li> <li><a href="/wiki/Lancichinetti%E2%80%93Fortunato%E2%80%93Radicchi_benchmark" title="Lancichinetti–Fortunato–Radicchi benchmark">Lancichinetti–Fortunato–Radicchi benchmark</a> – Algorithm<span style="display:none" class="category-spaceless-annotation">Pages displaying short descriptions with no spaces</span> for generating benchmark networks with communities</li></ul> <div class="mw-heading mw-heading2"><h2 id="References">References</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Stochastic_block_model&action=edit&section=14" title="Edit section: References"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <style data-mw-deduplicate="TemplateStyles:r1239543626">.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}</style><div class="reflist"> <div class="mw-references-wrap mw-references-columns"><ol class="references"> <li id="cite_note-hol-1"><span class="mw-cite-backlink"><b><a href="#cite_ref-hol_1-0">^</a></b></span> <span class="reference-text"><style data-mw-deduplicate="TemplateStyles:r1238218222">.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("//upload.wikimedia.org/wikipedia/commons/6/65/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("//upload.wikimedia.org/wikipedia/commons/d/d6/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("//upload.wikimedia.org/wikipedia/commons/a/aa/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("//upload.wikimedia.org/wikipedia/commons/4/4c/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}</style><cite id="CITEREFHollandLaskeyLeinhardt1983" class="citation journal cs1">Holland, Paul W; Laskey, Kathryn Blackmond; Leinhardt, Samuel (1983). <a rel="nofollow" class="external text" href="https://doi.org/10.1016/0378-8733(83)90021-7">"Stochastic blockmodels: First steps"</a>. <i><a href="/wiki/Social_Networks" class="mw-redirect" title="Social Networks">Social Networks</a></i>. <b>5</b> (2): 109–137. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0378-8733%2883%2990021-7">10.1016/0378-8733(83)90021-7</a>. <a href="/wiki/ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0378-8733">0378-8733</a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:34098453">34098453</a>. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20230204160405/https://www.sciencedirect.com/science/article/abs/pii/0378873383900217?via%3Dihub">Archived</a> from the original on 2023-02-04<span class="reference-accessdate">. Retrieved <span class="nowrap">2021-06-16</span></span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Social+Networks&rft.atitle=Stochastic+blockmodels%3A+First+steps&rft.volume=5&rft.issue=2&rft.pages=109-137&rft.date=1983&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A34098453%23id-name%3DS2CID&rft.issn=0378-8733&rft_id=info%3Adoi%2F10.1016%2F0378-8733%2883%2990021-7&rft.aulast=Holland&rft.aufirst=Paul+W&rft.au=Laskey%2C+Kathryn+Blackmond&rft.au=Leinhardt%2C+Samuel&rft_id=https%3A%2F%2Fdoi.org%2F10.1016%2F0378-8733%2883%2990021-7&rfr_id=info%3Asid%2Fen.wikipedia.org%3AStochastic+block+model" class="Z3988"></span></span> </li> <li id="cite_note-al14-2"><span class="mw-cite-backlink">^ <a href="#cite_ref-al14_2-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-al14_2-1"><sup><i><b>b</b></i></sup></a> <a href="#cite_ref-al14_2-2"><sup><i><b>c</b></i></sup></a></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFAminiLevina2014" class="citation arxiv cs1">Amini, Arash A.; <a href="/wiki/Elizaveta_Levina" title="Elizaveta Levina">Levina, Elizaveta</a> (June 2014). "On semidefinite relaxations for the block model". <a href="/wiki/ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/1406.5647">1406.5647</a></span> [<a rel="nofollow" class="external text" href="https://arxiv.org/archive/cs.LG">cs.LG</a>].</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=preprint&rft.jtitle=arXiv&rft.atitle=On+semidefinite+relaxations+for+the+block+model&rft.date=2014-06&rft_id=info%3Aarxiv%2F1406.5647&rft.aulast=Amini&rft.aufirst=Arash+A.&rft.au=Levina%2C+Elizaveta&rfr_id=info%3Asid%2Fen.wikipedia.org%3AStochastic+block+model" class="Z3988"></span></span> </li> <li id="cite_note-mns12-3"><span class="mw-cite-backlink">^ <a href="#cite_ref-mns12_3-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-mns12_3-1"><sup><i><b>b</b></i></sup></a> <a href="#cite_ref-mns12_3-2"><sup><i><b>c</b></i></sup></a></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFMosselNeemanSly2012" class="citation arxiv cs1">Mossel, Elchanan; Neeman, Joe; Sly, Allan (February 2012). "Stochastic Block Models and Reconstruction". <a href="/wiki/ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/1202.1499">1202.1499</a></span> [<a rel="nofollow" class="external text" href="https://arxiv.org/archive/math.PR">math.PR</a>].</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=preprint&rft.jtitle=arXiv&rft.atitle=Stochastic+Block+Models+and+Reconstruction&rft.date=2012-02&rft_id=info%3Aarxiv%2F1202.1499&rft.aulast=Mossel&rft.aufirst=Elchanan&rft.au=Neeman%2C+Joe&rft.au=Sly%2C+Allan&rfr_id=info%3Asid%2Fen.wikipedia.org%3AStochastic+block+model" class="Z3988"></span></span> </li> <li id="cite_note-mas13-4"><span class="mw-cite-backlink">^ <a href="#cite_ref-mas13_4-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-mas13_4-1"><sup><i><b>b</b></i></sup></a> <a href="#cite_ref-mas13_4-2"><sup><i><b>c</b></i></sup></a></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFMassoulie2013" class="citation arxiv cs1">Massoulie, Laurent (November 2013). "Community detection thresholds and the weak Ramanujan property". <a href="/wiki/ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/1311.3085">1311.3085</a></span> [<a rel="nofollow" class="external text" href="https://arxiv.org/archive/cs.SI">cs.SI</a>].</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=preprint&rft.jtitle=arXiv&rft.atitle=Community+detection+thresholds+and+the+weak+Ramanujan+property&rft.date=2013-11&rft_id=info%3Aarxiv%2F1311.3085&rft.aulast=Massoulie&rft.aufirst=Laurent&rfr_id=info%3Asid%2Fen.wikipedia.org%3AStochastic+block+model" class="Z3988"></span></span> </li> <li id="cite_note-as15a-5"><span class="mw-cite-backlink">^ <a href="#cite_ref-as15a_5-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-as15a_5-1"><sup><i><b>b</b></i></sup></a> <a href="#cite_ref-as15a_5-2"><sup><i><b>c</b></i></sup></a> <a href="#cite_ref-as15a_5-3"><sup><i><b>d</b></i></sup></a></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFAbbeSandon2015" class="citation arxiv cs1">Abbe, Emmanuel; Sandon, Colin (March 2015). "Community detection in general stochastic block models: fundamental limits and efficient recovery algorithms". <a href="/wiki/ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/1503.00609">1503.00609</a></span> [<a rel="nofollow" class="external text" href="https://arxiv.org/archive/math.PR">math.PR</a>].</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=preprint&rft.jtitle=arXiv&rft.atitle=Community+detection+in+general+stochastic+block+models%3A+fundamental+limits+and+efficient+recovery+algorithms&rft.date=2015-03&rft_id=info%3Aarxiv%2F1503.00609&rft.aulast=Abbe&rft.aufirst=Emmanuel&rft.au=Sandon%2C+Colin&rfr_id=info%3Asid%2Fen.wikipedia.org%3AStochastic+block+model" class="Z3988"></span></span> </li> <li id="cite_note-as15b-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-as15b_6-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFAbbeSandon2015" class="citation arxiv cs1">Abbe, Emmanuel; Sandon, Colin (June 2015). "Recovering communities in the general stochastic block model without knowing the parameters". <a href="/wiki/ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/1506.03729">1506.03729</a></span> [<a rel="nofollow" class="external text" href="https://arxiv.org/archive/math.PR">math.PR</a>].</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=preprint&rft.jtitle=arXiv&rft.atitle=Recovering+communities+in+the+general+stochastic+block+model+without+knowing+the+parameters&rft.date=2015-06&rft_id=info%3Aarxiv%2F1506.03729&rft.aulast=Abbe&rft.aufirst=Emmanuel&rft.au=Sandon%2C+Colin&rfr_id=info%3Asid%2Fen.wikipedia.org%3AStochastic+block+model" class="Z3988"></span></span> </li> <li id="cite_note-decelle11-7"><span class="mw-cite-backlink">^ <a href="#cite_ref-decelle11_7-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-decelle11_7-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFDecelleKrzakalaMooreZdeborová2011" class="citation journal cs1">Decelle, Aurelien; Krzakala, Florent; Moore, Cristopher; <a href="/wiki/Lenka_Zdeborov%C3%A1" title="Lenka Zdeborová">Zdeborová, Lenka</a> (September 2011). "Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications". <i>Physical Review E</i>. <b>84</b> (6): 066106. <a href="/wiki/ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/1109.3041">1109.3041</a></span>. <a href="/wiki/Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2011PhRvE..84f6106D">2011PhRvE..84f6106D</a>. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1103%2FPhysRevE.84.066106">10.1103/PhysRevE.84.066106</a>. <a href="/wiki/PMID_(identifier)" class="mw-redirect" title="PMID (identifier)">PMID</a> <a rel="nofollow" class="external text" href="https://pubmed.ncbi.nlm.nih.gov/22304154">22304154</a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:15788070">15788070</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Physical+Review+E&rft.atitle=Asymptotic+analysis+of+the+stochastic+block+model+for+modular+networks+and+its+algorithmic+applications&rft.volume=84&rft.issue=6&rft.pages=066106&rft.date=2011-09&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A15788070%23id-name%3DS2CID&rft_id=info%3Abibcode%2F2011PhRvE..84f6106D&rft_id=info%3Aarxiv%2F1109.3041&rft_id=info%3Apmid%2F22304154&rft_id=info%3Adoi%2F10.1103%2FPhysRevE.84.066106&rft.aulast=Decelle&rft.aufirst=Aurelien&rft.au=Krzakala%2C+Florent&rft.au=Moore%2C+Cristopher&rft.au=Zdeborov%C3%A1%2C+Lenka&rfr_id=info%3Asid%2Fen.wikipedia.org%3AStochastic+block+model" class="Z3988"></span></span> </li> <li id="cite_note-abh14-8"><span class="mw-cite-backlink">^ <a href="#cite_ref-abh14_8-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-abh14_8-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFAbbeBandeiraHall2014" class="citation arxiv cs1">Abbe, Emmanuel; Bandeira, Afonso S.; Hall, Georgina (May 2014). "Exact Recovery in the Stochastic Block Model". <a href="/wiki/ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/1405.3267">1405.3267</a></span> [<a rel="nofollow" class="external text" href="https://arxiv.org/archive/cs.SI">cs.SI</a>].</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=preprint&rft.jtitle=arXiv&rft.atitle=Exact+Recovery+in+the+Stochastic+Block+Model&rft.date=2014-05&rft_id=info%3Aarxiv%2F1405.3267&rft.aulast=Abbe&rft.aufirst=Emmanuel&rft.au=Bandeira%2C+Afonso+S.&rft.au=Hall%2C+Georgina&rfr_id=info%3Asid%2Fen.wikipedia.org%3AStochastic+block+model" class="Z3988"></span></span> </li> <li id="cite_note-krzakala-pnas-9"><span class="mw-cite-backlink"><b><a href="#cite_ref-krzakala-pnas_9-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFKrzakalaMooreMosselNeeman2013" class="citation journal cs1">Krzakala, Florent; Moore, Cristopher; Mossel, Elchanan; Neeman, Joe; Sly, Allan; Lenka, Lenka; Zhang, Pan (October 2013). <a rel="nofollow" class="external text" href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3876200">"Spectral redemption in clustering sparse networks"</a>. <i>Proceedings of the National Academy of Sciences</i>. <b>110</b> (52): 20935–20940. <a href="/wiki/ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/1306.5550">1306.5550</a></span>. <a href="/wiki/Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2013PNAS..11020935K">2013PNAS..11020935K</a>. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1073%2Fpnas.1312486110">10.1073/pnas.1312486110</a></span>. <a href="/wiki/PMC_(identifier)" class="mw-redirect" title="PMC (identifier)">PMC</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3876200">3876200</a></span>. <a href="/wiki/PMID_(identifier)" class="mw-redirect" title="PMID (identifier)">PMID</a> <a rel="nofollow" class="external text" href="https://pubmed.ncbi.nlm.nih.gov/24277835">24277835</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Proceedings+of+the+National+Academy+of+Sciences&rft.atitle=Spectral+redemption+in+clustering+sparse+networks&rft.volume=110&rft.issue=52&rft.pages=20935-20940&rft.date=2013-10&rft_id=https%3A%2F%2Fwww.ncbi.nlm.nih.gov%2Fpmc%2Farticles%2FPMC3876200%23id-name%3DPMC&rft_id=info%3Abibcode%2F2013PNAS..11020935K&rft_id=info%3Aarxiv%2F1306.5550&rft_id=info%3Apmid%2F24277835&rft_id=info%3Adoi%2F10.1073%2Fpnas.1312486110&rft.aulast=Krzakala&rft.aufirst=Florent&rft.au=Moore%2C+Cristopher&rft.au=Mossel%2C+Elchanan&rft.au=Neeman%2C+Joe&rft.au=Sly%2C+Allan&rft.au=Lenka%2C+Lenka&rft.au=Zhang%2C+Pan&rft_id=https%3A%2F%2Fwww.ncbi.nlm.nih.gov%2Fpmc%2Farticles%2FPMC3876200&rfr_id=info%3Asid%2Fen.wikipedia.org%3AStochastic+block+model" class="Z3988"></span></span> </li> <li id="cite_note-lr15-10"><span class="mw-cite-backlink"><b><a href="#cite_ref-lr15_10-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFLeiRinaldo2015" class="citation journal cs1">Lei, Jing; Rinaldo, Alessandro (February 2015). "Consistency of spectral clustering in stochastic block models". <i>The Annals of Statistics</i>. <b>43</b> (1): 215–237. <a href="/wiki/ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/1312.2050">1312.2050</a></span>. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1214%2F14-AOS1274">10.1214/14-AOS1274</a>. <a href="/wiki/ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0090-5364">0090-5364</a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:88519551">88519551</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=The+Annals+of+Statistics&rft.atitle=Consistency+of+spectral+clustering+in+stochastic+block+models&rft.volume=43&rft.issue=1&rft.pages=215-237&rft.date=2015-02&rft_id=info%3Aarxiv%2F1312.2050&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A88519551%23id-name%3DS2CID&rft.issn=0090-5364&rft_id=info%3Adoi%2F10.1214%2F14-AOS1274&rft.aulast=Lei&rft.aufirst=Jing&rft.au=Rinaldo%2C+Alessandro&rfr_id=info%3Asid%2Fen.wikipedia.org%3AStochastic+block+model" class="Z3988"></span></span> </li> <li id="cite_note-mns13-11"><span class="mw-cite-backlink"><b><a href="#cite_ref-mns13_11-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFMosselNeemanSly2013" class="citation journal cs1">Mossel, Elchanan; Neeman, Joe; Sly, Allan (September 2013). "Belief Propagation, Robust Reconstruction, and Optimal Recovery of Block Models". <i>The Annals of Applied Probability</i>. <b>26</b> (4): 2211–2256. <a href="/wiki/ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/1309.1380">1309.1380</a></span>. <a href="/wiki/Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2013arXiv1309.1380M">2013arXiv1309.1380M</a>. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1214%2F15-AAP1145">10.1214/15-AAP1145</a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:184446">184446</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=The+Annals+of+Applied+Probability&rft.atitle=Belief+Propagation%2C+Robust+Reconstruction%2C+and+Optimal+Recovery+of+Block+Models&rft.volume=26&rft.issue=4&rft.pages=2211-2256&rft.date=2013-09&rft_id=info%3Aarxiv%2F1309.1380&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A184446%23id-name%3DS2CID&rft_id=info%3Adoi%2F10.1214%2F15-AAP1145&rft_id=info%3Abibcode%2F2013arXiv1309.1380M&rft.aulast=Mossel&rft.aufirst=Elchanan&rft.au=Neeman%2C+Joe&rft.au=Sly%2C+Allan&rfr_id=info%3Asid%2Fen.wikipedia.org%3AStochastic+block+model" class="Z3988"></span></span> </li> <li id="cite_note-fat19-12"><span class="mw-cite-backlink"><b><a href="#cite_ref-fat19_12-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFFathi2019" class="citation arxiv cs1">Fathi, Reza (April 2019). "Efficient Distributed Community Detection in the Stochastic Block Model". <a href="/wiki/ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/1904.07494">1904.07494</a></span> [<a rel="nofollow" class="external text" href="https://arxiv.org/archive/cs.DC">cs.DC</a>].</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=preprint&rft.jtitle=arXiv&rft.atitle=Efficient+Distributed+Community+Detection+in+the+Stochastic+Block+Model&rft.date=2019-04&rft_id=info%3Aarxiv%2F1904.07494&rft.aulast=Fathi&rft.aufirst=Reza&rfr_id=info%3Asid%2Fen.wikipedia.org%3AStochastic+block+model" class="Z3988"></span></span> </li> <li id="cite_note-ker-13"><span class="mw-cite-backlink"><b><a href="#cite_ref-ker_13-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFKarrerNewman2011" class="citation journal cs1">Karrer, Brian; Newman, Mark E J (2011). <a rel="nofollow" class="external text" href="https://link.aps.org/doi/10.1103/PhysRevE.83.016107">"Stochastic blockmodels and community structure in networks"</a>. <i>Physical Review E</i>. <b>83</b> (1): 016107. <a href="/wiki/ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/1008.3926">1008.3926</a></span>. <a href="/wiki/Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2011PhRvE..83a6107K">2011PhRvE..83a6107K</a>. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1103%2FPhysRevE.83.016107">10.1103/PhysRevE.83.016107</a>. <a href="/wiki/PMID_(identifier)" class="mw-redirect" title="PMID (identifier)">PMID</a> <a rel="nofollow" class="external text" href="https://pubmed.ncbi.nlm.nih.gov/21405744">21405744</a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:9068097">9068097</a>. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20230204160406/https://journals.aps.org/pre/abstract/10.1103/PhysRevE.83.016107">Archived</a> from the original on 2023-02-04<span class="reference-accessdate">. Retrieved <span class="nowrap">2021-06-16</span></span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Physical+Review+E&rft.atitle=Stochastic+blockmodels+and+community+structure+in+networks&rft.volume=83&rft.issue=1&rft.pages=016107&rft.date=2011&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A9068097%23id-name%3DS2CID&rft_id=info%3Abibcode%2F2011PhRvE..83a6107K&rft_id=info%3Aarxiv%2F1008.3926&rft_id=info%3Apmid%2F21405744&rft_id=info%3Adoi%2F10.1103%2FPhysRevE.83.016107&rft.aulast=Karrer&rft.aufirst=Brian&rft.au=Newman%2C+Mark+E+J&rft_id=https%3A%2F%2Flink.aps.org%2Fdoi%2F10.1103%2FPhysRevE.83.016107&rfr_id=info%3Asid%2Fen.wikipedia.org%3AStochastic+block+model" class="Z3988"></span></span> </li> <li id="cite_note-pei-14"><span class="mw-cite-backlink"><b><a href="#cite_ref-pei_14-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFPeixoto2014" class="citation journal cs1">Peixoto, Tiago (2014). <a rel="nofollow" class="external text" href="https://journals.aps.org/prx/abstract/10.1103/PhysRevX.4.011047">"Hierarchical block structures and high-resolution model selection in large networks"</a>. <i>Physical Review X</i>. <b>4</b> (1): 011047. <a href="/wiki/ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/1310.4377">1310.4377</a></span>. <a href="/wiki/Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2014PhRvX...4a1047P">2014PhRvX...4a1047P</a>. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1103%2FPhysRevX.4.011047">10.1103/PhysRevX.4.011047</a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:5841379">5841379</a>. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20210624195430/https://journals.aps.org/prx/abstract/10.1103/PhysRevX.4.011047">Archived</a> from the original on 2021-06-24<span class="reference-accessdate">. Retrieved <span class="nowrap">2021-06-16</span></span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Physical+Review+X&rft.atitle=Hierarchical+block+structures+and+high-resolution+model+selection+in+large+networks&rft.volume=4&rft.issue=1&rft.pages=011047&rft.date=2014&rft_id=info%3Aarxiv%2F1310.4377&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A5841379%23id-name%3DS2CID&rft_id=info%3Adoi%2F10.1103%2FPhysRevX.4.011047&rft_id=info%3Abibcode%2F2014PhRvX...4a1047P&rft.aulast=Peixoto&rft.aufirst=Tiago&rft_id=https%3A%2F%2Fjournals.aps.org%2Fprx%2Fabstract%2F10.1103%2FPhysRevX.4.011047&rfr_id=info%3Asid%2Fen.wikipedia.org%3AStochastic+block+model" class="Z3988"></span></span> </li> <li id="cite_note-gbm-15"><span class="mw-cite-backlink"><b><a href="#cite_ref-gbm_15-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFGalhotraMazumdarPalSaha2018" class="citation journal cs1">Galhotra, Sainyam; Mazumdar, Arya; Pal, Soumyabrata; <a href="/wiki/Barna_Saha" title="Barna Saha">Saha, Barna</a> (February 2018). "The Geometric Block Model". <i>AAAI</i>. <b>32</b>. <a href="/wiki/ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/1709.05510">1709.05510</a></span>. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1609%2Faaai.v32i1.11905">10.1609/aaai.v32i1.11905</a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:19152144">19152144</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=AAAI&rft.atitle=The+Geometric+Block+Model&rft.volume=32&rft.date=2018-02&rft_id=info%3Aarxiv%2F1709.05510&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A19152144%23id-name%3DS2CID&rft_id=info%3Adoi%2F10.1609%2Faaai.v32i1.11905&rft.aulast=Galhotra&rft.aufirst=Sainyam&rft.au=Mazumdar%2C+Arya&rft.au=Pal%2C+Soumyabrata&rft.au=Saha%2C+Barna&rfr_id=info%3Asid%2Fen.wikipedia.org%3AStochastic+block+model" class="Z3988"></span></span> </li> <li id="cite_note-ar1-16"><span class="mw-cite-backlink"><b><a href="#cite_ref-ar1_16-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFAiroldiBleiFeinbergXing2007" class="citation journal cs1"><a href="/wiki/Edoardo_Airoldi" title="Edoardo Airoldi">Airoldi, Edoardo</a>; Blei, David; Feinberg, Stephen; Xing, Eric (May 2007). <a rel="nofollow" class="external text" href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3119541">"Mixed membership stochastic blockmodels"</a>. <i>Journal of Machine Learning Research</i>. <b>9</b>: 1981–2014. <a href="/wiki/ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/0705.4485">0705.4485</a></span>. <a href="/wiki/Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2007arXiv0705.4485A">2007arXiv0705.4485A</a>. <a href="/wiki/PMC_(identifier)" class="mw-redirect" title="PMC (identifier)">PMC</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3119541">3119541</a></span>. <a href="/wiki/PMID_(identifier)" class="mw-redirect" title="PMID (identifier)">PMID</a> <a rel="nofollow" class="external text" href="https://pubmed.ncbi.nlm.nih.gov/21701698">21701698</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Journal+of+Machine+Learning+Research&rft.atitle=Mixed+membership+stochastic+blockmodels&rft.volume=9&rft.pages=1981-2014&rft.date=2007-05&rft_id=info%3Aarxiv%2F0705.4485&rft_id=info%3Apmid%2F21701698&rft_id=https%3A%2F%2Fwww.ncbi.nlm.nih.gov%2Fpmc%2Farticles%2FPMC3119541%23id-name%3DPMC&rft_id=info%3Abibcode%2F2007arXiv0705.4485A&rft.aulast=Airoldi&rft.aufirst=Edoardo&rft.au=Blei%2C+David&rft.au=Feinberg%2C+Stephen&rft.au=Xing%2C+Eric&rft_id=https%3A%2F%2Fwww.ncbi.nlm.nih.gov%2Fpmc%2Farticles%2FPMC3119541&rfr_id=info%3Asid%2Fen.wikipedia.org%3AStochastic+block+model" class="Z3988"></span></span> </li> <li id="cite_note-gerlachnetwork-17"><span class="mw-cite-backlink"><b><a href="#cite_ref-gerlachnetwork_17-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFMartin_GerlachTiago_PeixotoEduardo_Altmann2018" class="citation journal cs1">Martin Gerlach; Tiago Peixoto; Eduardo Altmann (2018). <a rel="nofollow" class="external text" href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC6051742">"A network approach to topic models"</a>. <i>Science Advances</i>. <b>4</b> (7): eaaq1360. <a href="/wiki/ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/1708.01677">1708.01677</a></span>. <a href="/wiki/Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2018SciA....4.1360G">2018SciA....4.1360G</a>. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1126%2Fsciadv.aaq1360">10.1126/sciadv.aaq1360</a>. <a href="/wiki/PMC_(identifier)" class="mw-redirect" title="PMC (identifier)">PMC</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC6051742">6051742</a></span>. <a href="/wiki/PMID_(identifier)" class="mw-redirect" title="PMID (identifier)">PMID</a> <a rel="nofollow" class="external text" href="https://pubmed.ncbi.nlm.nih.gov/30035215">30035215</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Science+Advances&rft.atitle=A+network+approach+to+topic+models&rft.volume=4&rft.issue=7&rft.pages=eaaq1360&rft.date=2018&rft_id=https%3A%2F%2Fwww.ncbi.nlm.nih.gov%2Fpmc%2Farticles%2FPMC6051742%23id-name%3DPMC&rft_id=info%3Abibcode%2F2018SciA....4.1360G&rft_id=info%3Aarxiv%2F1708.01677&rft_id=info%3Apmid%2F30035215&rft_id=info%3Adoi%2F10.1126%2Fsciadv.aaq1360&rft.au=Martin+Gerlach&rft.au=Tiago+Peixoto&rft.au=Eduardo+Altmann&rft_id=https%3A%2F%2Fwww.ncbi.nlm.nih.gov%2Fpmc%2Farticles%2FPMC6051742&rfr_id=info%3Asid%2Fen.wikipedia.org%3AStochastic+block+model" class="Z3988"></span></span> </li> <li id="cite_note-18"><span class="mw-cite-backlink"><b><a href="#cite_ref-18">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFAlyson_FoxGeoffrey_SandersAndrew_Knyazev2018" class="citation book cs1">Alyson Fox; Geoffrey Sanders; Andrew Knyazev (2018). "Investigation of Spectral Clustering for Signed Graph Matrix Representations". <i>2018 IEEE High Performance extreme Computing Conference (HPEC)</i>. pp. 1–7. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FHPEC.2018.8547575">10.1109/HPEC.2018.8547575</a>. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-1-5386-5989-2" title="Special:BookSources/978-1-5386-5989-2"><bdi>978-1-5386-5989-2</bdi></a>. <a href="/wiki/OSTI_(identifier)" class="mw-redirect" title="OSTI (identifier)">OSTI</a> <a rel="nofollow" class="external text" href="https://www.osti.gov/biblio/1476177">1476177</a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:54443034">54443034</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=Investigation+of+Spectral+Clustering+for+Signed+Graph+Matrix+Representations&rft.btitle=2018+IEEE+High+Performance+extreme+Computing+Conference+%28HPEC%29&rft.pages=1-7&rft.date=2018&rft_id=info%3Adoi%2F10.1109%2FHPEC.2018.8547575&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A54443034%23id-name%3DS2CID&rft_id=https%3A%2F%2Fwww.osti.gov%2Fbiblio%2F1476177%23id-name%3DOSTI&rft.isbn=978-1-5386-5989-2&rft.au=Alyson+Fox&rft.au=Geoffrey+Sanders&rft.au=Andrew+Knyazev&rfr_id=info%3Asid%2Fen.wikipedia.org%3AStochastic+block+model" class="Z3988"></span></span> </li> <li id="cite_note-19"><span class="mw-cite-backlink"><b><a href="#cite_ref-19">^</a></b></span> <span class="reference-text"><a rel="nofollow" class="external autonumber" href="http://graphchallenge.mit.edu">[1]</a> <a rel="nofollow" class="external text" href="https://web.archive.org/web/20230204160402/http://graphchallenge.mit.edu/">Archived</a> 2023-02-04 at the <a href="/wiki/Wayback_Machine" title="Wayback Machine">Wayback Machine</a> DARPA/MIT/AWS Graph Challenge</span> </li> <li id="cite_note-20"><span class="mw-cite-backlink"><b><a href="#cite_ref-20">^</a></b></span> <span class="reference-text"><a rel="nofollow" class="external autonumber" href="http://graphchallenge.mit.edu/champions">[2]</a> <a rel="nofollow" class="external text" href="https://web.archive.org/web/20230204160403/http://graphchallenge.mit.edu/champions">Archived</a> 2023-02-04 at the <a href="/wiki/Wayback_Machine" title="Wayback Machine">Wayback Machine</a> DARPA/MIT/AWS Graph Challenge Champions</span> </li> <li id="cite_note-21"><span class="mw-cite-backlink"><b><a href="#cite_ref-21">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFA._J._UppalJ._ChoiT._B._RolingerH._Howie_Huang2021" class="citation book cs1">A. J. Uppal; J. Choi; T. B. Rolinger; H. Howie Huang (2021). "Faster Stochastic Block Partition Using Aggressive Initial Merging, Compressed Representation, and Parallelism Control". <i>2021 IEEE High Performance Extreme Computing Conference (HPEC)</i>. pp. 1–7. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FHPEC49654.2021.9622836">10.1109/HPEC49654.2021.9622836</a>. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-1-6654-2369-4" title="Special:BookSources/978-1-6654-2369-4"><bdi>978-1-6654-2369-4</bdi></a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:244780210">244780210</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=Faster+Stochastic+Block+Partition+Using+Aggressive+Initial+Merging%2C+Compressed+Representation%2C+and+Parallelism+Control&rft.btitle=2021+IEEE+High+Performance+Extreme+Computing+Conference+%28HPEC%29&rft.pages=1-7&rft.date=2021&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A244780210%23id-name%3DS2CID&rft_id=info%3Adoi%2F10.1109%2FHPEC49654.2021.9622836&rft.isbn=978-1-6654-2369-4&rft.au=A.+J.+Uppal&rft.au=J.+Choi&rft.au=T.+B.+Rolinger&rft.au=H.+Howie+Huang&rfr_id=info%3Asid%2Fen.wikipedia.org%3AStochastic+block+model" class="Z3988"></span></span> </li> <li id="cite_note-22"><span class="mw-cite-backlink"><b><a href="#cite_ref-22">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFDavid_ZhuzhunashviliAndrew_Knyazev2017" class="citation book cs1">David Zhuzhunashvili; Andrew Knyazev (2017). "Preconditioned spectral clustering for stochastic block partition streaming graph challenge (Preliminary version at arXiv.)". <i>2017 IEEE High Performance Extreme Computing Conference (HPEC)</i>. pp. 1–6. <a href="/wiki/ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/1708.07481">1708.07481</a></span>. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FHPEC.2017.8091045">10.1109/HPEC.2017.8091045</a>. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-1-5386-3472-1" title="Special:BookSources/978-1-5386-3472-1"><bdi>978-1-5386-3472-1</bdi></a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:19781504">19781504</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=Preconditioned+spectral+clustering+for+stochastic+block+partition+streaming+graph+challenge+%28Preliminary+version+at+arXiv.%29&rft.btitle=2017+IEEE+High+Performance+Extreme+Computing+Conference+%28HPEC%29&rft.pages=1-6&rft.date=2017&rft_id=info%3Aarxiv%2F1708.07481&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A19781504%23id-name%3DS2CID&rft_id=info%3Adoi%2F10.1109%2FHPEC.2017.8091045&rft.isbn=978-1-5386-3472-1&rft.au=David+Zhuzhunashvili&rft.au=Andrew+Knyazev&rfr_id=info%3Asid%2Fen.wikipedia.org%3AStochastic+block+model" class="Z3988"></span></span> </li> <li id="cite_note-23"><span class="mw-cite-backlink"><b><a href="#cite_ref-23">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFLisa_DurbeckPeter_Athanas2020" class="citation book cs1">Lisa Durbeck; Peter Athanas (2020). "Incremental Streaming Graph Partitioning". <i>2020 IEEE High Performance Extreme Computing Conference (HPEC)</i>. pp. 1–8. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FHPEC43674.2020.9286181">10.1109/HPEC43674.2020.9286181</a>. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-1-7281-9219-2" title="Special:BookSources/978-1-7281-9219-2"><bdi>978-1-7281-9219-2</bdi></a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:229376193">229376193</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=Incremental+Streaming+Graph+Partitioning&rft.btitle=2020+IEEE+High+Performance+Extreme+Computing+Conference+%28HPEC%29&rft.pages=1-8&rft.date=2020&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A229376193%23id-name%3DS2CID&rft_id=info%3Adoi%2F10.1109%2FHPEC43674.2020.9286181&rft.isbn=978-1-7281-9219-2&rft.au=Lisa+Durbeck&rft.au=Peter+Athanas&rfr_id=info%3Asid%2Fen.wikipedia.org%3AStochastic+block+model" class="Z3988"></span></span> </li> </ol></div></div>    </div><noscript><img src="https://login.wikimedia.org/wiki/Special:CentralAutoLogin/start?useformat=desktop&type=1x1&usesul3=0" alt="" width="1" height="1" style="border: none; position: absolute;"></noscript> <div class="printfooter" data-nosnippet="">Retrieved from "<a dir="ltr" href="https://en.wikipedia.org/w/index.php?title=Stochastic_block_model&oldid=1230624135">https://en.wikipedia.org/w/index.php?title=Stochastic_block_model&oldid=1230624135</a>"</div></div> <div id="catlinks" class="catlinks" data-mw="interface"><div id="mw-normal-catlinks" class="mw-normal-catlinks"><a href="/wiki/Help:Category" title="Help:Category">Categories</a>: <ul><li><a href="/wiki/Category:Random_graphs" title="Category:Random graphs">Random graphs</a></li><li><a href="/wiki/Category:Networks" title="Category:Networks">Networks</a></li><li><a href="/wiki/Category:Blockmodeling" title="Category:Blockmodeling">Blockmodeling</a></li></ul></div><div id="mw-hidden-catlinks" class="mw-hidden-catlinks mw-hidden-cats-hidden">Hidden categories: <ul><li><a href="/wiki/Category:Webarchive_template_wayback_links" title="Category:Webarchive template wayback links">Webarchive template wayback links</a></li><li><a href="/wiki/Category:Pages_displaying_short_descriptions_with_no_spaces_via_Module:Annotated_link" title="Category:Pages displaying short descriptions with no spaces via Module:Annotated link">Pages displaying short descriptions with no spaces via Module:Annotated link</a></li></ul></div></div> </div> </main> </div> <div class="mw-footer-container"> <footer id="footer" class="mw-footer" > <ul id="footer-info"> <li id="footer-info-lastmod"> This page was last edited on 23 June 2024, at 19:38<span class="anonymous-show"> (UTC)</span>.</li> <li id="footer-info-copyright">Text is available under the <a href="/wiki/Wikipedia:Text_of_the_Creative_Commons_Attribution-ShareAlike_4.0_International_License" title="Wikipedia:Text of the Creative Commons Attribution-ShareAlike 4.0 International License">Creative Commons Attribution-ShareAlike 4.0 License</a>; additional terms may apply. By using this site, you agree to the <a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Terms_of_Use" class="extiw" title="foundation:Special:MyLanguage/Policy:Terms of Use">Terms of Use</a> and <a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy" class="extiw" title="foundation:Special:MyLanguage/Policy:Privacy policy">Privacy Policy</a>. Wikipedia® is a registered trademark of the <a rel="nofollow" class="external text" href="https://wikimediafoundation.org/">Wikimedia Foundation, Inc.</a>, a non-profit organization.</li> </ul> <ul id="footer-places"> <li id="footer-places-privacy"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy">Privacy policy</a></li> <li id="footer-places-about"><a href="/wiki/Wikipedia:About">About Wikipedia</a></li> <li id="footer-places-disclaimers"><a href="/wiki/Wikipedia:General_disclaimer">Disclaimers</a></li> <li id="footer-places-contact"><a href="//en.wikipedia.org/wiki/Wikipedia:Contact_us">Contact Wikipedia</a></li> <li id="footer-places-wm-codeofconduct"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Universal_Code_of_Conduct">Code of Conduct</a></li> <li id="footer-places-developers"><a href="https://developer.wikimedia.org">Developers</a></li> <li id="footer-places-statslink"><a href="https://stats.wikimedia.org/#/en.wikipedia.org">Statistics</a></li> <li id="footer-places-cookiestatement"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Cookie_statement">Cookie statement</a></li> <li id="footer-places-mobileview"><a href="//en.m.wikipedia.org/w/index.php?title=Stochastic_block_model&mobileaction=toggle_view_mobile" class="noprint stopMobileRedirectToggle">Mobile view</a></li> </ul> <ul id="footer-icons" class="noprint"> <li id="footer-copyrightico"><a href="https://wikimediafoundation.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><img src="/static/images/footer/wikimedia-button.svg" width="84" height="29" alt="Wikimedia Foundation" loading="lazy"></a></li> <li id="footer-poweredbyico"><a href="https://www.mediawiki.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><img src="/w/resources/assets/poweredby_mediawiki.svg" alt="Powered by MediaWiki" width="88" height="31" loading="lazy"></a></li> </ul> </footer> </div> </div> </div> <div class="vector-settings" id="p-dock-bottom"> <ul></ul> </div><script>(RLQ=window.RLQ||[]).push(function(){mw.config.set({"wgHostname":"mw-web.codfw.canary-7698d988c8-4srfn","wgBackendResponseTime":176,"wgPageParseReport":{"limitreport":{"cputime":"0.596","walltime":"0.813","ppvisitednodes":{"value":2379,"limit":1000000},"postexpandincludesize":{"value":89204,"limit":2097152},"templateargumentsize":{"value":1545,"limit":2097152},"expansiondepth":{"value":13,"limit":100},"expensivefunctioncount":{"value":1,"limit":500},"unstrip-depth":{"value":1,"limit":20},"unstrip-size":{"value":113471,"limit":5000000},"entityaccesscount":{"value":0,"limit":400},"timingprofile":["100.00% 575.323 1 -total"," 49.53% 284.931 1 Template:Reflist"," 30.55% 175.764 3 Template:Sidebar"," 26.89% 154.694 10 Template:Cite_journal"," 24.22% 139.346 1 Template:Network_science"," 22.91% 131.803 2 Template:Annotated_link"," 7.36% 42.368 3 Template:Hlist"," 6.95% 39.969 7 Template:Cite_arXiv"," 4.44% 25.567 4 Template:Cite_book"," 1.81% 10.418 2 Template:Webarchive"]},"scribunto":{"limitreport-timeusage":{"value":"0.381","limit":"10.000"},"limitreport-memusage":{"value":13145615,"limit":52428800}},"cachereport":{"origin":"mw-web.codfw.main-59b954b7fb-rdv8w","timestamp":"20241207170133","ttl":2592000,"transientcontent":false}}});});</script> <script type="application/ld+json">{"@context":"https:\/\/schema.org","@type":"Article","name":"Stochastic block model","url":"https:\/\/en.wikipedia.org\/wiki\/Stochastic_block_model","sameAs":"http:\/\/www.wikidata.org\/entity\/Q25053762","mainEntity":"http:\/\/www.wikidata.org\/entity\/Q25053762","author":{"@type":"Organization","name":"Contributors to Wikimedia projects"},"publisher":{"@type":"Organization","name":"Wikimedia Foundation, Inc.","logo":{"@type":"ImageObject","url":"https:\/\/www.wikimedia.org\/static\/images\/wmf-hor-googpub.png"}},"datePublished":"2015-09-17T04:14:33Z","dateModified":"2024-06-23T19:38:24Z","image":"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/d\/d2\/Internet_map_1024.jpg"}</script> </body> </html>