A Sparse Completely Positive Relaxation of the Modularity Maximization for Community Detection

DOI10.1137/17M1141904zbMath1405.90082arXiv1708.01072OpenAlexW2962823402MaRDI QIDQ4685333

ZaiWen Wen, Haoyang Liu, Junyu Zhang, Shu-Zhong Zhang

Publication date: 8 October 2018

Published in: SIAM Journal on Scientific Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1708.01072

zbMATH Keywords

community detectioncompletely positive relaxationdegree-correlated stochastic block modelnonasymptotic error boundproximal block coordinate descent method

Mathematics Subject Classification ID

Integer programming (90C10) Nonconvex programming, global optimization (90C26) Nonlinear programming (90C30)

Related Items (4)

An exact penalty approach for optimization with nonnegative orthogonality constraints ⋮ Primal-dual optimization algorithms over Riemannian manifolds: an iteration complexity analysis ⋮ A brief introduction to manifold optimization ⋮ Kurdyka-Łojasiewicz property of zero-norm composite functions

Uses Software

• SNAP
• SparseMatrix
• CYCLADES
• HOGWILD

Cites Work

• Fast community detection by SCORE
• Community discovery using nonnegative matrix factorization
• Spectral clustering and the high-dimensional stochastic blockmodel
• Community detection in sparse networks via Grothendieck's inequality
• Robust and computationally feasible community detection in the presence of arbitrary outlier nodes
• Convexified modularity maximization for degree-corrected stochastic block models
• The university of Florida sparse matrix collection
• Finding Planted Partitions in Random Graphs with General Degree Distributions
• A Consistent Adjacency Spectral Embedding for Stochastic Blockmodel Graphs
• A spectral method for community detection in moderately sparse degree-corrected stochastic block models
• Fast unfolding of communities in large networks

This page was built for publication: A Sparse Completely Positive Relaxation of the Modularity Maximization for Community Detection