2.765

2022影响因子

(CJCR)

  • 中文核心
  • EI
  • 中国科技核心
  • Scopus
  • CSCD
  • 英国科学文摘

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

基于模体演化的时序链路预测方法

王守辉 于洪涛 黄瑞阳 马青青

王守辉, 于洪涛, 黄瑞阳, 马青青. 基于模体演化的时序链路预测方法. 自动化学报, 2016, 42(5): 735-745. doi: 10.16383/j.aas.2016.c150526
引用本文: 王守辉, 于洪涛, 黄瑞阳, 马青青. 基于模体演化的时序链路预测方法. 自动化学报, 2016, 42(5): 735-745. doi: 10.16383/j.aas.2016.c150526
WANG Shou-Hui, YU Hong-Tao, HUANG Rui-Yang, MA Qing-Qing. A Temporal Link Prediction Method Based on Motif Evolution. ACTA AUTOMATICA SINICA, 2016, 42(5): 735-745. doi: 10.16383/j.aas.2016.c150526
Citation: WANG Shou-Hui, YU Hong-Tao, HUANG Rui-Yang, MA Qing-Qing. A Temporal Link Prediction Method Based on Motif Evolution. ACTA AUTOMATICA SINICA, 2016, 42(5): 735-745. doi: 10.16383/j.aas.2016.c150526

基于模体演化的时序链路预测方法

doi: 10.16383/j.aas.2016.c150526
基金项目: 

国家自然科学基金 61521003

详细信息
    作者简介:

    王守辉 国家数字交换系统工程技术研究中心硕士研究生. 主要研究方向为复杂网络链路预测. E-mail:huistudy@foxmail.com.

    黄瑞阳 国家数字交换系统工程技术研究中心助理研究员, 博士. 主要研究方向为网络大数据分析, 大图挖掘.E-mail:18337176095@139.com

    马青青 国家数字交换系统工程技术研究中心硕士研究生. 主要研究方向为社会网络分析.E-mail:qingqingma7@126.com

    通讯作者:

    于洪涛 国家数字交换系统工程技术研究中心研究员, 博士. 主要研究方向为网络大数据分析与处理. 本文通信作者. E-mail:15937101921@139.com.

A Temporal Link Prediction Method Based on Motif Evolution

Funds: 

National Natural Science Foundation of China 61521003

More Information
    Author Bio:

    Master student at the National Digital Switching System Engineering Technological Research Center. His research interestcovers link prediction on complex network.

    Ph. D., assistant professor at the National Digital Switching System Engineering Technological Research Center. His research interest covers network big data analysis and big graph mining.

    Master student at the National Digital Switching System Engineering Technological Research Center. Her research interest covers social network analysis.

    Corresponding author: YU Hong-Tao Ph. D., professor at the National Digital Switching System Engineering Technological Research Center. His research interest covers network big data analysis and processing. Corresponding author of this paper. E-mail:15937101921@139.com.
  • 摘要: 时序链路预测是动态网络分析的重要组成部分,具有极大的理论和应用价值. 传统的时序链路预测方法往往直接对边的演化规律进行分析,忽略了网络中其他微观结构的演化对链路形成的影响. 基于此分析,本文引入非负张量分解和时间序列分析对网络模体的演化规律进行研究,进而提出一种基于模体演化的链路预测方法. 在三个真实数据集上的实验结果表明,该方法能有效提高链路预测精度.
  • 图  1  无向网络三元组

    Fig.  1  Triads in undirected network

    图  2  CP分解模型

    Fig.  2  CP decomposition model

    图  3  Facebook网络TCM矩阵色谱图

    Fig.  3  Chromatogram of TCM matrix in Facebook network

    图  4  Enron网络TCM矩阵色谱图

    Fig.  4  Chromatogram of TCM matrix in Enron network

    图  5  Condmat网络TCM矩阵色谱图

    Fig.  5  Chromatogram of TCM matrix in Condmat network

    图  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

    图  8  三元组与节点对关系示意图

    Fig.  8  Diagram of the relationship of triad and node pair

    图  9  训练集与测试集选取方案

    Fig.  9  Selection scheme of training set and test set

    图  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

    CondmatEnronFacebook
    节点数1763622 47760 290
    总边数88 036164 081838 090
    快招数61652
    下载: 导出CSV

    表  2  Facebook数据集中各算法预测精度表

    Table  2  Accuracy of different methods in Facebook network

    PAHPLPTTMTSTCM
    AUC0.520.760.790.830.84
    AUPR0.030.060.080.10.13
    下载: 导出CSV

    表  3  Enron数据集中各算法预测精度表

    Table  3  Accuracy of different methods in Enron network

    PAHPLPTTMTSTCM
    AUC0.80.910.810.920.89
    AUPR0.040.170.210.230.30
    下载: 导出CSV

    表  4  Condmat数据集中各算法预测精度表

    Table  4  Accuracy of different methods in Condmat network

    PAHPLPTTMTSTCM
    AUC0.590.680.760.810.92
    AUPR0.240.250.220.250.35
    下载: 导出CSV
  • [1] 席裕庚. 大系统控制论与复杂网络——探索与思考. 自动化学报, 2013, 39(11): 1758-1768

    Xi 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-1015

    Lu 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-331

    Deng 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-321

    Chen 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
  • 加载中
图(13) / 表(4)
计量
  • 文章访问数:  1779
  • HTML全文浏览量:  390
  • PDF下载量:  1694
  • 被引次数: 0
出版历程
  • 收稿日期:  2015-08-19
  • 录用日期:  2015-11-26
  • 刊出日期:  2016-05-01

目录

    /

    返回文章
    返回