ISSN 0253-2778

CN 34-1054/N

open
Free to Publish. Free to Read.
Open AccessOpen Access JUSTC Original Paper

Link prediction in dynamical networks based on mutual information

  • 1.

    Department of Electronic Science and Technology, University of Science and Technology of China, Hefei 230027, China

  • 2.

    Guangdong Province Key Laboratory of Popular High Performance Computers, College of Computer Science and Software Engineering,Shenzhen University,Shenzhen 518060, China

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
    Abstract

  • Abstract

    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.

    Abstract

    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.
    • FullText(HTML)
  • loading
    • References(20)
  • [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.)
    • Supplements(0)
    • Related Articles
    • Track Citations
  • 加载中

Catalog

    |
    Get Citation
    PDF
    XML
    [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.)
    Recommended articles
    TrendMD
    Volume 48 Issue 6 page: 440-446
    Cover

    Article Metrics

    Article views (62) PDF downloads(114)
    Proportional views

    Copyright © Editorial Office of JUSTC, All Rights Reserved. 皖ICP备05002528号

    Supported by: Beijing Renhe Information Technology Co. Ltd    

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return