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

Sampling social networks using shortest paths

Author

Listed:
  • Rezvanian, Alireza
  • Meybodi, Mohammad Reza

Abstract

In recent years, online social networks (OSN) have emerged as a platform of sharing variety of information about people, and their interests, activities, events and news from real worlds. Due to the large scale and access limitations (e.g., privacy policies) of online social network services such as Facebook and Twitter, it is difficult to access the whole public network in a limited amount of time. For this reason researchers try to study and characterize OSN by taking appropriate and reliable samples from the network. In this paper, we propose to use the concept of shortest path for sampling social networks. The proposed sampling method first finds the shortest paths between several pairs of nodes selected according to some criteria. Then the edges in these shortest paths are ranked according to the number of times that each edge has appeared in the set of found shortest paths. The sampled network is then computed as a subgraph of the social network which contains a percentage of highly ranked edges. In order to investigate the performance of the proposed sampling method, we provide a number of experiments on synthetic and real networks. Experimental results show that the proposed sampling method outperforms the existing method such as random edge sampling, random node sampling, random walk sampling and Metropolis–Hastings random walk sampling in terms of relative error (RE), normalized root mean square error (NMSE), and Kolmogorov–Smirnov (KS) test.

Suggested Citation

  • Rezvanian, Alireza & Meybodi, Mohammad Reza, 2015. "Sampling social networks using shortest paths," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 424(C), pages 254-268.
  • Handle: RePEc:eee:phsmap:v:424:y:2015:i:c:p:254-268
    DOI: 10.1016/j.physa.2015.01.030
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0378437115000321
    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.2015.01.030?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. Pablo M. Gleiser & Leon Danon, 2003. "Community Structure In Jazz," Advances in Complex Systems (ACS), World Scientific Publishing Co. Pte. Ltd., vol. 6(04), pages 565-573.
    2. Qi Gao & Xintong Ding & Feng Pan & Weixing Li, 2014. "An improved sampling method of complex network," International Journal of Modern Physics C (IJMPC), World Scientific Publishing Co. Pte. Ltd., vol. 25(05), pages 1-11.
    3. M. Goldstein & S. Morris & G. Yen, 2004. "Problems with fitting to the power-law distribution," The European Physical Journal B: Condensed Matter and Complex Systems, Springer;EDP Sciences, vol. 41(2), pages 255-258, September.
    4. Rezvanian, Alireza & Rahmati, Mohammad & Meybodi, Mohammad Reza, 2014. "Sampling from complex networks using distributed learning automata," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 396(C), pages 224-234.
    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. Gillespie, Colin S., 2015. "Fitting Heavy Tailed Distributions: The poweRlaw Package," Journal of Statistical Software, Foundation for Open Access Statistics, vol. 64(i02).
    2. Zhang, Wen-Yao & Wei, Zong-Wen & Wang, Bing-Hong & Han, Xiao-Pu, 2016. "Measuring mixing patterns in complex networks by Spearman rank correlation coefficient," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 451(C), pages 440-450.
    3. Fenner, Trevor & Levene, Mark & Loizou, George, 2010. "Predicting the long tail of book sales: Unearthing the power-law exponent," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 389(12), pages 2416-2421.
    4. Zhang, Yun & Liu, Yongguo & Li, Jieting & Zhu, Jiajing & Yang, Changhong & Yang, Wen & Wen, Chuanbiao, 2020. "WOCDA: A whale optimization based community detection algorithm," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 539(C).
    5. Kong, Hanzhang & Kang, Qinma & Li, Wenquan & Liu, Chao & Kang, Yunfan & He, Hong, 2019. "A hybrid iterated carousel greedy algorithm for community detection in complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 536(C).
    6. Rafael González-Val, 2012. "A Nonparametric Estimation of the Local Zipf Exponent for all US Cities," Environment and Planning B, , vol. 39(6), pages 1119-1130, December.
    7. Yuan, Quan & Liu, Binghui, 2021. "Community detection via an efficient nonconvex optimization approach based on modularity," Computational Statistics & Data Analysis, Elsevier, vol. 157(C).
    8. Xinyu Huang & Dongming Chen & Dongqi Wang & Tao Ren, 2020. "MINE: Identifying Top- k Vital Nodes in Complex Networks via Maximum Influential Neighbors Expansion," Mathematics, MDPI, vol. 8(9), pages 1-25, August.
    9. Fatemi, Samira & Salehi, Mostafa & Veisi, Hadi & Jalili, Mahdi, 2018. "A fuzzy logic based estimator for respondent driven sampling of complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 510(C), pages 42-51.
    10. Rafael González-Val, 2021. "The Probability Distribution of Worldwide Forest Areas," Sustainability, MDPI, vol. 13(3), pages 1-19, January.
    11. Zhao, Shuying & Sun, Shaowei, 2023. "Identification of node centrality based on Laplacian energy of networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 609(C).
    12. Rafael González‐Val, 2019. "Historical urban growth in Europe (1300–1800)," Papers in Regional Science, Wiley Blackwell, vol. 98(2), pages 1115-1136, April.
    13. Zhe Li & Xinyu Huang, 2023. "Identifying Influential Spreaders Using Local Information," Mathematics, MDPI, vol. 11(6), pages 1-14, March.
    14. Marcus Berliant & Hiroki Watanabe, 2015. "Explaining the size distribution of cities: Extreme economies," Quantitative Economics, Econometric Society, vol. 6(1), pages 153-187, March.
    15. Tomson Ogwang, 2011. "Power laws in top wealth distributions: evidence from Canada," Empirical Economics, Springer, vol. 41(2), pages 473-486, October.
    16. Klabunde, Anna, 2014. "Computational Economic Modeling of Migration," Ruhr Economic Papers 471, RWI - Leibniz-Institut für Wirtschaftsforschung, Ruhr-University Bochum, TU Dortmund University, University of Duisburg-Essen.
    17. Ogwang, Tomson, 2013. "Is the wealth of the world’s billionaires Paretian?," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 392(4), pages 757-762.
    18. Fenner, Trevor & Levene, Mark & Loizou, George, 2005. "A stochastic evolutionary model exhibiting power-law behaviour with an exponential cutoff," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 355(2), pages 641-656.
    19. Liu, X. & Murata, T., 2010. "Advanced modularity-specialized label propagation algorithm for detecting communities in networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 389(7), pages 1493-1500.
    20. 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.

    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:424:y:2015:i:c:p:254-268. 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.