Network clustering with higher order structures

Monday, October 3, 2016 -
4:00pm to 5:00pm
Spectral clustering is a well-known way to partition a graph or network into clusters or communities with provable guarantees on the quality of the clusters. This guarantee is known as the Cheeger inequality and it holds for undirected graphs. We'll discuss a new generalization of the Cheeger inequality to higher-order structures in networks including network motifs. This is easy to implement and seamlessly generalizes spectral clustering to directed, signed, and many other types of complex networks. In particular, our generalization allow us to re-use the large history of existing ideas in spectral clustering including local methods, overlapping methods, and relationships with kernel k-means. We will illustrate the types of clusters or communities found by our new method in biological, neuroscience, ecological, transportation, and social networks.This is joint work with Austin Benson and Jure Leskovec at Stanford.
David Gleich
Purdue University
Event Location: 
Fine Hall 214