CONSISTENCY OF MODULARITY CLUSTERING ON RANDOM GEOMETRIC GRAPHS

• 成果类型: Article
• 署名作者: Davis, Erik; Sethuraman, Sunder
• 署名单位: University of Arizona
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/17-AAP1313
• 发表日期: 2018
• 页码: 2003-2062
• 关键词: Community Detection; gamma-convergence; least-perimeter; optimization; laplacian; approximation; inequalities; partitions; networks; limit

摘要

Given a graph, the popular modularity clustering method specifies a partition of the vertex set as the solution of a certain optimization problem. In this paper, we discuss scaling limits of this method with respect to random geometric graphs constructed from i.i.d. points X-n = {X-1, X-2,..., X-n}, distributed according to a probability measure nu supported on a bounded domain D subset of R-d. Among other results, we show, via a Gamma convergence framework, a geometric form of consistency: When the number of clusters, or partitioning sets of X-n is a priori bounded above, the discrete optimal modularity clusterings converge in a specific sense to a continuum partition of the underlying domain D, characterized as the solution to a soap bubble or Kelvin-type shape optimization problem.