Community Detection in Graphs

It's good to see my article on HN, but I have to admit it's woefully incomplete.

I wrote the article a year ago, and I have continued to study community detection through today. There are a number of large recent developments that didn't make it into that post, particularly the methods based on the stochastic block model. This model is sort of the simplest idea you can have for a random graph with community structure: you specify the communities and probabilities for within-community and across-community edges.

The nice thing about the SBM is that we have a very precise theoretical understanding of when our best algorithms can and can't find the communities. And moreover, our best algorithms are spectral algorithms (which look at eigenvalues of the adjacency matrix of the network), which is another thing I completely ignored in the post. We also happen to know that SBM is particularly good for fitting to real data if that data has significant community structure.

If you're interested in more of this stuff, check out the lecture notes of Aaron Clauset[1] and in general the recent work of Mark Newman, Cris Moore, etc.

[1]: http://tuvalu.santafe.edu/~aaronc/courses/5352/fall2013/