BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Community recovery in weighted stochastic block models - Po-Ling L
 oh (University of Wisconsin-Madison)
DTSTART:20170706T104500Z
DTEND:20170706T113000Z
UID:TALK73175@talks.cam.ac.uk
CONTACT:INI IT
DESCRIPTION:<span>Co-authors: Min Xu		(University of Pennsylvania)\, Varun
  Jog		(University of Wisconsin - Madison)        <br></span><span><br>Iden
 tifying communities in a network is an important problem in many fields\, 
 including social science\, neuroscience\, military intelligence\, and gene
 tic analysis. In the past decade\, the Stochastic Block Model (SBM) has em
 erged as one of the most well-studied and well-understood statistical mode
 ls for this problem. Yet\, the SBM has an important limitation: it assumes
  that each network edge is drawn from a Bernoulli distribution. This is ra
 ther restrictive\, since weighted edges are fairly ubiquitous in scientifi
 c applications\, and disregarding edge weights naturally results in a loss
  of valuable information. In this paper\, we study a weighted generalizati
 on of the SBM\, where observations are collected in the form of a weighted
  adjacency matrix\, and the weight of each edge is generated independently
  from a distribution determined by the community membership of its endpoin
 ts. We propose and analyze a novel algorithm for community estimation in t
 he weighted SBM based on various su broutines involving transformation\, d
 iscretization\, spectral clustering\, and appropriate refinements. We prov
 e that our procedure is optimal in terms of its rate of convergence\, and 
 that the misclassification rate is characterized by the Renyi divergence b
 etween the distributions of within-community edges and between-community e
 dges. In the regime where the edges are sparse\, we also establish sharp t
 hresholds for exact recovery of the communities. Our theoretical results s
 ubstantially generalize previously established thresholds derived specific
 ally for unweighted block models. Furthermore\, our algorithm introduces a
  principled and computationally tractable method of incorporating edge wei
 ghts to the analysis of network data.</span>
LOCATION:Seminar Room 1\, Newton Institute
END:VEVENT
END:VCALENDAR