---
title: "Modular Community Detection in Networks"
authors:
  - "Wenye Li"
  - "Dale Schuurmans"
doi: "10.5591/978-1-57735-516-8/IJCAI11-231"
url: "https://ijcai.org/proceedings/2011/231"
pdf: "https://ijcai.org/proceedings/2011/0231.pdf"
venue: "Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence"
year: 2011
pages: "1366-1370"
track: ""
keywords:
---

# Modular Community Detection in Networks

Wenye Li, Dale Schuurmans

*Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence*, pages 1366-1370. DOI: [10.5591/978-1-57735-516-8/IJCAI11-231](https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-231)

## Abstract

Network community detection — the problem of dividing a network of interest into clusters for intelligent analysis — has recently attracted significant attention in diverse fields of research. To discover intrinsic community structure a quantitative measure called modularity has been widely adopted as an optimization objective. Unfortunately, modularity is inherently NP-hard to optimize and approximate solutions must be sought if tractability is to be ensured. In practice, a spectral relaxation method is most often adopted, after which a community partition is recovered from relaxed fractional values by a rounding process. In this paper, we propose an iterative rounding strategy for identifying the partition decisions that is coupled with a fast constrained power method that sequentially achieves tighter spectral relaxations. Extensive evaluation with this coupled relaxation-rounding method demonstrates consistent and sometimes dramatic improvements in the modularity of the communities discovered.