基于非负矩阵分解的复杂网络重构

陈增强; 谢征; 张青; 陈增强; 谢征; 张青

doi:10.13306/j.1672-3813.2016.03.004

复杂系统与复杂性科学 >

2016 , Vol. 13 >Issue 3: 26 - 32

DOI: https://doi.org/10.13306/j.1672-3813.2016.03.004

基于非负矩阵分解的复杂网络重构

陈增强 ,
谢征 ,
张青 ,
陈增强 ,
谢征 ,
张青

展开

1.南开大学计算机与控制工程学院天津市智能机器人技术重点实验室,天津 300071;
2.中国民航大学理学院,天津 300300

陈增强(1964-),男,天津人,博士,教授,主要研究方向为复杂网络,多智能体系统。

收稿日期: 2014-09-05

修回日期: 2014-11-16

网络出版日期: 2025-02-25

基金资助

国家自然科学基金(61174094);天津自然科学基金(14JCYBJC18700,13JCYBJC17400)

收起

Complex Network Reconstruction Based on Nonnegative Matrix Factorization

CHEN Zengqiang ,
XIE Zheng ,
ZHANG Qing ,
CHEN Zengqiang ,
XIE Zheng ,
ZHANG Qing

Expand

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

Received date: 2014-09-05

Revised date: 2014-11-16

Online published: 2025-02-25

Fold

摘要

将网络连边的产生机制和其社团结构结合在一起,基于社团结构决定网络连边的假设推导出节点间的连接概率矩阵并表达为矩阵乘积的形式,然后利用非负矩阵分解得到节点间的连接概率矩阵进行网络重建。设计实验并在几个真实的网络数据上测试,相比基于相似度的网络重构算法,该算法取得了更好的网络重构效果。

关键词： 复杂网络; 网络重构; 社团结构; 连接概率矩阵; 非负矩阵分解

本文引用格式

陈增强 , 谢征 , 张青 , 陈增强 , 谢征 , 张青 . 基于非负矩阵分解的复杂网络重构[J]. 复杂系统与复杂性科学, 2016 , 13(3) : 26 -32 . DOI: 10.13306/j.1672-3813.2016.03.004

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.

Key words： complex network; network reconstruction; community structure; connection probability matrix; nonnegative matrix factorization.

参考文献

[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.

Options

文章导航

模态框（Modal）标题

摘要

本文引用格式

Abstract

参考文献