Network clustering with higher order structures

-
David Gleich, Purdue University
Fine Hall 214

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.