Community detection and graph partitioning

Understand

Many methods have been proposed for community detection in networks.

• Some of the most promising are methods based on statistical inference, which rest on solid mathematical foundations and return excellent results in practice.
• In this paper we show that two of the most widely used inference methods can be mapped directly onto versions of the standard minimum-cut graph partitioning problem, which allows us to apply any of the many well-understood partitioning algorithms to the solution of community detection problems.
• We illustrate the approach by adapting the Laplacian spectral partitioning method to perform community inference, testing the resulting algorithm on a range of examples, including computer-generated and real-world networks.