-
摘要: 时序链路预测是动态网络分析的重要组成部分,具有极大的理论和应用价值. 传统的时序链路预测方法往往直接对边的演化规律进行分析,忽略了网络中其他微观结构的演化对链路形成的影响. 基于此分析,本文引入非负张量分解和时间序列分析对网络模体的演化规律进行研究,进而提出一种基于模体演化的链路预测方法. 在三个真实数据集上的实验结果表明,该方法能有效提高链路预测精度.Abstract: Temporal link prediction, which has great value in both research and application, is an important component of the dynamic network analysis. Traditional temporal link prediction methods trend to directly analyze the edge's evolution regularity, while ignoring the influence of other microstructure evolution on link formation. On the basis of this analysis, we adopt the nonnegative tensor decomposition and time series analysis model to extract the evolution regulars of motif, and then propose a temporal link prediction method based on motif evolution. Experimental results on three real data sets show that our method can effectively improve the link prediction accuracy.
-
图 6 Facebook数据集不同三元组类型间转换概率随时间变化色谱图
Fig. 6 Chromatogram of triad transition probabilities that change with time in Facebook network
图 7 Facebook数据集中部分随时间变化的三元组转换概率示意图
Fig. 7 Diagram of some triad transition probabilities that change with time in Facebook network
图 10 Facebook数据集TCM算法和TTM算法性能对比图
Fig. 10 Performance contrastgures of TCM algorithm and TTM algorithm in Facebook network
图 11 Enron数据集TCM算法和TTM算法性能对比图
Fig. 11 Performance contrastgures of TCM algorithm and TTM algorithm in Enron network
图 12 Condmat数据集TCM算法和TTM算法性能对比图
Fig. 12 Performance contrastgures of TCM algorithm and TTM algorithm in Condmat network
图 13 时间窗口及三元组重要性指标对TCM算法的影响
Fig. 13 Influence of time window and the triad importance index to TCM method
表 1 实验数据集参数表
Table 1 Parameters of experimental data sets
Condmat Enron Facebook 节点数 17636 22 477 60 290 总边数 88 036 164 081 838 090 快招数 6 16 52 
下载: 导出CSV
表 2 Facebook数据集中各算法预测精度表
Table 2 Accuracy of different methods in Facebook network
PA HPLP TTM TS TCM AUC 0.52 0.76 0.79 0.83 0.84 AUPR 0.03 0.06 0.08 0.1 0.13
下载: 导出CSV
表 3 Enron数据集中各算法预测精度表
Table 3 Accuracy of different methods in Enron network
PA HPLP TTM TS TCM AUC 0.8 0.91 0.81 0.92 0.89 AUPR 0.04 0.17 0.21 0.23 0.30
下载: 导出CSV
表 4 Condmat数据集中各算法预测精度表
Table 4 Accuracy of different methods in Condmat network
PA HPLP TTM TS TCM AUC 0.59 0.68 0.76 0.81 0.92 AUPR 0.24 0.25 0.22 0.25 0.35
下载: 导出CSV
-
[1] 席裕庚. 大系统控制论与复杂网络——探索与思考. 自动化学报, 2013, 39(11): 1758-1768Xi Yu-Geng. Large-scale systems control and complex networks——exploration and thinking. Acta Automatica Sinica, 2013, 39(11): 1758-1768 [2] 陆浩, 王飞跃, 刘德荣, 张楠, 赵学亮. 基于科研知识图谱的近年国内外自动化学科发展综述. 自动化学报, 2014, 40(5): 994-1015Lu Hao, Wang Fei-Yue, Liu De-Rong, Zhang Nan, Zhao Xue-Liang. Analytics of lastest research progress in automation discipline based on academic knowledge mapping. Acta Automatica Sinica, 2014, 40(5): 994-1015 [3] Lv L, Medo M, Yeung C H, Zhang Y C, Zhang Z K, Zhou T. Recommender systems. Physics Reports, 2012, 519(1): 1-49 [4] Scellato S, Noulas A, Mascolo C. Exploiting place features in link prediction on location-based social networks. In: Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, USA: ACM, 2011. 1046-1054 [5] Wang D S, Pedreschi D, Song C M, Giannotti F, Barabasi A L. Human mobility, social ties, and link prediction. In: Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, USA: ACM, 2011. 1100-1108 [6] Mamitsuka H. Mining from protein-protein interactions. Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, 2012, 2(5): 400-410 [7] Huang Z, Lin D K J. The time-series link prediction problem with applications in communication surveillance. INFORMS Journal on Computing, 2009, 21(2): 286-303 [8] Bliss C A, Frank M R, Danforth C M, Dodds P S. An evolutionary algorithm approach to link prediction in dynamic social networks. Journal of Computational Science, 2014, 5(5): 750-764 [9] 邓志宏, 老松杨, 白亮. 基于预测误差修正的时序链路预测方法. 电子与信息学报, 2014, 36(2): 325-331Deng Zhi-Hong, Lao Song-Yang, Bai Liang. A temporal link prediction method based on link prediction error correction. Journal of Electronics and Information Technology, 2014, 36(2): 325-331 [10] Munasinghe L, Ichise R. Time score: a new feature for link prediction in social networks. IEICE Transactions on Information and Systems, 2012, E95-D(3): 821-828 [11] Zeng Z Z, Chen K J, Zhang S B, Zhang H J. A link prediction approach using semi-supervised learning in dynamic networks. In: Proceedings of the 6th International Conference on Advanced Computational Intelligence. Hangzhou, China: IEEE, 2013. 276-280 [12] Dunlavy D M, Kolda T G, Acar E. Temporal link prediction using matrix and tensor factorizations. ACM Transactions on Knowledge Discovery from Data, 2011, 5(2): Article No. 10 [13] Gao S, Denoyer L, Gallinari P. Temporal link prediction by integrating content and structure information. In: Proceedings of the 20th ACM International Conference on Information and Knowledge Management. Glasgow, UK: ACM, 2011. 1169-1174 [14] Milo R, Itzkovitz S, Kashtan N, Levitt R, Shen-Orr S, Ayzenshtat I, Sheffer M, Alon U. Superfamilies of evolved and designed networks. Science, 2004, 303(5663): 1538- 1542 [15] 陈关荣. 复杂动态网络环境下控制理论遇到的问题与挑战. 自动化学报, 2013, 39(4): 312-321Chen Guan-Rong. Problems and challenges in control theory under complex dynamical network environments Acta Automatica Sinica, 2013, 39(4): 312-321 [16] Juszczyszyn K, Musial K, Kazienko P, Gabrys B. Temporal changes in local topology of an email-based social network. Computing and Informatics, 2009, 28(6): 763-779 [17] Bringmann B, Berlingerio M, Bonchi F, Gionis A. Learning and predicting the evolution of social networks. IEEE Intelligent Systems, 2010, 25(4): 26-35 [18] Juszczyszyn K, Musial K, Budka M. Link prediction based on subgraph evolution in dynamic social networks. In: Proceedings of the 3rd IEEE International Conference on Social Computing, the 3rd IEEE International Conference on Privacy, Security, Risk and Trust. Boston, USA: IEEE, 2011. 27-34 [19] Rümmele N, Ichise R, Werthner H. Exploring supervised methods for temporal link prediction in heterogeneous social networks. In: Proceedings of the 24th International Conference on World Wide Web. Florence, Italy: International World Wide Web Conferences Steering Committee, 2015. 1363-1368 [20] Davis D, Lichtenwalter R, Chawla N V. Supervised methods for multi-relational link prediction. Social Network Analysis and Mining, 2013, 3(2): 127-141 [21] Microscopic evolution of social networks. In: Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Las Vegas, USA: ACM, 2008. 462-470 [22] Kolda T G, Bader B W. Tensor decompositions and applications. SIAM Review, 2009, 51(3): 455-500 [23] Signoretto M, Van de Plas R, De Moor B, Suykens J A K. Tensor versus matrix completion: a comparison with application to spectral data. IEEE Signal Processing Letters, 2011, 18(7): 403-406 [24] Leskovec J, Lang K J, Dasgupta A, Mahoney M W. Community structure in large networks: natural cluster sizes and the absence of large well-defined clusters. Internet Mathematics, 2009, 6(1): 29-123 [25] Viswanath B, Mislove A, Cha M, Gummadi K P. On the evolution of user interaction in Facebook. In: Proceedings of the 2nd ACM Workshop on Online Social Networks. Barcelona, Spain: ACM, 2009. 37-42 [26] Bader B W, Kolda T G. Efficient Matlab computations with sparse and factored tensors. SIAM Journal on Scientific Computing, 2007, 30(1): 205-231 [27] Chatfield C. The Analysis of Time Series: an Introduction (6th edition). Boca Raton: Chapman and Hall/CRC Press, 2013. 7-8 [28] Sharan U, Neville J. Temporal-relational classifiers for prediction in evolving domains. In: Proceedings of the 8th IEEE International Conference on Data Mining. Pisa, Italy: IEEE, 2008. 540-549 [29] Lichtenwalter R N, Lussier J T, Chawla N V. New perspectives and methods in link prediction. In: Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Washington DC, USA: ACM, 2010. 243-252 [30] 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 [31] Lichtnwalter R, Chawla N V. Link prediction: fair and effective evaluation. In: Proceedings of the 2012 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining. Istanbul, Turkey: IEEE, 2012. 376-383 -
计量
- 文章访问数: 1862
- HTML全文浏览量: 406
- PDF下载量: 1701
- 被引次数: 0
