基于加权非负矩阵分解的链接预测算法

doi:10.3969/j.issn.0372-2112.2016.10.016

电子学报 ›› 2016, Vol. 44 ›› Issue (10): 2391-2397.DOI: 10.3969/j.issn.0372-2112.2016.10.016

基于加权非负矩阵分解的链接预测算法

王萌萌^1,2, 左万利^1,2, 王英^1,2

1. 吉林大学计算机科学与技术学院, 吉林长春 130012;
2. 符号计算与知识工程教育部重点实验室(吉林大学), 吉林长春 130012

收稿日期:2015-03-30 修回日期:2015-08-03 出版日期:2016-10-25 发布日期:2016-10-25
通讯作者: 王英
作者简介:王萌萌,女,1987年出生,吉林长春人,2013年至今于吉林大学计算机学院攻读博士学位,从事社会网络分析、自然语言处理等有关研究.E-mail:wmmwwlh@126.com;左万利,男,1957年出生,吉林长春人,博士,教授、博士生导师,从事社会网络分析、网络搜索引擎、自然语言处理等有关研究.E-mail:wanli@jlu.edu.cn
基金资助:
国家自然科学基金（No.61300148）；吉林省科技发展计划（No.20130206051GX）；吉林省科技计划（No.20130522112JH）；吉林大学基本科研业务费科学前沿与交叉项目（No.201103129）

Link Prediction Model Based on Weighted Nonnegative Matrix Factorization

WANG Meng-meng^1,2, ZUO Wan-li^1,2, WANG Ying^1,2

1. College of Compuer Science and Technology, Jilin University, Changchun, Jilin 130012, China;
2. Key Laboratory of Symbolic Computation and Knowledge Engineering(Jilin University), Ministry of Education, Changchun, Jilin 130012, China

Received:2015-03-30 Revised:2015-08-03 Online:2016-10-25 Published:2016-10-25

摘要/Abstract

摘要：

本文针对在线微博，首先，基于带权动态链接预测特征集合，以用户社会关系因子约束目标函数，从用户概要和用户发布内容两个维度利用非负矩阵分解方法预测社会网络中链接的存在性和方向性.然后，在真实的数据集上验证了提出框架的有效性，并通过实验进一步证明了特征权重和时间信息在链接预测问题中的重要性.

关键词: 有向链接预测, 非负矩阵分解, 特征权重, 时间信息, 动态社会网络

Abstract:

Targeted at on-line microbloggings,on the basis of weighted and dynamic link prediction features,we utilize nonnegative matrix factorization to predict existence and directivity of link from user-based and post-based dimension by employing relationship-based factor to constrain objective function.Experiments on real-world dataset demonstrate the effectiveness of the proposed framework.Further experiments are conducted to understand the importance of features' weights and temporal information in link prediction.

Key words: directed link prediction, nonnegative matrix factorization, features' weights, temporal information, dynamic social networks

中图分类号:

TP393.03

王萌萌, 左万利, 王英. 基于加权非负矩阵分解的链接预测算法[J]. 电子学报, 2016, 44(10): 2391-2397.

WANG Meng-meng, ZUO Wan-li, WANG Ying. Link Prediction Model Based on Weighted Nonnegative Matrix Factorization[J]. Acta Electronica Sinica, 2016, 44(10): 2391-2397.

参考文献

[1] Airoldi E M,et al.Mixed membership stochastic block models for relational data with application to protein-protein interactions[A].Proceedings of ICML Workshop on Statistical Network Analysis[C].Pittsburgh,Pennsylvania,USA:Springer,2006.57-74.
[2] Hasan M Al,et al.Link prediction using supervised learning[A].Proceedings of Workshop on Link Analysis,Counter-terrorism and Security[C].Maryland,USA:SIAM,2006.322-331.
[3] Henzinger M R.Link analysis in web information retrieval[J].IEEE Data Engineering Bulletin,2000,23(3):3-8.
[4] Huang Z,et al.Link prediction approach to collaborative filtering[A].Proceedings of the 5th ACM/IEEE-CS Joint Conference on Digital libraries[C].Denver,Colorado,USA:ACM,2005.141-142.
[5] Lichtenwalter R N,et al.New perspectives and methods in link prediction[A].Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining[C].Washington,DC,USA:ACM,2010.243-252.
[6] Hasan M A,Zaki M J.A survey of link prediction in social networks[J].Social Network Data Analytics,2011,(2011):243-275.
[7] Lu L,Zhou T.Link prediction in complex networks:a survey[J].Physica A,2011,390(6):1150-1170.
[8] An J,et al.Social relation predictive model of mobile nodes in Internet of things[J].Elektronika Ir Elektrotechnika,2013,19(4):81-86.
[9] Schall D.Link prediction in directed social networks[J].Social Network Analysis and Mining,2014,4(1):1-14.
[10] Symeonidis P,Mantas N.Spectral clustering for link prediction in social networks with positive and negative links[J].Social Network Analysis and Mining,2013,3(4):1433-1447.
[11] Fire M,et al.Computationally efficient link prediction in a variety of social networks[J].ACM Transactions on Intelligent Systems and Technology,2013,5(1):10.
[12] Lou T,et al.Learning to predict reciprocity and triadic closure in social networks[J].ACM Transactions on Knowledge Discovery from Data,2013,7(2):5.
[13] Jorge V R,Alneu A L.Exploiting behaviors of communities of twitter users for link prediction[J].Social Network Analysis and Mining,2013,3(4):1063-1074.
[14] Soares Paulo R S,Prudêncio Ricardo B C.Time series based link prediction[A].Proceedings of the 2012 International Joint Conference on Neural Networks[C].Brisbane,Australia:IEEE,2012.1-7.
[15] Soares Paulo R S,Prudêncio Ricardo B C.Proximity measures for link prediction based on temporal events[J].Expert Systems with Applications,2013,40(16):6652-6660.
[16] Zhang J,et al.LaFT-tree:perceiving the expansion trace of one's circle of friends in online social networks[A].Proceedings of the sixth ACM International Conference on Web Search and Data Mining[C].Rome,Italy:ACM,2013.597-606.
[17] Zhang J,et al.Social influence locality for modeling retweeting behaviors[A].Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence[C].Beijing,China:IJCAI/AAAI,2013.2761-2767.
[18] Leskovec J,et al.Signed networks in social media[A].Proceedings of the SIGCHI Conference on Human Factors in Computing Systems[C].Atlanta,Georgia,USA:ACM,2010.1361-1370.
[19] 李乐,章毓晋.非负矩阵分解算法综述[J].电子学报,2008,36(4):737-743. Li L,Zhang Y J.A survey on algorithms of non-negative matrix factorization[J].Acta Electronica Sinica,2008,36(4):737-743.(in Chinese)
[20] Lee D D,Seung H S.Learning the parts of objects by non-negative matrix factorization[J].Nature,1999,401(6755):788-791.

基于加权非负矩阵分解的链接预测算法

Link Prediction Model Based on Weighted Nonnegative Matrix Factorization

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	张二华, 王明合, 唐振民. 加性噪声条件下鲁棒说话人确认[J]. 电子学报, 2019, 47(6): 1244-1250.
[2]	贺超波, 汤庸, 张琼, 刘双印, 刘海. 基于增量式鲁棒非负矩阵分解的短文本在线聚类[J]. 电子学报, 2019, 47(5): 1086-1093.
[3]	范利云, 左万利, 王英, 王鑫. 一种基于差分隐私和时序的推荐系统模型研究[J]. 电子学报, 2017, 45(9): 2057-2064.
[4]	常振超, 陈鸿昶, 王凯, 卫红权, 黄瑞阳. 基于图流在线非负矩阵分解的社团检测[J]. 电子学报, 2017, 45(9): 2077-2084.
[5]	吴奇, 陈福才, 黄瑞阳, 常振超. 基于语义路径的异质网络社区发现方法[J]. 电子学报, 2016, 44(6): 1465-1471.
[6]	刘正, 张国印, 陈志远. 基于特征加权和非负矩阵分解的多视角聚类算法[J]. 电子学报, 2016, 44(3): 535-540.
[7]	叶有时, 刘淑芬, 孙强, 刘鸿瑾, 刘波, 杨桦, 吴一帆. 改进粒子滤波算法在深空红外小目标跟踪中的应用[J]. 电子学报, 2015, 43(8): 1506-1512.
[8]	刘建军, 吴泽彬, 韦志辉, 肖亮, 孙乐. 基于约束非负矩阵分解的高光谱图像解混快速算法[J]. 电子学报, 2013, 41(3): 432-437.
[9]	史加荣;焦李成;尚凡华. 不完全非负矩阵分解的加速算法[J]. 电子学报, 2011, 39(2): 291-295.
[10]	邓晓政;焦李成;卢山. 基于非负矩阵分解的谱聚类集成SAR图像分割[J]. 电子学报, 2011, 39(12): 2905-2909.
[11]	薛二娟;鲍长春;李如玮. 基于二维非负矩阵分解的1kb/s WI语音编码算法[J]. 电子学报, 2010, 38(7): 1574-1579.
[12]	龙泓琳;皮亦鸣;曹宗杰. 基于非负矩阵分解的SAR图像目标识别[J]. 电子学报, 2010, 38(6): 1425-1429.
[13]	郭莉莉;鲍长春. 基于贝叶斯阴阳机的2kb/s NMF-WI语音编码算法[J]. 电子学报, 2009, 37(5): 1146-1153.
[14]	李乐;章毓晋;. 非负矩阵分解算法综述[J]. 电子学报, 2008, 36(4): 737-743.
[15]	张鹏;鲍长春;郭莉莉. 基于非负矩阵分解的2kb/s波形内插语音编码算法[J]. 电子学报, 2008, 36(4): 632-638.