Spectral approaches to community detection
Presented by Prof. Dragan STEVANOVIć
Type: Keynote Lecture
Community detection is an important part of the analysis of naturally occuring networks. The quality of division into communities is measured mostly by modularity, representing the difference from the expected number of edges occuring within and between the communities. Here we reinterpret modularity within a more general framework for measuring the quality of community division and discuss on real-world examples a few related community division measures, related to the eigenvectors of the extremal eigenvalues of the adjacency and the normalized Laplacian matrices of network's complement. Due to expected large size of naturally occuring networks, we further study the result of using a new local search method for improving the quality of spectral division as opposed to the standard Kernighan-Lin heuristic.