基于边重要度的矩阵分解链路预测算法

doi:10.16451/j.cnki.issn1003-6059.201802006

摘要
图/表
参考文献(44)
相关文章 (13)

全文: PDF (683 KB) HTML (1 KB)
输出: BibTeX | EndNote (RIS)

摘要

基于矩阵分解的链路预测方法的领域适应性较好.然而在已有基于矩阵分解的链路预测方法中,0-1矩阵的网络数据表示对网络中未知连边的假设较强,同时对网络中已知连边的重要度无区分性.为此,文中放松0-1矩阵的网络数据表示假设,对未知节点对连边不做任何假设,并提出边重要度度量方法,对网络中已知连边进行重要度度量,最终建立基于网络权重矩阵分解的链路预测模型.在8个公开网络数据集上对比基于度量的链路预测方法和已有矩阵分解方法,文中方法链路预测结果更好.

	服务

	把本文推荐给朋友
	加入我的书架
	加入引用管理器
	E-mail Alert
	RSS
	作者相关文章
	郭丽媛
	王智强
	梁吉业

关键词 ：链路预测, 矩阵分解, 边重要度

Abstract：

The domain adaptability of link prediction method based on matrix factorization is fine. However, in the existing link prediction method based on matrix factorization, the network data representation of 0-1 matrix has a strong assumption of unknown edge in the network, while the importance of the known edges in the network is indistinguishable. The network data representation hypothesis of 0-1 matrix is relaxed in this paper, and no assumption to the edges of the unknown node-pairs is made. The measure method of importance of edges is put forward. Finally, the link prediction model based on the network weight matrix factorization is established by measuring the importance of the known edges in the network. The model is compared with the prediction algorithms based on metric and matrix factorization. Experimental results on eight public network datasets show the proposed algorithm is more effective.

Key words： Link Prediction Matrix Factorization Importance of Edges

收稿日期: 2017-05-12

ZTFLH:

TP 391

基金资助:

国家自然科学基金项目(No.U1435212,U61432011)、山西省重点科技攻关项目(No.MQ2014-09)资助

作者简介: 郭丽媛,女,硕士研究生,主要研究方向为社会计算.E-mail:15735176109@163.com.王智强,男,博士研究生,主要研究方向为社会网络分析、机器学习.E-mail:zhiq.wang@163.com.梁吉业,男,博士,教授,主要研究方向为粒计算、数据挖掘、机器学习.E-mail:ljy@sxu.edu.cn.

引用本文:

郭丽媛, 王智强, 梁吉业. 基于边重要度的矩阵分解链路预测算法[J]. 模式识别与人工智能, 2018, 31(2): 150-157. GUO Liyuan, WANG Zhiqiang, LIANG Jiye. Link Prediction Algorithm by Matrix Factorization Based on Importance of Edges. , 2018, 31(2): 150-157.

链接本文:

http://manu46.magtech.com.cn/Jweb_prai/CN/10.16451/j.cnki.issn1003-6059.201802006 或 http://manu46.magtech.com.cn/Jweb_prai/CN/Y2018/V31/I2/150

[1] HASAN M A, ZAKI M J. A Survey of Link Prediction in Social Networks // AGGARWAL C C, eds. Social Network Data Analytics. New York, USA: Springer, 2011: 243-275.
[2] MA H, YANG H X, LYU M R, et al. SoRec: Social Recommendation Using Probabilistic Matrix Factorization // Proc of the 17th ACM Conference on Information and Knowledge Management. New York, USA: ACM, 2008: 931-940.
[3] WANG Z Q, LIANG J Y, LI Y, et al. An Approach to Cold-Start Link Prediction: Establishing Connections between Non-topological and Topological Information. IEEE Transactions on Knowledge and Data Engineering, 2016, 28(11): 2857-2870.
[4] LIBEN-NOWELL D, KLEINBERG J. The Link-Prediction Problem for Social Networks. Journal of the American Society for Information Science and Technology, 2007, 58(7): 1019-1031.
[5] MITZENMACHER M. A Brief History of Generative Models for Power Law and Lognormal Distributions. Internet Mathematics, 2004, 1(2): 226-251.
[6] ADAMIC L A, ADAR E. Friends and Neighbors on the Web. Social Networks, 2003, 25(3): 211-230.
[7] ZHOU T, LÜ L Y, ZHANG Y C. Predicting Missing Links via Local Information. The European Physical Journal B, 2009, 71(4): 623-630.
[8] KATZ L. A New Status Index Derived from Sociometric Analysis. Psychometrika, 1953, 18(1): 39-43.
[9] JEH G, WIDOM J. SimRank: A Measure of Structural-Context Similarity // Proc of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, USA: ACM, 2002: 538-543.
[10] BRIN S, PAGE L. Reprint of: The Anatomy of a Large-Scale Hypertextual Web Search Engine. Computer Networks and ISDN Systems, 2012, 56(18): 3825-3833.
[11] CLAUSET A, MOORE C, NEWMAN M E J. Hierarchical Structure and the Prediction of Missing Links in Networks. Nature, 2008, 453: 98-101.
[12] WHITE H C, BOORMAN S A, BREIGER R L. Social Structure from Multiple Networks: I. Blockmodels of Roles and Positions. The American Journal of Sociology, 1976, 81(4): 730-780.
[13] ANDERSON C J, WASSERMAN S, FAUST K. Building Stochastic Boockmodels. Social Networks, 1992, 14(1/2): 137-161.
[14] DORELAN P, BATAGELJ V, FERLIGOJ A. Generalized Blockmodeling. Cambridge, UK: Cambridge University Press, 2004.
[15] 吴祖峰,梁棋,刘峤,等.基于AdaBoost的链路预测优化算法.通信学报, 2014, 35(3): 116-123.
(WU Z F, LIANG Q, LIU J, et al. Modified Link Prediction Algorithm Based on AdaBoost. Journal of Communication, 2014, 35(3): 116-123.)
[16] PAN Y, LAI H J, LIU C, et al. Rank Aggregation via Low-Rank and Structured-Sparse Decomposition // Proc of the 27th AAAI Conference on Artificial Intelligence. Palo Alto, USA: AAAI Press, 2013: 760-766.
[17] LEE J, KIM S, LEBANON G, et al. Local Low-Rank Matrix Approximation // Proc of the 30th International Conference on Machine Learning. Cambridge, USA: The MIT Press, 2013: 82-90.
[18] ZHENG Y G, ZHANG X R, YANG S Y, et al. Low-Rank Representation with Local Constraint for Graph Construction. Neurocomputing, 2013, 122: 398-405.
[19] BILLSUS D, PAZZANI M J. Learning Collaborative Information Filters // Proc of the 15th International Conference on Machine Learning. San Francisco, USA: Morgan Kaufmann, 1998: 46-54.
[20] YAZAMA Y, MITSUKURA Y, FUKUMI M, et al. Recognition from EMG Signals by an Evolutional Method and Non-negative Matrix Factorization // Proc of the 7th International Conference on Knowledge-Based Intelligent Information and Engineering Systems. New York, USA: Springer, 2003, I: 594-600.
[21] SALAKHUTDINOV R, MNIH A. Probalistic Matrix Factorization[C/OL]. [2017-04-28]. https://papers.nips.cc/paper/3208-probabilistic-matrix-factorization.pdf.
[22] SALAKHUTDINOV R. Bayesian Probabilistic Matrix Factorization Using MCMC[C/OL]. [2017-04-28]. http://www.cs.toronto.edu/~rsalakhu/papers/bpmf.pdf.
[23] LIU Y, WANG Z S, YIN J, et al. A Scalable Proximity Measure for Link Prediction via Low-Rank Matrix Estimation[C/OL]. [2017-04-28]. www.atlantis-press.com/php/download_paper.php?id=12639.
[24] MENON A K, ELKAN C. Link Prediction via Matrix Factorization // Proc of the Joint European Conference on Machine Learning and Knowledge Discovery in Databases. New York, USA: Springer, 2011, II: 437-452.
[25] PAGE L B, PERRY J E. Reliability Polynomials and Link Importance in Networks. IEEE Transactions on Reliability, 1994, 43(1): 51-58.
[26] NARDELLI E, PROIETTI G, WIDMAYER P. Finding the Detour-Critical Edge of a Shortest Path between Two Nodes. Information Processing Letters, 1998, 67(1): 51-54.
[27] NARDELLI E, PROIETTI G, WIDMAYER P. A Faster Computation of the Most Vital Edge of a Shortest Path. Information Processing Letters, 2001, 79(2): 81-85.
[28] TRALDI L. Commentary on: Reliability Polynomials and Link Importance in Networks. IEEE Transactions on Reliability, 2000, 49(3): 322.
[29] HSU L H, JAN R H, LEE Y C, et al. Finding the Most Vital Edge with Respect to Minimum Spanning Tree in Weighted Graphs. Information Processing Letters, 1991, 39(5): 277-281.
[30] RAO V V B. Most-Vital Edge of a Graph with Respect to Spanning Trees. IEEE Transactions on Reliability, 1998, 47(1): 6-7.
[31] TSEN F S P, SUNG T Y, LIN M Y, et al. Finding the Most Vital Edges with Respect to the Number of Spanning Trees. IEEE Transactions on Reliability, 1994, 43(4): 600-602.
[32] BALL M O, GOLDEN B L, VOHRA R V. Finding the Most Vital Arcs in a Network. Operations Research Letters, 1989, 8(2): 73-76.
[33] KOREN Y, BELL R, VOLINSKY C. Matrix Factorization Techniques for Recommender Systems. Computer, 2009, 42(8): 30-37.
[34] SALAKHUTDINOV R, MNIH A. Probabilistic Matrix Factorization[C/OL]. [2017-04-28]. https://papers.nips.cc/paper/3208-probabilistic-matrix-factorization.pdf.
[35] ZACHARY W W. An Information Flow Model for Conflict and Fission in Small Groups. Journal of Anthropological Research, 1977, 33(4): 452-473.
[36] LÓPEZ B D, SHIRAI J A B. Marine Aquaculture and Bottlenose
Dolphins′(Tursiops Truncatus) Social Structure. Behavioral Ecology & Sociobiology, 2008, 62: 887-894.
[37] KNUTH D E. The Stanford GraphBase: A Platform for Computing. New York, USA: ACM, 1993.
[38] WATTS D J, STROGATZ S H. Collective Dynamics of ′Small World′ Networks. Nature, 1998, 393: 440-442.
[39] KRSTULOVIC S, HUNECKE A, SCHRÖDER M. An HMM-Based Speech Synthesis System Applied to German and Its Adaptation to a Limited Set of Expressive Football Announcements // Proc of the 8th Annual Conference of the International Speech Communication Association. Berlin, Germany: Springer, 2007:1897-1900.
[40] ALMUNIA J, BASTERRETXEA G, ARISTEGUI J, et al. Benthic-Pelagic Switching in a Coastal Subtropical Lagoon. Estuarine, Coastal and Shelf Science, 1999, 49(3): 363-384.
[41] LÜ L Y, ZHOU T. Link Prediction in Complex Networks: A Survey. Physica A: Statistical Mechanics and Its Applications, 2011, 390(6): 1150-1170.
[42] 吕琳媛.复杂网络链路预测.电子科技大学学报, 2010, 39(5): 651-661.
(LÜ L Y. Link Prediction on Complex Networks. Journal of University of Electronic Science & Technology of China, 2010, 39(5): 651-661.)
[43] KALMAN D. A Singularly Valuable Decomposition: The SVD of a Matrix. The College Mathematics Journal, 1996, 27(1): 2-23
[44] SPRING N, MAHAJAN R, WETHERALL D, et al. Measuring ISP Topologies with Rocketfuel. IEEE/ACM Transactions on Networking, 2004, 12(1): 2-16.