Modularity-maximizing graph communities via mathematical programming

By Gaurav Agarwal, David Kempe. 2007

312 citations recorded by the source corpus.

In many networks, it is of great interest to identify communities, unusually densely knit groups of individuals. Such communities often shed light on the function of the networks or underlying properties of the individuals. Recently, Newman suggested modularity as a natural measure of the quality of a network partitioning into communities. Since then, various algorithms have been proposed for (approximately) maximizing the modularity of the partitioning determined. In this paper, we introduce the technique of rounding mathematical programs to the problem of modularity maximization, presenting two novel algorithms. More specifically, the algorithms round solutions to linear and vector programs. Importantly, the linear programing algorithm comes with an a posteriori approximation guarantee: by comparing the solution quality to the fractional solution of the linear program, a bound on the available “room for improvement” can be obtained. The vector programming algorithm provides a similar bound for the best partition into two communities. We evaluate both algorithms using experiments on several standard test cases for network partitioning algorithms, and find that they perform comparably or better than past algorithms, while being more efficient than exhaustive techniques.

Subfields: Geometry and Topology, Molecular Biology, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/b97a52a2ad5fa92dd1f485c6a87f515641a3e2f2

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Geometry and Topology

In Molecular Biology

In Statistical and Nonlinear Physics

Citations in the corpus

FENNEL: streaming graph partitioning for massive scale graphs (2014, methodology): “• A special case of interest is that of a modularity objective [21, 46, 5] for which we provide the first rigorous approximation guarantee.”
Community detection in graphs (2009, background): “Agarwal and Kempe have suggested to maximize modularity within the framework of mathematical programming (Agarwal and Kempe, 2008).”
Social Network Analysis and Mining for Business Applications (2011, methodology): “White and Smyth [2005] follow a spectral approach to optimize modularity and Agarwal and Kempe [2008] develop a mathematical programing algorithm, among many other algorithms.”
The community-search problem and how to plan a successful cocktail party (2010, methodology): “[6] showed that it is NP-hard to optimize modularity, Fortunato and Barthelemy [14] identify the resolution-limit problem, White and Smyth [29] follow a spectral approach to optimize modularity, Agarwal and Kempe [1] develop a mathematical-programing algorithm, and many more algorithms.”