ISSN 0253-2778

CN 34-1054/N

Open AccessOpen Access JUSTC Original Paper

Link prediction in dynamical networks based on mutual information

Cite this:
https://doi.org/10.3969/j.issn.0253-2778.2018.06.002
  • Received Date: 27 June 2017
  • Accepted Date: 26 July 2017
  • Rev Recd Date: 26 July 2017
  • Publish Date: 30 June 2018
  • The critical issue of link prediction is to measure the existence probability of new links between nodes with the known node properties and observed structural features. The previous researches on complex network are conducted based on the oversimplified assumption that the network structure is static, while the temporal dimension has great impacts on structure and dynamic of real systems, which limits the performance of state-of-the-art methods. Inspired by this, we proposed moving average mutual information (MA_MI) algorithm that combines mutual information with moving average model. This method not only considers the information of common neighbors of nodes, but also describes the evolution pattern of network with historical information. Experimental results on four real-world networks show that MA_MI outperforms the traditional methods and achieves the higher precision.
    The critical issue of link prediction is to measure the existence probability of new links between nodes with the known node properties and observed structural features. The previous researches on complex network are conducted based on the oversimplified assumption that the network structure is static, while the temporal dimension has great impacts on structure and dynamic of real systems, which limits the performance of state-of-the-art methods. Inspired by this, we proposed moving average mutual information (MA_MI) algorithm that combines mutual information with moving average model. This method not only considers the information of common neighbors of nodes, but also describes the evolution pattern of network with historical information. Experimental results on four real-world networks show that MA_MI outperforms the traditional methods and achieves the higher precision.
  • loading
  • [1]
    ALBERT R, BARABSI A L. Statistical mechanics of complex networks[J]. Reviews of Modern Physics, 2002, 74(1): 47-51.
    [2]
    NEWMAN M E J. The structure and function of complex networks[J]. SIAM Review, 2003, 45(2): 167-256.
    [3]
    WANG P, XU B W, WU Y R, et al. Link prediction in social networks: The state-of-the-art[J]. Science China Information Sciences, 2015, 58(1): 1-38.
    [4]
    LEI C, RUAN J. A novel link prediction algorithm for reconstructing protein–protein interaction networks by topological similarity[J]. Bioinformatics, 2013, 29(3): 355-364.
    [5]
    LI X, CHEN H. Recommendation as link prediction in bipartite graphs: A graph kernel-based machine learning approach[J]. Decision Support Systems, 2013, 54(2): 880-890.
    [6]
    LICHTENWALTER R N, LUSSIER J T, CHAWLA N V. New perspectives and methods in link prediction[C]//Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, NY, USA : ACM, 2010: 243-252.
    [7]
    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.
    [8]
    BLISS C A, FRANK M R, DANFORTH C M, et al. An evolutionary algorithm approach to link prediction in dynamic social networks[J]. Journal of Computational Science, 2014, 5(5): 750-764.
    [9]
    WANG Xiaojie, ZHANG Xue, ZHAO Chengli, et al. Predicting link directions using local directed path[J]. Physica A: Statistical Mechanics and its Applications, 2015, 419: 260-267.
    [10]
    LIU W, L L. Link prediction based on local random walk[J]. EPL (Europhysics Letters), 2010, 89(5): 58007.
    [11]
    TAN F, XIA Y, ZHU B. Link prediction in complex networks: A mutual information perspective [J]. PloS ONE, 2014, 9(9): e107056.
    [12]
    XU Z, PU C, YANG J. Link prediction based on path entropy[J]. Physica A: Statistical Mechanics and its Applications, 2016, 456: 294-301.
    [13]
    ZHU B, XIA Y. Link prediction in weighted networks: A weighted mutual information model[J]. PloS ONE, 2016, 11(2): e0148265.
    [14]
    SARKAR P, CHAKRABARTI D, JORDAN M. Nonparametric link prediction in dynamic networks[EB/OL]. (2012-06-27)[2017-05-27]. https://arxiv.org/abs/1206.6394.
    [15]
    DUNLAVY D M, KOLDA T G, ACAR E. Temporal link prediction using matrix and tensor factorizations[J]. ACM Transactions on Knowledge Discovery from Data (TKDD), 2011, 5(2): 10.
    [16]
    HUANG Z, LIN D K J. The time-series link prediction problem with applications in communication surveillance[J]. INFORMS Journal on Computing,2008, 21(2): 286 – 303.
    [17]
    COVER T M, THOMAS J A. Elements of Information Theory[M]. Hoboken, New Jersey, USA: John Wiley & Sons, 2012.
    [18]
    DA SILVA SOARES P R, PRUDNCIO R B C. Time series based link prediction[C]// The 2012 International Joint Conference on Neural Networks (IJCNN). Piscataway, NY, USA: IEEE Press, 2012: 1-7.
    [19]
    HERLOCKER J L, KONSTAN J A, TERVEEN L G, et al. Evaluating collaborative filtering recommender systems[J]. ACM Transactions on Information Systems (TOIS), 2004, 22(1): 5-53.
    [20]
    JRME K. KONECT Datasets: The Koblenz Network Collection[EB/OL]. [2017-05-27]. http://konect.uni-koblenz.de.)
  • 加载中

Catalog

    [1]
    ALBERT R, BARABSI A L. Statistical mechanics of complex networks[J]. Reviews of Modern Physics, 2002, 74(1): 47-51.
    [2]
    NEWMAN M E J. The structure and function of complex networks[J]. SIAM Review, 2003, 45(2): 167-256.
    [3]
    WANG P, XU B W, WU Y R, et al. Link prediction in social networks: The state-of-the-art[J]. Science China Information Sciences, 2015, 58(1): 1-38.
    [4]
    LEI C, RUAN J. A novel link prediction algorithm for reconstructing protein–protein interaction networks by topological similarity[J]. Bioinformatics, 2013, 29(3): 355-364.
    [5]
    LI X, CHEN H. Recommendation as link prediction in bipartite graphs: A graph kernel-based machine learning approach[J]. Decision Support Systems, 2013, 54(2): 880-890.
    [6]
    LICHTENWALTER R N, LUSSIER J T, CHAWLA N V. New perspectives and methods in link prediction[C]//Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, NY, USA : ACM, 2010: 243-252.
    [7]
    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.
    [8]
    BLISS C A, FRANK M R, DANFORTH C M, et al. An evolutionary algorithm approach to link prediction in dynamic social networks[J]. Journal of Computational Science, 2014, 5(5): 750-764.
    [9]
    WANG Xiaojie, ZHANG Xue, ZHAO Chengli, et al. Predicting link directions using local directed path[J]. Physica A: Statistical Mechanics and its Applications, 2015, 419: 260-267.
    [10]
    LIU W, L L. Link prediction based on local random walk[J]. EPL (Europhysics Letters), 2010, 89(5): 58007.
    [11]
    TAN F, XIA Y, ZHU B. Link prediction in complex networks: A mutual information perspective [J]. PloS ONE, 2014, 9(9): e107056.
    [12]
    XU Z, PU C, YANG J. Link prediction based on path entropy[J]. Physica A: Statistical Mechanics and its Applications, 2016, 456: 294-301.
    [13]
    ZHU B, XIA Y. Link prediction in weighted networks: A weighted mutual information model[J]. PloS ONE, 2016, 11(2): e0148265.
    [14]
    SARKAR P, CHAKRABARTI D, JORDAN M. Nonparametric link prediction in dynamic networks[EB/OL]. (2012-06-27)[2017-05-27]. https://arxiv.org/abs/1206.6394.
    [15]
    DUNLAVY D M, KOLDA T G, ACAR E. Temporal link prediction using matrix and tensor factorizations[J]. ACM Transactions on Knowledge Discovery from Data (TKDD), 2011, 5(2): 10.
    [16]
    HUANG Z, LIN D K J. The time-series link prediction problem with applications in communication surveillance[J]. INFORMS Journal on Computing,2008, 21(2): 286 – 303.
    [17]
    COVER T M, THOMAS J A. Elements of Information Theory[M]. Hoboken, New Jersey, USA: John Wiley & Sons, 2012.
    [18]
    DA SILVA SOARES P R, PRUDNCIO R B C. Time series based link prediction[C]// The 2012 International Joint Conference on Neural Networks (IJCNN). Piscataway, NY, USA: IEEE Press, 2012: 1-7.
    [19]
    HERLOCKER J L, KONSTAN J A, TERVEEN L G, et al. Evaluating collaborative filtering recommender systems[J]. ACM Transactions on Information Systems (TOIS), 2004, 22(1): 5-53.
    [20]
    JRME K. KONECT Datasets: The Koblenz Network Collection[EB/OL]. [2017-05-27]. http://konect.uni-koblenz.de.)

    Article Metrics

    Article views (98) PDF downloads(410)
    Proportional views

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return