A Method Based on Total Variation for Network Modularity Optimization using the MBO Scheme
arXiv:1304.4679
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 find communities is to maximize a quality function known as {\em 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 balance term. By employing numerical techniques from image processing and 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.
arXiv comment23 pages
References in corpus (18)
- Fast unfolding of communities in large networks
- Community structure in social and biological networks
- Finding and evaluating community structure in networks
- Community detection in graphs
- Finding community structure in very large networks
- Fast algorithm for detecting community structure in networks
- Finding community structure in networks using the eigenvectors of matrices
- Benchmark graphs for testing community detection algorithms
- Statistical Mechanics of Community Detection
- Community detection in complex networks using Extremal Optimization
- The performance of modularity maximization in practical contexts
- Social Structure of Facebook Networks
- Community Structure in Congressional Cosponsorship Networks
- Fast and Accurate Coarsening Simulation with an Unconditionally Stable Time Step
- Spectral tripartitioning of networks
- Gamma-convergence of graph Ginzburg-Landau functionals
- Stable image reconstruction using total variation minimization
- Multiclass Data Segmentation using Diffuse Interface Methods on Graphs