|
|
|
| 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.
|
|
Received: 31 July 2015
|
|
|
| About author:: LI Guopeng, born in 1982, Ph.D. candidate. His research interests include computational intelligence and pattern recognition. PAN Zhisong(Corresponding author), born in 1973, Ph.D.,professor. His research interests include pattern recognition and machine learning.YAO Qing, born in 1983, Ph.D., engineer. Her research interests include cloud computing.LI Deyi, born in 1944, Ph.D., professor. His research interests include artificial intelligence. |
|
|
|
[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 
