{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,18]],"date-time":"2026-09-18T08:24:44Z","timestamp":1789719884773,"version":"4.0.1"},"reference-count":37,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"5","funder":[{"DOI":"10.13039\/501100005146","name":"Basic Research Programs of Sichuan Province","doi-asserted-by":"publisher","award":["2015CB856002"],"award-info":[{"award-number":["2015CB856002"]}],"id":[{"id":"10.13039\/501100005146","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11421101"],"award-info":[{"award-number":["11421101"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Sci. Comput."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>In this paper, we consider the community detection problem under either the stochastic block model (SBM) assumption or the degree-correlated SBM assumption. The modularity maximization formulation for the community detection problem is NP-hard in general. In this paper, we propose a sparse and low-rank completely positive relaxation for the modularity maximization problem, we then develop an efficient row-by-row (RBR)-type block coordinate descent algorithm to solve the relaxation and prove an $\\mathcal{O}(1\/\\sqrt{N})$ convergence rate to a stationary point, where $N$ is the number of iterations. A fast rounding scheme is constructed to retrieve the community structure from a solution to the above relaxation. Nonasymptotic high probability bounds on the misclassification rate are established to justify our approach. We further develop an asynchronous parallel RBR algorithm to speed up the convergence. Extensive numerical experiments on both synthetic and real world networks show that the proposed approach enjoys advantages in both clustering accuracy and numerical efficiency. Our numerical results indicate that the newly proposed method is a competitive alternative for the community detection problem on sparse networks with over 50 million nodes.<\/jats:p>","DOI":"10.1137\/17m1141904","type":"journal-article","created":{"date-parts":[[2018,9,25]],"date-time":"2018-09-25T10:43:51Z","timestamp":1537872231000},"page":"A3091-A3120","source":"Crossref","is-referenced-by-count":13,"title":["A Sparse Completely Positive Relaxation of the Modularity Maximization for Community Detection"],"prefix":"10.1137","volume":"40","author":[{"given":"Junyu","family":"Zhang","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Haoyang","family":"Liu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zaiwen","family":"Wen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5838-1676","authenticated-orcid":true,"given":"Shuzhong","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,9,25]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1088\/1742-5468\/2008\/10\/P10008"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1214\/14-AOS1290"},{"key":"atypb3","first-page":"23","volume-title":"Proc.","author":"Chaudhuri K.","year":"2012"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1214\/17-AOS1595"},{"key":"atypb5","first-page":"2204","volume-title":"Curran","author":"Chen Y.","year":"2012"},{"key":"atypb6","first-page":"244","volume-title":"Curran","author":"Chen Y.","year":"2014"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1137\/070699354"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.61"},{"key":"atypb9","doi-asserted-by":"crossref","unstructured":"T. A. Davis and Y. Hu,\n                      The University of Florida Sparse Matrix Collection\n                      ,http:\/\/www.cise.ufl.edu\/research\/sparse\/matrices(2011).","DOI":"10.1145\/2049662.2049663"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972757.70"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1145\/1150402.1150420"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-015-0659-z"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1017\/apr.2017.18"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1016\/0378-8733(83)90021-7"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139020411"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1214\/14-AOS1265"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.83.016107"},{"key":"atypb18","volume-title":"Technical report","author":"Kim J.","year":"2008"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972825.10"},{"key":"atypb20","unstructured":"J. Leskovec and A. Krevl,\n                      SNAP Datasets: Stanford Large Network Dataset Collection\n                      ,http:\/\/snap.stanford.edu\/data(2014)."},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2001.959929"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0601602103"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.117.078301"},{"key":"atypb24","volume-title":"\u201cLow Rank+ Sparse\" Decomposition, https:\/\/arxiv.org\/abs\/1104.5186","author":"Oymak S.","year":"2011"},{"key":"atypb25","first-page":"2568","author":"Pan X.","year":"2016","journal-title":"Advances in Neural Information Processing Systems"},{"key":"atypb26","volume-title":"Orthogonal Symmetric Non-negative Matrix Factorization Under the Stochastic Block Model, https:\/\/arxiv.org\/abs\/1605.05349","author":"Paul S.","year":"2016"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.83.066114"},{"key":"atypb28","first-page":"3120","volume-title":"Curran","author":"Qin T.","year":"2013"},{"key":"atypb29","first-page":"693","author":"Recht B.","year":"2011","journal-title":"Advances in Neural Information Processing Systems"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.96.032310"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1214\/11-AOS887"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.2012.699795"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1137\/080734315"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-010-0181-y"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.14778\/2794367.2794370"},{"key":"atypb36","first-page":"1079","volume-title":"Curran","author":"Yang Z.","year":"2012"},{"key":"atypb37","volume-title":"Detecting Overlapping Communities in Networks using Spectral Methods, https:\/\/arxiv.org\/abs\/1412.3432","author":"Zhang Y.","year":"2014"}],"container-title":["SIAM Journal on Scientific Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/17M1141904","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T17:31:41Z","timestamp":1787333501000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/17M1141904"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":37,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/17M1141904"],"URL":"https:\/\/doi.org\/10.1137\/17m1141904","relation":{},"ISSN":["1064-8275","1095-7197"],"issn-type":[{"value":"1064-8275","type":"print"},{"value":"1095-7197","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}