This site uses cookies. By continuing to use this site you agree to our use of cookies. To find out more, see our
Privacy and Cookies policy.
M. E. J. Newman 2013 EPL 103 28003 doi:10.1209/0295-5075/103/28003
M. E. J. Newman
Show affiliationsMany 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. Both the quality of the results and the running time rival the best previous methods.
Issue 2 (July 2013)
Received 7 June 2013, accepted for publication 16 July 2013
Published 9 August 2013
Total article downloads: 42
M. E. J. Newman 2013 EPL 103 28003
