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

Bounded link prediction in very large networks

Author

Listed:
  • Cui, Wei
  • Pu, Cunlai
  • Xu, Zhongqi
  • Cai, Shimin
  • Yang, Jian
  • Michaelson, Andrew

Abstract

Evaluating link prediction methods is a hard task in very large complex networks due to the prohibitive computational cost. However, if we consider the lower bound of node pairs’ similarity scores, this task can be greatly optimized. In this paper, we study CN index in the bounded link prediction framework, which is applicable to enormous heterogeneous networks. Specifically, we propose a fast algorithm based on the parallel computing scheme to obtain all node pairs with CN values larger than the lower bound. Furthermore, we propose a general measurement, called self-predictability, to quantify the performance of similarity indices in link prediction, which can also indicate the link predictability of networks with respect to given similarity indices.

Suggested Citation

  • Cui, Wei & Pu, Cunlai & Xu, Zhongqi & Cai, Shimin & Yang, Jian & Michaelson, Andrew, 2016. "Bounded link prediction in very large networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 457(C), pages 202-214.
    • Handle: RePEc:eee:phsmap:v:457:y:2016:i:c:p:202-214
    DOI: 10.1016/j.physa.2016.03.041
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0378437116300395
    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.03.041?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. Dorogovtsev, S. N. & Mendes, J.F.F., 2013. "Evolution of Networks: From Biological Nets to the Internet and WWW," OUP Catalogue, Oxford University Press, number 9780199686711.
    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. Yao Hongxing & Lu Yunxia, 2017. "Analyzing the Potential Influence of Shanghai Stock Market Based on Link Prediction Method," Journal of Systems Science and Information, De Gruyter, vol. 5(5), pages 446-461, October.
    2. Rafiee, Samira & Salavati, Chiman & Abdollahpouri, Alireza, 2020. "CNDP: Link prediction based on common neighbors degree penalization," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 539(C).
    3. 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).
    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. Saucan, Emil & Sreejith, R.P. & Vivek-Ananth, R.P. & Jost, Jürgen & Samal, Areejit, 2019. "Discrete Ricci curvatures for directed networks," Chaos, Solitons & Fractals, Elsevier, vol. 118(C), pages 347-360.
    2. Li, Xun & Cao, Lang, 2016. "Diffusion processes of fragmentary information on scale-free networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 450(C), pages 624-634.
    3. Kashin Sugishita & Yasuo Asakura, 2021. "Vulnerability studies in the fields of transportation and complex networks: a citation network analysis," Public Transport, Springer, vol. 13(1), pages 1-34, March.
    4. A. Paolo Masucci & Carlos Molinero, 2016. "Robustness and closeness centrality for self-organized and planned cities," The European Physical Journal B: Condensed Matter and Complex Systems, Springer;EDP Sciences, vol. 89(2), pages 1-8, February.
    5. Zhihong Tian & Zhenji Zhang & Ruize Gao, 2016. "Optimization in e-commerce market network based on value order parameter," Information Technology and Management, Springer, vol. 17(2), pages 187-197, June.
    6. Lei, Lixing & Yang, Junzhong, 2021. "Patterns in coupled FitzHugh–Nagumo model on duplex networks," Chaos, Solitons & Fractals, Elsevier, vol. 144(C).
    7. , David, 2016. "The formation of networks with local spillovers and limited observability," Theoretical Economics, Econometric Society, vol. 11(3), September.
    8. Hernández, Juan M. & González-Martel, Christian, 2017. "An evolving model for the lodging-service network in a tourism destination," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 482(C), pages 296-307.
    9. Neiva, Mariane B. & Bruno, Odemir M., 2023. "Exploring ordered patterns in the adjacency matrix for improving machine learning on complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 626(C).
    10. Nicanor García Álvarez & Belarmino Adenso-Díaz & Laura Calzada-Infante, 2021. "Maritime Traffic as a Complex Network: a Systematic Review," Networks and Spatial Economics, Springer, vol. 21(2), pages 387-417, June.
    11. Chih-Sheng Hsieh & Michael D. König & Xiaodong Liu, 2012. "Network formation with local complements and global substitutes: the case of R&D networks," ECON - Working Papers 217, Department of Economics - University of Zurich, revised Feb 2017.
    12. A. Paolo Masucci & Carlos Molinero, 2016. "Robustness and closeness centrality for self-organized and planned cities," The European Physical Journal B: Condensed Matter and Complex Systems, Springer;EDP Sciences, vol. 89(2), pages 1-8, February.
    13. Zhang, Ziqiao & Pu, Peng & Han, Dingding & Tang, Ming, 2018. "Self-adaptive Louvain algorithm: Fast and stable community detection algorithm based on the principle of small probability event," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 506(C), pages 975-986.
    14. Rybalova, E.V. & Strelkova, G.I. & Anishchenko, V.S., 2021. "Impact of sparse inter-layer coupling on the dynamics of a heterogeneous multilayer network of chaotic maps," Chaos, Solitons & Fractals, Elsevier, vol. 142(C).
    15. Gutiérrez, Caracé & Gancio, Juan & Cabeza, Cecilia & Rubido, Nicolás, 2021. "Finding the resistance distance and eigenvector centrality from the network’s eigenvalues," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 569(C).
    16. Pu, Cunlai & Li, Siyuan & Yang, Xianxia & Yang, Jian & Wang, Kai, 2016. "Information transport in multiplex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 447(C), pages 261-269.
    17. Ma, Liangliang & Liu, Jing & Duan, Boping, 2016. "Evolution of network robustness under continuous topological changes," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 451(C), pages 623-631.
    18. Lucas Cuadra & Sancho Salcedo-Sanz & Javier Del Ser & Silvia Jiménez-Fernández & Zong Woo Geem, 2015. "A Critical Review of Robustness in Power Grids Using Complex Networks Concepts," Energies, MDPI, vol. 8(9), pages 1-55, August.
    19. Havlin, Shlomo & Stanley, H. Eugene & Bashan, Amir & Gao, Jianxi & Kenett, Dror Y., 2015. "Percolation of interdependent network of networks," Chaos, Solitons & Fractals, Elsevier, vol. 72(C), pages 4-19.
    20. Fabio Vanni & Paolo Barucca, 2019. "Degree-correlations in a bursting dynamic network model," Journal of Economic Interaction and Coordination, Springer;Society for Economic Science with Heterogeneous Interacting Agents, vol. 14(3), pages 663-695, September.

    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:457:y:2016:i:c:p:202-214. 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.