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

Empirical comparison of network sampling: How to choose the most appropriate method?

Author

Listed:
  • Blagus, Neli
  • Šubelj, Lovro
  • Bajec, Marko

Abstract

In the past few years, the storage and the analysis of large-scale and fast evolving networks presents a great challenge. Therefore, a number of different techniques have been proposed for sampling large networks. Studies on network sampling primarily analyze the changes of network properties under the sampling. In general, network exploration techniques approximate the original networks more accurate than random node and link selection. Yet, link selection with additional subgraph induction step outperforms most other techniques. In this paper, we apply subgraph induction also to random walk and forest-fire sampling and evaluate the effects of subgraph induction on the sampling accuracy. We analyze different real-world networks and the changes of their properties introduced by sampling. The results reveal that the techniques with subgraph induction improve the performance of techniques without induction and create denser sample networks with larger average degree. Furthermore, the accuracy of sampling decrease consistently across various sampling techniques, when the sampled networks are smaller. Based on the results of the comparison, we introduce the scheme for selecting the most appropriate technique for network sampling. Overall, the breadth-first exploration sampling proves as the best performing technique.

Suggested Citation

  • Blagus, Neli & Šubelj, Lovro & Bajec, Marko, 2017. "Empirical comparison of network sampling: How to choose the most appropriate method?," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 477(C), pages 136-148.
    • Handle: RePEc:eee:phsmap:v:477:y:2017:i:c:p:136-148
    DOI: 10.1016/j.physa.2017.02.048
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0378437117301681
    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.2017.02.048?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. 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.
    2. Blagus, Neli & Šubelj, Lovro & Bajec, Marko, 2012. "Self-similar scaling of density in complex real-world networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 391(8), pages 2794-2802.
    3. Blagus, Neli & Šubelj, Lovro & Bajec, Marko, 2014. "Assessing the effectiveness of real-world network simplification," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 413(C), pages 134-146.
    4. Blagus, Neli & Šubelj, Lovro & Weiss, Gregor & Bajec, Marko, 2015. "Sampling promotes community structure in social and information networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 432(C), pages 206-215.
    Full references (including those not matched with items on IDEAS)

    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. Wang, Jing & Ma, Xiao-Jing & Xiang, Bing-Bing & Bao, Zhong-Kui & Zhang, Hai-Feng, 2022. "Maximizing influence in social networks by distinguishing the roles of seeds," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 604(C).
    2. Chen, Ling-Jiao & Zhang, Zi-Ke & Liu, Jin-Hu & Gao, Jian & Zhou, Tao, 2017. "A vertex similarity index for better personalized recommendation," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 466(C), pages 607-615.
    3. Jiang, Lincheng & Zhao, Xiang & Ge, Bin & Xiao, Weidong & Ruan, Yirun, 2019. "An efficient algorithm for mining a set of influential spreaders in complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 516(C), pages 58-65.
    4. Dong-Rui Chen & Chuang Liu & Yi-Cheng Zhang & Zi-Ke Zhang, 2019. "Predicting Financial Extremes Based on Weighted Visual Graph of Major Stock Indices," Complexity, Hindawi, vol. 2019, pages 1-17, October.
    5. Wei, Daijun & Deng, Xinyang & Zhang, Xiaoge & Deng, Yong & Mahadevan, Sankaran, 2013. "Identifying influential nodes in weighted networks based on evidence theory," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 392(10), pages 2564-2575.
    6. Weihua Lei & Luiz G. A. Alves & Luís A. Nunes Amaral, 2022. "Forecasting the evolution of fast-changing transportation networks using machine learning," Nature Communications, Nature, vol. 13(1), pages 1-12, December.
    7. 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.
    8. 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).
    9. Dai, Liang & Derudder, Ben & Liu, Xingjian, 2018. "Transport network backbone extraction: A comparison of techniques," Journal of Transport Geography, Elsevier, vol. 69(C), pages 271-281.
    10. Linyuan Lü & Yi-Cheng Zhang & Chi Ho Yeung & Tao Zhou, 2011. "Leaders in Social Networks, the Delicious Case," PLOS ONE, Public Library of Science, vol. 6(6), pages 1-9, June.
    11. Yin, Liang & Shi, Li-Chen & Zhao, Jun-Yan & Du, Song-Yang & Xie, Wen-Bo & Yuan, Fei & Chen, Duan-Bing, 2018. "Heterogeneous information network model for equipment-standard system," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 490(C), pages 935-943.
    12. 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.
    13. Kart, Ozge & Ulucay, Oguzhan & Bingol, Berkay & Isik, Zerrin, 2020. "A machine learning-based recommendation model for bipartite networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 553(C).
    14. Alireza Abbasi & Mahdi Jalili & Abolghasem Sadeghi-Niaraki, 2018. "Influence of network-based structural and power diversity on research performance," Scientometrics, Springer;Akadémiai Kiadó, vol. 117(1), pages 579-590, October.
    15. Lee, Yan-Li & Zhou, Tao, 2021. "Collaborative filtering approach to link prediction," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 578(C).
    16. Moradabadi, Behnaz & Meybodi, Mohammad Reza, 2016. "Link prediction based on temporal similarity metrics using continuous action set learning automata," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 460(C), pages 361-373.
    17. Jiang, Yawen & Jia, Caiyan & Yu, Jian, 2013. "An efficient community detection method based on rank centrality," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 392(9), pages 2182-2194.
    18. Park, Mingyu & Geum, Youngjung, 2022. "Two-stage technology opportunity discovery for firm-level decision making: GCN-based link-prediction approach," Technological Forecasting and Social Change, Elsevier, vol. 183(C).
    19. Yichi Zhang & Zhiliang Dong & Sen Liu & Peixiang Jiang & Cuizhi Zhang & Chao Ding, 2021. "Forecast of International Trade of Lithium Carbonate Products in Importing Countries and Small-Scale Exporting Countries," Sustainability, MDPI, vol. 13(3), pages 1-23, January.
    20. 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.

    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:477:y:2017:i:c:p:136-148. 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.