Title  A SPARSE COMPLETELY POSITIVE RELAXATION OF THE MODULARITY MAXIMIZATION FOR COMMUNITY DETECTION 
Author (Name in English or Pinyin)  
Date Issued  20180925 
Source Publication  SIAM JOURNAL ON SCIENTIFIC COMPUTING 
ISSN  10648275 
DOI  10.1137/17M1141904 
Firstlevel Discipline  信息科学与系统科学 
Education discipline  科技类 
Published range  国外学术期刊 
Volume Issue Pages  卷: 40 期: 5 页: A3091A3120 
References  [1] V. D. Blondel, J.L. Guillaume, R. Lambiotte, and E. Lefebvre, Fast unfolding of communities in large networks, J. Stat. Mech. Theory Exp., 10 (2008), 10008, https://doi.org/10.1088/17425468/2008/10/P10008. [2] T. T. Cai, X. Li, et al, Robust and computationally feasible community detection in the presence of arbitrary outlier nodes, Ann. Statist., 43 (2015), pp. 10271059. [3] K. Chaudhuri, F. C. Graham, and A. Tsiatas, Spectral clustering of graphs with general degrees in the extended planted partition model, JMLR Workshop Conf. Proc., 23 (2012), 35 [4] Y. Chen, X. Li, and J. Xu, Convexified modularity maximization for degreecorrected stochastic block models, Ann. Statist., 4 (2018), pp. 15731602. [5] Y. Chen, S. Sanghavi, and H. Xu, Clustering sparse graphs, in Advances in Neural Information Processing Systems, Curran, Red Hook, NY, 2012, pp. 22042212. [6] Y. Chen and J. Xu, Statisticalcomputational phase transitions in planted models: The highdimensional setting., in ICML, Curran, Red Hook, NY, 2014, pp. 244252. [7] A. CojaOghlan and A. Lanka, Finding planted partitions in random graphs with general degree distributions, SIAM J. Discrete Math., 23 (2010), pp. 16821714. [8] A. Dasgupta, J. E. Hopcroft, and F. McSherry, Spectral analysis of random graphs with skewed degree distributions, in Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, 2004, IEEE Computer Society, Los Alamitos, CA, 2004, pp. 602610. [9] T. A. Davis and Y. Hu, The University of Florida Sparse Matrix Collection, http://www.cise.ufl.edu/research/sparse/matrices (2011). [10] C. Ding, X. He, and H. D. Simon, On the equivalence of nonnegative matrix factorization and spectral clustering, in Proceedings of the 2005 SIAM International Conference on Data Mining, SIAM, Philadelphia, 2005, pp. 606610. [11] C. Ding, T. Li, W. Peng, and H. Park, Orthogonal nonnegative matrix tfactorizations for clustering, in Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, New York, 2006, pp. 126135. [12] O. Guédon and R. Vershynin, Community detection in sparse networks via Grothendiecks inequality, Probab. Theory Related Fields, 165 (2016), pp. 10251049. [13] L. Gulikers, M. Lelarge, and L. Massoulié, A spectral method for community detection in moderatelysparse degreecorrected stochastic block models, Adv. Appl. Probab., 49 (2017), pp. 686721. [14] P. W. Holland, K. B. Laskey, and S. Leinhardt, Stochastic blockmodels: First steps, Social Netw., 5 (1983), pp. 109137. [15] R. A. Horn and C. R. Johnson, Matrix Analysis, Cambridge University Press, Cambridge, 2012. [16] J. Jin, Fast community detection by score, Ann. Statist., 43 (2015), pp. 5789. [17] B. Karrer and M. E. Newman, Stochastic blockmodels and community structure in networks, Phys. Rev. E (3), 83 (2011), 016107. [18] J. Kim and H. Park, Sparse Nonnegative Matrix Factorization for Clustering, Technical report, Georgia Institute of Technology, Atlanta, GA, 2008. [19] D. Kuang, C. Ding, and H. Park, Symmetric nonnegative matrix factorization for graph clustering, in Proceedings of the 2012 SIAM International Conference on Data Mining, SIAM, Philadelphia, 2012, pp. 106117. [20] J. Leskovec and A. Krevl, SNAP Datasets: Stanford Large Network Dataset Collection, http://snap.stanford.edu/data (2014). [21] F. McSherry, Spectral partitioning of random graphs, in Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science, 2001, IEEE, Computer Society, Los Alamitos, CA, 2001, pp. 529537. [22] M. E. Newman, Modularity and community structure in networks, Proc. Natl. Acad. Sci. USA, 103 (2006), pp. 85778582. [23] M. E. Newman and G. Reinert, Estimating the number of communities in a network, Phys. Rev. Lett., 117 (2016), 078301. [24] S. Oymak and B. Hassibi, Finding Dense Clusters Via "Low Rank+ Sparse" Decomposition, https://arxiv.org/abs/1104.5186 (2011). [25] X. Pan, M. Lam, S. Tu, D. Papailiopoulos, C. Zhang, M. I. Jordan, K. Ramchandran, C. Re, and B. Recht, Cyclades: Conflictfree asynchronous machine learning, Advances in Neural Information Processing Systems, 2016, pp. 25682576. [26] S. Paul and Y. Chen, Orthogonal Symmetric Nonnegative Matrix Factorization Under the Stochastic Block Model, https://arxiv.org/abs/1605.05349 (2016). [27] I. Psorakis, S. Roberts, M. Ebden, and B. Sheldon, Overlapping community detection using Bayesian nonnegative matrix factorization, Phys. Rev. E (3), 83 (2011), 066114. [28] T. Qin and K. Rohe, Regularized spectral clustering under the degreecorrected stochastic blockmodel, in Advances in Neural Information Processing Systems, Curran, Red Hook, NY, 2013, pp. 31203128. [29] B. Recht, C. Re, S. Wright, and F. Niu, Hogwild: A lockfree approach to parallelizing stochastic gradient descent, in Advances in Neural Information Processing Systems, 2011, pp. 693701. [30] M. A. Riolo, G. T. Cantwell, G. Reinert, and M. Newman, Efficient method for estimating the number of communities in a network, Phys. Rev. E (3), 96 (2017), 032310. [31] K. Rohe, S. Chatterjee, and B. Yu, Spectral clustering and the highdimensional stochastic blockmodel, Ann. Statist., (2011), pp. 18781915. [32] D. L. Sussman, M. Tang, D. E. Fishkind, and C. E. Priebe, A consistent adjacency spectral embedding for stochastic blockmodel graphs, J. Amer. Statist. Assoc., 107 (2012), pp. 11191128. [33] A. L. Traud, E. D. Kelsic, P. J. Mucha, and M. A. Porter, Comparing community structure to characteristics in online collegiate social networks, SIAM Rev., 53 (2011), pp. 526543. [34] F. Wang, T. Li, X. Wang, S. Zhu, and C. Ding, Community discovery using nonnegative matrix factorization, Data Min. Knowl. Discov., 22 (2011), pp. 493521. [35] M. Wang, C. Wang, J. X. Yu, and J. Zhang, Community detection in social networks: An indepth benchmarking study with a procedureoriented framework, Proc. VLDB Endowment, 8 (2015), pp. 9981009. [36] Z. Yang, T. Hao, O. Dikmen, X. Chen, and E. Oja, Clustering by nonnegative matrix factorization using graph random walk, in Advances in Neural Information Processing Systems, Curran, Red Hook, NY, 2012, pp. 10791087. [37] Y. Zhang, E. Levina, and J. Zhu, Detecting Overlapping Communities in Networks using Spectral Methods, https://arxiv.org/abs/1412.3432 (2014). 
Citation statistics 
Cited Times [WOS]:0
[WOS Record]
[Related Records in WOS]

Document Type  Journal article 
Identifier  https://irepository.cuhk.edu.cn/handle/3EPUXD0A/148 
Collection  School of Data Science 
Corresponding Author  Zhang, Junyu 
Affiliation  1.Univ Minnesota, Dept Ind & Syst Engn, Minneapolis, MN 55455 USA 2.Peking Univ, Beijing Int Ctr Math Res, Beijing, Peoples R China 3.Chinese Univ Hong Kong , Inst Data & Decis Analyt, Shenzhen, Peoples R China 
Recommended Citation GB/T 7714  Zhang, Junyu,Liu, Haoyang,Wen, Zaiwenet al. A SPARSE COMPLETELY POSITIVE RELAXATION OF THE MODULARITY MAXIMIZATION FOR COMMUNITY DETECTION[J]. SIAM JOURNAL ON SCIENTIFIC COMPUTING,2018. 
APA  Zhang, Junyu, Liu, Haoyang, Wen, Zaiwen, & Zhang, Shuzhong. (2018). A SPARSE COMPLETELY POSITIVE RELAXATION OF THE MODULARITY MAXIMIZATION FOR COMMUNITY DETECTION. SIAM JOURNAL ON SCIENTIFIC COMPUTING. 
MLA  Zhang, Junyu,et al."A SPARSE COMPLETELY POSITIVE RELAXATION OF THE MODULARITY MAXIMIZATION FOR COMMUNITY DETECTION".SIAM JOURNAL ON SCIENTIFIC COMPUTING (2018). 
Files in This Item:  
There are no files associated with this item. 
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment