BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//wp-events-plugin.com//7.2.3.1//EN
BEGIN:VEVENT
UID:44@lincs.fr
DTSTART;TZID=Europe/Paris:20160928T140000
DTEND;TZID=Europe/Paris:20160928T150000
DTSTAMP:20170313T170814Z
URL:https://www.lincs.fr/events/n-backtracking-spectrum-of-degree-correcte
 d-stochastic-block-models/
SUMMARY:n-Backtracking Spectrum of Degree-Corrected Stochastic Block Models
DESCRIPTION:Motivated by community detection\, we characterise the spectrum
 of the non-backtracking matrix $B$ in the Degree-Corrected Stochastic Block
 Model.Specifically\, we consider a random graph on $n$ vertices partitioned
 into two equal-sized clusters. The vertices have i.i.d. weights $ phi_u
 _u=1^n$ with second moment $PHItwo$. The intra-cluster connection
 probability for vertices $u$ and $v$ is $ phi_u phi_v a/b$ and the
 inter-cluster connection probability is $phi_u phi_v b/n$. We show that
 with high probability\, the following holds: The leading eigenvalue of the
 non-backtracking matrix $B$ is asymptotic to $rho = (a+b)/2 PHItwo$. The
 second eigenvalue is asymptotic to $mu_2 = (a+b)/2 PHItwo$ when $mu_2^2
 &gt\; rho$\, but asymptotically bounded by $sqrtrho$ when $mu_2^2 leq rho$.
 All the remaining eigenvalues are asymptotically bounded by $sqrtrho$. As a
 result\, a clustering positively-correlated with the true communities can
 be obtained based on the second eigenvector of $B$ in the regime where
 $mu_2^2 &gt\; rho.$In a previous work we obtained that detection is
 impossible when $mu_2^2 &lt\; rho\,$ meaning that there occurs a
 phase-transition in the sparse regime of the Degree-Corrected Stochastic
 Block Model. As a corollary\, we obtain that Degree-Corrected Erdos-Renyi
 graphs asymptotically satisfy the graph Riemann hypothesis\, a
 quasi-Ramanujan property.A by-product of our proof is a weak law of large
 numbers for local-functionals on Degree-Corrected Stochastic Block Models\,
 which could be of independent interest.
CATEGORIES:Seminars
LOCATION:LINCS Meeting Room 40\, 23\, avenue d'Italie\, Paris\, 75013\,
 France
GEO:48.8283983;2.3568972000000485
X-APPLE-STRUCTURED-LOCATION;VALUE=URI;X-ADDRESS=23\, avenue d'Italie\,
 Paris\, 75013\, France;X-APPLE-RADIUS=100;X-TITLE=LINCS Meeting Room
 40:geo:48.8283983,2.3568972000000485
END:VEVENT
BEGIN:VTIMEZONE
TZID:Europe/Paris
X-LIC-LOCATION:Europe/Paris
BEGIN:DAYLIGHT
DTSTART:20160327T030000
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
TZNAME:CEST
END:DAYLIGHT
END:VTIMEZONE
END:VCALENDAR