Communities, Spectral Clustering, and Random Walks
David Bindel (CS, Cornell)

We think of a community in a social network as a subgraph that is unusually tightly connected. But there are many possible definitions of what it means to be unusually tightly connected, and these lead to a plethora of formal definitions of communities in terms of subgraphs that minimize or maximize some metric. Several of these metrics can be expressed in terms of quadratic forms, and so relaxed versions of these optimization problems lead naturally to eigenvalue problems and to spectral methods to community detection. After discussing some standard spectral ideas that produce detect disjoint communities, we discuss a new approach to finding overlapping communities by a constrained l1 minimization problem over a subspace. We then turn to another approach to community detection based on the intermediate dynamics of random walks. Though superficially dissimilar to the spectral approach, we show that this random-walk-based method is fundamentally related to standard iterations for computing eigenvectors. We also comment on a curious connection between community detection via random walks and the dynamics of transitions between quasi-equilibrium states in chemical physics.