IDEAS home Printed from https://ideas.repec.org/a/eee/phsmap/v455y2016icp120-135.html
   My bibliography  Save this article

Evolving networks—Using past structure to predict the future

Author

Listed:
  • Shang, Ke-ke
  • Yan, Wei-sheng
  • Small, Michael

Abstract

Many previous studies on link prediction have focused on using common neighbors to predict the existence of links between pairs of nodes. More broadly, research into the structural properties of evolving temporal networks and temporal link prediction methods have recently attracted increasing attention. In this study, for the first time, we examine the use of links between a pair of nodes to predict their common neighbors and analyze the relationship between the weight and the structure in static networks, evolving networks, and in the corresponding randomized networks. We propose both new unweighted and weighted prediction methods and use six kinds of real networks to test our algorithms. In unweighted networks, we find that if a pair of nodes connect to each other in the current network, they will have a higher probability to connect common nodes both in the current and the future networks—and the probability will decrease with the increase of the number of neighbors. Furthermore, we find that the original networks have their particular structure and statistical characteristics which benefit link prediction. In weighted networks, the prediction algorithm performance of networks which are dominated by human factors decrease with the decrease of weight and are in general better in static networks. Furthermore, we find that geographical position and link weight both have significant influence on the transport network. Moreover, the evolving financial network has the lowest predictability. In addition, we find that the structure of non-social networks has more robustness than social networks. The structure of engineering networks has both best predictability and also robustness.

Suggested Citation

  • Shang, Ke-ke & Yan, Wei-sheng & Small, Michael, 2016. "Evolving networks—Using past structure to predict the future," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 455(C), pages 120-135.
  • Handle: RePEc:eee:phsmap:v:455:y:2016:i:c:p:120-135
    DOI: 10.1016/j.physa.2016.02.067
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0378437116002454
    Download Restriction: Full text for ScienceDirect subscribers only. Journal offers the option of making the article available online on Science direct for a fee of $3,000

    File URL: https://libkey.io/10.1016/j.physa.2016.02.067?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Ke-Ke Shang & Wei-Sheng Yan & Xiao-Ke Xu, 2014. "Limitation of degree information for analyzing the interaction evolution in online social networks," International Journal of Modern Physics C (IJMPC), World Scientific Publishing Co. Pte. Ltd., vol. 25(10), pages 1-10.
    2. Aaron Clauset & Cristopher Moore & M. E. J. Newman, 2008. "Hierarchical structure and the prediction of missing links in networks," Nature, Nature, vol. 453(7191), pages 98-101, May.
    3. Lü, Linyuan & Zhou, Tao, 2011. "Link prediction in complex networks: A survey," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 390(6), pages 1150-1170.
    4. Sid Redner, 2008. "Teasing out the missing links," Nature, Nature, vol. 453(7191), pages 47-48, May.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Shang, Ke-ke & Small, Michael & Yan, Wei-sheng, 2017. "Link direction for link prediction," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 469(C), pages 767-776.
    2. Charakopoulos, A.K. & Katsouli, G.A. & Karakasidis, T.E., 2018. "Dynamics and causalities of atmospheric and oceanic data identified by complex networks and Granger causality analysis," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 495(C), pages 436-453.
    3. Yin, Likang & Deng, Yong, 2018. "Toward uncertainty of weighted networks: An entropy-based model," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 508(C), pages 176-186.
    4. Charikhi, Mourad, 2024. "Association of the PageRank algorithm with similarity-based methods for link prediction in complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 637(C).
    5. Shang, Ke-ke & Small, Michael & Yan, Wei-sheng, 2017. "Fitness networks for real world systems via modified preferential attachment," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 474(C), pages 49-60.
    6. Jiang, Zhongyuan & Tang, Xiaoke & Zeng, Yong & Li, Jinku & Ma, Jianfeng, 2021. "Adversarial link deception against the link prediction in complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 577(C).
    7. Yin, Likang & Zheng, Haoyang & Bian, Tian & Deng, Yong, 2017. "An evidential link prediction method and link predictability based on Shannon entropy," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 482(C), pages 699-712.
    8. Zhang, Cheng-Jun & Zhu, Xue-lian & Yu, Wen-bin & Liu, Jin & Chen, Ya-dang & Yao, Yu & Wang, Su-xun, 2024. "Predicting popularity of online products via collective recommendations," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 641(C).
    9. Zhao, Liming & Zhang, Haihong & Wu, Wenqing, 2017. "Knowledge service decision making in business incubators based on the supernetwork model," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 479(C), pages 249-264.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Mingyu Nan & Yifan Zhu & Jie Zhang & Tao Wang & Xin Zhou, 2022. "MSGWO-MKL-SVM: A Missing Link Prediction Method for UAV Swarm Network Based on Time Series," Mathematics, MDPI, vol. 10(14), pages 1-29, July.
    2. Liao, Hao & Zeng, An & Zhang, Yi-Cheng, 2015. "Predicting missing links via correlation between nodes," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 436(C), pages 216-223.
    3. Liu, Chuang & Zhou, Wei-Xing, 2012. "Heterogeneity in initial resource configurations improves a network-based hybrid recommendation algorithm," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 391(22), pages 5704-5711.
    4. Xia, Yongxiang & Pang, Wenbo & Zhang, Xuejun, 2021. "Mining relationships between performance of link prediction algorithms and network structure," Chaos, Solitons & Fractals, Elsevier, vol. 153(P2).
    5. Aslan, Serpil & Kaya, Buket & Kaya, Mehmet, 2019. "Predicting potential links by using strengthened projections in evolving bipartite networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 525(C), pages 998-1011.
    6. Leto Peel & Tiago P. Peixoto & Manlio De Domenico, 2022. "Statistical inference links data and theory in network science," Nature Communications, Nature, vol. 13(1), pages 1-15, December.
    7. Wang, Zuxi & Wu, Yao & Li, Qingguang & Jin, Fengdong & Xiong, Wei, 2016. "Link prediction based on hyperbolic mapping with community structure for complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 450(C), pages 609-623.
    8. Lee, Yan-Li & Zhou, Tao, 2021. "Collaborative filtering approach to link prediction," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 578(C).
    9. Shang, Ke-ke & Small, Michael & Yan, Wei-sheng, 2017. "Link direction for link prediction," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 469(C), pages 767-776.
    10. Peng Liu & Liang Gui & Huirong Wang & Muhammad Riaz, 2022. "A Two-Stage Deep-Learning Model for Link Prediction Based on Network Structure and Node Attributes," Sustainability, MDPI, vol. 14(23), pages 1-15, December.
    11. Yao, Can-Zhong & Lin, Ji-Nan & Zheng, Xu-Zhou & Liu, Xiao-Feng, 2015. "The study of RMB exchange rate complex networks based on fluctuation mode," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 436(C), pages 359-376.
    12. Liu, Zhenfeng & Feng, Jian & Uden, Lorna, 2023. "Technology opportunity analysis using hierarchical semantic networks and dual link prediction," Technovation, Elsevier, vol. 128(C).
    13. Zhang, Xue & Wang, Xiaojie & Zhao, Chengli & Yi, Dongyun & Xie, Zheng, 2014. "Degree-corrected stochastic block models and reliability in networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 393(C), pages 553-559.
    14. Chi, Kuo & Qu, Hui & Yin, Guisheng, 2022. "Link prediction for existing links in dynamic networks based on the attraction force," Chaos, Solitons & Fractals, Elsevier, vol. 159(C).
    15. Yin, Likang & Deng, Yong, 2018. "Measuring transferring similarity via local information," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 498(C), pages 102-115.
    16. Lü, Linyuan & Zhou, Tao, 2011. "Link prediction in complex networks: A survey," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 390(6), pages 1150-1170.
    17. Zhou, Tao & Lee, Yan-Li & Wang, Guannan, 2021. "Experimental analyses on 2-hop-based and 3-hop-based link prediction algorithms," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 564(C).
    18. Shang, Ke-ke & Small, Michael & Yan, Wei-sheng, 2017. "Fitness networks for real world systems via modified preferential attachment," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 474(C), pages 49-60.
    19. Wang, Xiaojie & Zhang, Xue & Zhao, Chengli & Xie, Zheng & Zhang, Shengjun & Yi, Dongyun, 2015. "Predicting link directions using local directed path," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 419(C), pages 260-267.
    20. Guan, Qing & An, Haizhong & Gao, Xiangyun & Huang, Shupei & Li, Huajiao, 2016. "Estimating potential trade links in the international crude oil trade: A link prediction approach," Energy, Elsevier, vol. 102(C), pages 406-415.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:phsmap:v:455:y:2016:i:c:p:120-135. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.journals.elsevier.com/physica-a-statistical-mechpplications/ .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.