Complex Network Reconstruction Based on Nonnegative Matrix Factorization
CHEN Zengqiang1,2, XIE Zheng1, ZHANG Qing2
1. Tianjin Key Laboratory of Intelligent Robotics, College of Computer & Control Engineering,Nankai University, Tianjin 300071, China; 2. College of Science, Civil Aviation University of China, Tianjin 300300, China
Abstract：Based on the hypothesis that community structure determines the network connections, the connection probability matrix which describes the nodes’ community structure can be transfered into the form of product of matrices. The nonnegative matrix factorization is applied here to get the connection probability matrix and then obtain the reconstruction. Experiments on several real world datasets show that the proposed algorithm outperforms some other algorithm which are based on similarity indexes.
[1] 汪小帆,李翔,陈关荣.网络科学导论[M].北京:高等教育出版社.2012:3-27. [2] 吕琳媛, 陆君安, 张子柯,等. 复杂网络观察[J].复杂系统与复杂性科学, 2010, 7(2/3): 173-186. Lü Linyuan, Lu Junan, Zhang Zike, et al. Looking into complex networks [J].Complex Systems and Complexity Science, 2010, 7(2/3): 173-186. [3] Albert R, Barabási|A L. Statistical mechanics of complex networks [J].Reviews of Modern Physics, 2002, 74(1): 47-97. [4] 方义,夏承遗,刘子超,等.闪烁小世界网络上疾病传播的动态行为研究[J].复杂系统与复杂性科学,2011, 8(3): 34-37. Fang Yi, Xia Chengyi, Liu Zichao, et al. Dynamical behavior of disease spreading on blinking small-world networks [J].Complex Systems and Complexity Science, 2011, 8(3): 34-37. [5] Xia C Y, Wang Z, Sanz J, et al. Effects of delayed recovery and nonuniform transmission on the spreading of diseases in complex in complex networks [J].Physica A, 2013, 392, 1577-1585. [6] Wang X F, Chen G R. Pinning control of scale-free dynamical networks [J].Physica A, 2002, 310(3/4): 521-531. [7] 吕琳瑗,周涛.链路预测[M].北京:高等教育出版社.2013: 42-56,172-212. [8] Guimerà R, Sales-Pardo M. Missing and spurious interactions and the reconstruction of complex networks [J].Proceedings of the National Academy of Sciences, 2009, 106(52): 22073-22078. [9] Shen Z, Wang W X, Fan Y, et al. Reconstructing propagation networks with natural diversity and identifying hidden sources[J].Nature Communications, 2014, 5(5):4323. [10] Lü L, Zhou T. Link prediction in complex networks: a survey[J].Physica A: Statistical Mechanics and Its Applications, 2011, 390(6): 1150-1170. [11] Liben‐Nowell D, Kleinberg J. The link-prediction problem for social networks[J].Journal of the American Society for Information Science and Technology, 2007, 58(7): 1019-1031. [12] Zhou T, Lü L, Zhang Y C. Predicting missing links via local information[J].The European Physical Journal B-Condensed Matter and Complex Systems, 2009, 71(4): 623-630. [13] Clauset A, Moore C, Newman M E J. Hierarchical structure and the prediction of missing links in networks [J].Nature, 2008, 453(7191): 98-101. [14] Gao S, Denoyer L, Gallinari P. Temporal link prediction by integrating content and structure information [C]//Proceedings of the 20th ACM International Conference on Information and Knowledge Management. Glasgow, Scotland, UK: ACM, 2011: 1169-1174. [15] Candès E J, Recht B. Exact matrix completion via convex optimization[J].Foundations of Computational Mathematics, 2009, 9(6): 717-772. [16] Candès E J, Li X, Ma Y, et al. Robust principal component analysis?[J].Journal of the ACM, 2011, 58(3): 11-12. [17] 程学旗, 沈华伟. 复杂网络的社区结构[J].复杂系统与复杂性科学, 2011, 8(1): 57-70. Cheng Xueqi, Shen Huawei. Community structure of complex networks [J].Complex Systems and Complexity Science, 2011, 8(1): 57-70. [18] Lee D D, Seung H S. Learning the parts of objects by non-negative matrix factorization [J].Nature, 1999, 401(6755): 788-791. [19] Ding C, He X, Simon H D. On the equivalence of nonnegative matrix factorization and spectral clustering[C]//SIAM International Conference on Data Mining. Vancouver, British Columbia, Canada: SIAM, 2005, 5: 606-610. [20] Ding C, Li T, Peng W, et al. Orthogonal nonnegative matrix t-factorizations for clustering[C]//Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Philadelphia, USA: ACM, 2006: 126-135. [21] Lee D D, Seung H S. Algorithms for non-negative matrix factorization[C]//Advances in Neural Information Processing Systems. Massachusetts, Cambridge, USA: The MIT Press, 2001: 556-562. [22] Cai D, He X, Han J, et al. Graph regularized nonnegative matrix factorization for data representation [J].IEEE Transactions on Pattern Analysis and Machine Intelligence, 2011, 33(8): 1548-1560. [23] Zachary W W. An information flow model for conflict and fission in small groups [J].Journal of Anthropological Research, 1977: 33(4): 452-473. [24] Vladimir B, Andrej M. Pajek datasets [DB/OL].[2013-12-30] , http://vlado.fmf.uni-lj.si/pub/networks/data/mix/USAir97.net. [25] Duch J, Arenas A. Community detection in complex networks using extremal optimization [J].Physical Review E, 2005, 72(2): 027104. [26] Watts D J, Strogatz S H. Collective dynamics of ‘small-world’ networks[J].Nature, 1998, 393(6684): 440-442.
