Tuesday, May 19, 2015 - 3:30pm - 4:20pm
This talk will be about the non-backtracking matrix of a graph. I will review recent works on its spectral properties for random graphs and concentrate on its algorithmic applications. Notably I will talk about optimality of the corresponding spectral algorithm for clustering of sparse networks and for analysis of percolation on sparse networks. The relation with linearized belief propagation for the corresponding graphical model will be instrumental.