@article{9b71f06256c44f718a360fad19a1d4a2,
title = "Simplified Energy Landscape for Modularity Using Total Variation",
abstract = "Networks capture pairwise interactions between entities and are frequently used in applications such as social networks, food networks, and protein interaction networks, to name a few. Communities, cohesive groups of nodes, often form in these applications, and identifying them gives insight into the overall organization of the network. One common quality function used to identify community structure is modularity. In Hu et al. [SIAM J. Appl. Math., 73 (2013), pp. 2224--2246], it was shown that modularity optimization is equivalent to minimizing a particular nonconvex total variation (TV) based functional over a discrete domain. They solve this problem---assuming the number of communities is known---using a Merriman--Bence--Osher (MBO) scheme. We show that modularity optimization is equivalent to minimizing a convex TV-based functional over a discrete domain---again, assuming the number of communities is known. Furthermore, we show that modularity has no convex relaxation satisfying certain natural conditions. We therefore find a manageable nonconvex approximation using a Ginzburg--Landau functional, which provably converges to the correct energy in the limit of a certain parameter. We then derive an MBO algorithm that has fewer hand-tuned parameters than in Hu et al. and that is seven times faster at solving the associated diffusion equation due to the fact that the underlying discretization is unconditionally stable. Our numerical tests include a hyperspectral video whose associated graph has 2.9× 107 edges, which is roughly 37 times larger than what was handled in the paper of Hu et al.",
keywords = "Community detection, Data clustering, Graphs, MBO scheme, Modularity, Social networks",
author = "Boyd, {Zachary M.} and Egil Bae and Tai, {Xue Cheng} and Bertozzi, {Andrea L.}",
note = "Funding Information: The first and fourth authors' work was supported by NSF grants DMS-1417674,DMS-1118971, and DMS-1737770 as well as DARPA award FA8750-18-2-0066. The first and thirdauthors' work was supported by ISP-Matematikk (Project 2390033/F20) at the University of Bergen.The third author's work was additionally supported by the startup grant at Hong Kong BaptistUniversity, grant RG(R)-RC/17-18/02-MATH, and FRG2/17-18/033. The first author's work wasadditionally supported by the U.S. Department of Defense (DoD) through the National DefenseScience \& Engineering Graduate Fellowship (NDSEG) Program. Publisher copyright: {\textcopyright} 2018, Society for Industrial and Applied Mathematics",
year = "2018",
month = sep,
day = "13",
doi = "10.1137/17M1138972",
language = "English",
volume = "78",
pages = "2439--2464",
journal = "SIAM Journal on Applied Mathematics",
issn = "0036-1399",
publisher = "Society for Industrial and Applied Mathematics (SIAM)",
number = "5",
}