8b7948f3a78a1410VgnVCM100000c2b1d38dRCRDapproved/UMICH/stats/Home/News & Events/Statistics SeminarSeminar Series: Belief Propagation and Phase Transitions in the Stochastic Block Model###@###(Wed, 16 Oct 2013)Seminar Series: Belief Propagation and Phase Transitions in the Stochastic Block Model###@###(Wed, 16 Oct 2013)4448 East Hall, 530 Church Street, Ann Arbor, MI, 48109-1043stats1381942800000138194280000001:00 PM<div style=" font-weight: normal; line-height: normal; font-variant: normal; orphans: auto; text-indent: 0px; widows: auto; word-spacing: 0px; font-size: 13px; text-align: start; background-color: rgb(255, 255, 255); color: rgb(34, 34, 34); white-space: normal; letter-spacing: normal; text-transform: none; font-family: arial, sans-serif; font-style: normal; -webkit-text-stroke-width: 0px;">The stochastic block model is a popular model of social and biological networks. &nbsp;It generalizes the Erdos-Renyi model by assigning each vertex to one of k groups, and having the probability of an edge depend on the groups to which its endpoints belong. &nbsp;It allows both "assortative" communities where vertices are more likely to connect to others of the same, and "disassortative" and directed community structures, like those in food webs, where predators form a community because they feed on similar prey. &nbsp;Given a graph, we would like to infer the most likely block model: both the group assignment of the nodes, and the parameters of the model. &nbsp;Recently, we gave an efficient algorithm for this problem based on belief propagation. &nbsp;In the sparse case, this algorithm appears to work (with some caveats) in nearly-linear time. &nbsp;</div> <div style=" font-weight: normal; line-height: normal; font-variant: normal; orphans: auto; text-indent: 0px; widows: auto; word-spacing: 0px; font-size: 13px; text-align: start; background-color: rgb(255, 255, 255); color: rgb(34, 34, 34); white-space: normal; letter-spacing: normal; text-transform: none; font-family: arial, sans-serif; font-style: normal; -webkit-text-stroke-width: 0px;"><br> </div> <div style=" font-weight: normal; line-height: normal; font-variant: normal; orphans: auto; text-indent: 0px; widows: auto; word-spacing: 0px; font-size: 13px; text-align: start; background-color: rgb(255, 255, 255); color: rgb(34, 34, 34); white-space: normal; letter-spacing: normal; text-transform: none; font-family: arial, sans-serif; font-style: normal; -webkit-text-stroke-width: 0px;">I will give an accessible explanation of this algorithm, including its connections with the cavity method of statistical physics. &nbsp;I will also discuss a phase transition in the detectability of communities, that we conjectured on the basis of the Kesten-Stigum bound, and that was recently proved by Mossel, Neeman, and Sly. &nbsp;If time permits, I will discuss other phase transitions in this model, such as in semisupervised learning where we are given the correct group labels for a certain fraction of the vertices, and some recent work on spectral algorithms for sparse networks.</div> <div style=" font-weight: normal; line-height: normal; font-variant: normal; orphans: auto; text-indent: 0px; widows: auto; word-spacing: 0px; font-size: 13px; text-align: start; background-color: rgb(255, 255, 255); color: rgb(34, 34, 34); white-space: normal; letter-spacing: normal; text-transform: none; font-family: arial, sans-serif; font-style: normal; -webkit-text-stroke-width: 0px;"><br> </div> <div style=" font-weight: normal; line-height: normal; font-variant: normal; orphans: auto; text-indent: 0px; widows: auto; word-spacing: 0px; font-size: 13px; text-align: start; background-color: rgb(255, 255, 255); color: rgb(34, 34, 34); white-space: normal; letter-spacing: normal; text-transform: none; font-family: arial, sans-serif; font-style: normal; -webkit-text-stroke-width: 0px;">This is joint work with Aurelien Decelle, Florent Krzakala, Lenka Zdeborova, and Pan Zhang.</div> <p>&nbsp;</p>Nbzunigabzuniga13815136614575b7948f3a78a1410VgnVCM100000c2b1d38d____once11112newnewProfessor Cris Moore, Santa Fe Institute