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

Link direction for link prediction

Author

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

Abstract

Almost all previous studies on link prediction have focused on using the properties of the network to predict the existence of links between pairs of nodes. Unfortunately, previous methods rarely consider the role of link direction for link prediction. In fact, many real-world complex networks are directed and ignoring the link direction will mean overlooking important information. In this study, we propose a phase-dynamic algorithm of the directed network nodes to analyse the role of link directions and demonstrate that the bi-directional links and the one-directional links have different roles in link prediction and network structure formation. From this, we propose new directional prediction methods and use six real networks to test our algorithms. In real networks, we find that compared to a pair of nodes which are connected by a one-directional link, a pair of nodes which are connected by a bi-directional link always have higher probabilities to connect to the common neighbours with only bi-directional links (or conversely by one-directional links). We suggest that, in the real networks, the bi-directional links will generally be more informative for link prediction and network structure formation. In addition, we propose a new directional randomized algorithm to demonstrate that the direction of the links plays a significant role in link prediction and network structure formation.

Suggested Citation

  • 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.
    • Handle: RePEc:eee:phsmap:v:469:y:2017:i:c:p:767-776
    DOI: 10.1016/j.physa.2016.11.129
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0378437116309530
    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.11.129?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. Réka Albert & Hawoong Jeong & Albert-László Barabási, 1999. "Diameter of the World-Wide Web," Nature, Nature, vol. 401(6749), pages 130-131, September.
    2. 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.
    3. Shin-ya Takemura & Arjun Bharioke & Zhiyuan Lu & Aljoscha Nern & Shiv Vitaladevuni & Patricia K. Rivlin & William T. Katz & Donald J. Olbris & Stephen M. Plaza & Philip Winston & Ting Zhao & Jane Anne, 2013. "A visual motion detection circuit suggested by Drosophila connectomics," Nature, Nature, vol. 500(7461), pages 175-181, August.
    4. 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.
    5. Liu, Yangyang & Zhao, Chengli & Wang, Xiaojie & Huang, Qiangjuan & Zhang, Xue & Yi, Dongyun, 2016. "The degree-related clustering coefficient and its application to link prediction," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 454(C), pages 24-33.
    6. Davi D. Bock & Wei-Chung Allen Lee & Aaron M. Kerlin & Mark L. Andermann & Greg Hood & Arthur W. Wetzel & Sergey Yurgenson & Edward R. Soucy & Hyon Suk Kim & R. Clay Reid, 2011. "Network anatomy and in vivo physiology of visual cortical neurons," Nature, Nature, vol. 471(7337), pages 177-182, March.
    7. 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. 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.
    2. Bütün, Ertan & Kaya, Mehmet, 2019. "A pattern based supervised link prediction in directed complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 525(C), pages 1136-1145.
    3. Aghabozorgi, Farshad & Khayyambashi, Mohammad Reza, 2018. "A new similarity measure for link prediction based on local structures in social networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 501(C), pages 12-23.
    4. 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.

    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. 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.
    2. 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.
    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. Anton Kocheturov & Panos M. Pardalos & Athanasia Karakitsiou, 2019. "Massive datasets and machine learning for computational biomedicine: trends and challenges," Annals of Operations Research, Springer, vol. 276(1), pages 5-34, May.
    5. Kumar, Ajay & Singh, Shashank Sheshar & Singh, Kuldeep & Biswas, Bhaskar, 2020. "Link prediction techniques, applications, and performance: A survey," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 553(C).
    6. 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.
    7. 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.
    8. 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.
    9. 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.
    10. Kumar, Ajay & Mishra, Shivansh & Singh, Shashank Sheshar & Singh, Kuldeep & Biswas, Bhaskar, 2020. "Link prediction in complex networks based on Significance of Higher-Order Path Index (SHOPI)," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 545(C).
    11. Emöke-Ágnes Horvát & Michael Hanselmann & Fred A Hamprecht & Katharina A Zweig, 2012. "One Plus One Makes Three (for Social Networks)," PLOS ONE, Public Library of Science, vol. 7(4), pages 1-8, April.
    12. Mohd-Zaid, Fairul & Kabban, Christine M. Schubert & Deckro, Richard F. & White, Edward D., 2017. "Parameter specification for the degree distribution of simulated Barabási–Albert graphs," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 465(C), pages 141-152.
    13. He, He & Yang, Bo & Hu, Xiaoming, 2016. "Exploring community structure in networks by consensus dynamics," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 450(C), pages 342-353.
    14. Ding, Ying, 2011. "Community detection: Topological vs. topical," Journal of Informetrics, Elsevier, vol. 5(4), pages 498-514.
    15. Elias Carroni & Paolo Pin & Simone Righi, 2020. "Bring a Friend! Privately or Publicly?," Management Science, INFORMS, vol. 66(5), pages 2269-2290, May.
    16. Gräbner, Claudius, 2016. "From realism to instrumentalism - and back? Methodological implications of changes in the epistemology of economics," MPRA Paper 71933, University Library of Munich, Germany.
    17. Duan, Shuyu & Wen, Tao & Jiang, Wen, 2019. "A new information dimension of complex network based on Rényi entropy," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 516(C), pages 529-542.
    18. Tamás Nepusz & Tamás Vicsek, 2013. "Hierarchical Self-Organization of Non-Cooperating Individuals," PLOS ONE, Public Library of Science, vol. 8(12), pages 1-9, December.
    19. Baek, Seung Ki & Kim, Tae Young & Kim, Beom Jun, 2008. "Testing a priority-based queue model with Linux command histories," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 387(14), pages 3660-3668.
    20. Freddy Hernán Cepeda López, 2008. "La topología de redes como herramienta de seguimiento en el Sistema de Pagos de Alto Valor en Colombia," Borradores de Economia 513, Banco de la Republica de Colombia.

    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:469:y:2017:i:c:p:767-776. 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.