Nonnegative Matrix Factorization Algorithm with Prior Information for Community Detection
LI Guopeng1,2, PAN Zhisong1, YAO Qing3, LI Deyi1,4
1.College of Command Information System, PLA University of Science and Technology, Nanjing 210007 2.Xi′an Communications Institute, Xi′an 710106 3.China Electronic Equipment System Engineering Company, Beijing 100079 4.Institute of China Electronic System Engineering Corporation, Beijing 100039
Abstract：To solve the problem of community detection in complex networks, a semi-supervised nonnegative matrix factorization (NMF) algorithm with prior information is proposed to obtain more accurate and better understanding results, and the detailed iteration algorithm is presented. In this algorithm, prior information is added to object function as additional constraints in community indicator matrix. Consequently, results are more meaningful. The experiments on real-world network datasets confirm the effectiveness of the proposed algorithm. It reduces the negative impact of the addition of prior information on node importance analysis with NMF, and it is suitable for weighted and un-weighted networks.
李国朋，潘志松， 姚 清，李德毅. 融合先验信息的非负矩阵分解社区发现算法*[J]. 模式识别与人工智能, 2016, 29(7): 608-615.
LI Guopeng, PAN Zhisong, YAO Qing, LI Deyi. Nonnegative Matrix Factorization Algorithm with Prior Information for Community Detection. , 2016, 29(7): 608-615.
[1] ZHANG Z Y, SUN K D, WANG S Q. Enhanced Community Structure Detection in Complex Networks with Partial Background Information [EB/OL]. [2015-07-20].http://arxiv.org/pdf/1210.2473v2.pdf. [2] LEE D D, SEUNG H S. Algorithms for Non-negative Matrix Factorization // LEEN T K, DIETTERICH T G, TRESP T V, eds. Advances in Neural Information Processing Systems Conference. Cambridge, USA: MIT Press, 2001: 556-562. [3] CHOO J, LEE C, REDDY C K, et al. Weakly Supervised Nonne-gative Matrix Factorization for User-Driven Clustering. Data Mining and Knowledge Discovery, 2015, 29(6): 1598-1621. [4] WANG F, LI T, WANG X, et al. Community Discovery Using Nonnegative Matrix Factorization. Data Mining and Knowledge Discovery, 2011, 22(3): 493-521. [5] LI G P, PAN Z S, XIAO B. Community Discovery and Importance Analysis in Social Network. Intelligent Data Analysis, 2014, 18(3): 495-510. [6] TANG J L, LIU H. Unsupervised Feature Selection for Linked Social Media Data // Proc of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, USA: ACM, 2012: 904-912. [7] YANG L, JIN D, WANG X, et al. Active Link Selection for Efficient Semi-supervised Community Detection. Scientific Reports, 2015. DOI: 10.1038/srep09039. [8] WANG Z X, WANG W J, XUE G X, et al. Semi-supervised Community Detection Framework Based on Non-negative Factorization Using Individual Labels // Proc of the 6th International Conference on Advances in Swarm and Computational Intelligence. Basel, Switzerland: Springer International Publishing, 2015, II: 349-359. [9] HE Y C, LU H T, HUANG L, et al. Non-negative Matrix Factorization with Pairwise Constraints and Graph Laplacian. Neural Process Letters, 2015, 42(1): 167-185. [10] JIN D, GABRYS B, DANG J W. Combined Node and Link Partitions Method for Finding Overlapping Communities in Complex Networks. Scientific Reports, 2015. DOI: 10.1038/srep08600. [11] NEWMAN M E J. Fast Algorithm for Detecting Community Structure in Networks. Physical Review E, 2004. DOI: 10.1103/PhysRevE.69.066133. [12] BEIS S, PAPADOPOULOS S, KOMPATSIARIS Y. Benchmarking Graph Databases on the Problem of Community Detection // Proc of the 18th East European Conference on Advances in Databases and Information Systems and Associated Satellite Events. Basel, Swit-zerland: Springer International Publishing, 2015, I: 3-14. [13] PEI Y L, CHAKRABORTY N, SYCARA K, et al. Nonnegative Matrix Tri-factorization with Graph Regularization for Community Detection in Social Networks // Proc of the 24th International Conference on Artificial Intelligence. Palo Alto, USA: AAAI Press, 2015: 2083-2089. [14] DANON L, DIAZ-GUILERA A, DUCH J, et al. Comparing Community Structure Identification. Journal of Statistical Mechanics:Theory and Experiment, 2014. DOI: 10.1088/1742-5468/2005/09/P09008. [15] HOYER P O. Non-negative Matrix Factorization with Sparseness Constraints. Journal of Machine Learning Research, 2004, 5:1457-1469.
2016, Vol. 29 
