Skip to main content
Article
A Method Based on Total Variation for Network Modularity Optimization using the MBO Scheme
SIAM Journal on Applied Mathematics
  • Huiyi Hu, University of California, Los Angeles
  • Thomas Laurent, Loyola Marymount University
  • Mason A. Porter, University of Oxford
  • Andrea L. Bertozzi, University of California, Los Angeles
Document Type
Article - post-print
Publication Date
1-1-2013
Disciplines
Abstract

The study of network structure is pervasive in sociology, biology, computer science, and many other disciplines. One of the most important areas of network science is the algorithmic detection of cohesive groups of nodes called “communities.” One popular approach to finding communities is to maximize a quality function known as modularity to achieve some sort of optimal clustering of nodes. In this paper, we interpret the modularity function from a novel perspective: we reformulate modularity optimization as a minimization problem of an energy functional that consists of a total variation term and an $\ell_2$ balance term. By employing numerical techniques from image processing and $\ell_1$ compressive sensing---such as convex splitting and the Merriman--Bence--Osher (MBO) scheme---we develop a variational algorithm for the minimization problem. We present our computational results using both synthetic benchmark networks and real data.

Original Publication Citation

This is an author-manuscript of an article accepted for publication in SIAM Journal on Applied Mathematics following peer review. The version of record: H. Hu, T. Laurent, M. A. Porter and A. L. Bertozzi. A Method Based on Total Variation for Network Modularity Optimization using the MBO Scheme. SIAM J. Appl. Math., 73(6), pp. 2224-2246, 2013. is available online at: DOI:10.1137/130917387.

Citation Information
H. Hu, T. Laurent, M. A. Porter and A. L. Bertozzi. A Method Based on Total Variation for Network Modularity Optimization using the MBO Scheme. SIAM J. Appl. Math., 73(6), pp. 2224-2246, 2013. DOI:10.1137/130917387.