Empirical comparison of network sampling techniques

Neli Blagus, Lovro Šubelj, Marko Bajec · arXiv.org · 2015

Summary

This paper applies subgraph induction also to random walk and forest-fire sampling, and reveals that the techniques with sub graph induction underestimate the degree and clustering distribution, while overestimate average degree and density of the original networks.

Type: preprint
Published: 2015-06-08
Cited by: 8
References: 28
Access: Open access
DOI: https://doi.org/10.48550/arxiv.1506.02449
arXiv: https://arxiv.org/abs/1506.02449
OpenAlex: https://openalex.org/W829117785
Semantic Scholar: https://api.semanticscholar.org/CorpusID:7372010

Keywords

Sampling (signal processing), Selection (genetic algorithm), Computer science, Cluster analysis, Degree (music)

References

Reconsidering the Foundations of Network SamplingNesreen K. Ahmed, Jennifer Neville, Ramana Rao Kompella — 2010
Random Walks on Graphs: A SurveyLászló Lovász — 2001
Network Sampling via Edge-based Node Selection with Graph InductionNesreen K. Ahmed, Jennifer Neville, Ramana Rao Kompella — 2011
On the bias of BFSMaciej Kurant, Athina Markopoulou, Patrick Thiran — 2010
A new algorithm for extracting a small representative subgraph from a very large graphHarish Sethu, Xiaoyu Chu — 2012
A Survey and Taxonomy of Graph SamplingPili Hu, Hong, Seok-Hee, Jing, Yongcheng — 2013
Network Sampling: From Static to Streaming GraphsNesreen K. Ahmed, Jennifer Neville, Ramana Rao Kompella — 2012
Self-similar scaling of density in complex real-world networksNeli Blagus, Lovro Šubelj, Marko Bajec — 2011
Defining and evaluating network communities based on ground-truthJaewon Yang, Jure Leskovec — 2012
Statistical properties of sampled networks.Sang Hoon Lee, Pan‐Jun Kim, Hawoong Jeong — 2005
Benefits of bias: towards better characterization of network samplingArun S. Maiya, Tanya Berger‐Wolf — 2011
Subnets of scale-free networks are not scale-free: sampling properties of networks.Michael P. H. Stumpf, Carsten Wiuf, Robert M. May — 2005
Community-Affiliation Graph Model for Overlapping Network Community DetectionJaewon Yang, Jure Leskovec — 2012
Metric convergence in social network samplingChristian Doerr, Norbert Blenn — 2013
Graph evolution: Densification and shrinking diametersJure Leskovec, Jon Kleinberg, Christos Faloutsos — 2006
Friendship and mobility: user movement in location-based social networksEunjoon Cho, Seth A. Myers, Jure Leskovec — 2011
Collective dynamics of ‘small-world’ networksDuncan J. Watts, Steven H. Strogatz — 1998
Sampling promotes community structure in social and information networksNeli Blagus, Lovro Šubelj, Gregor Weiß — 2015
Assessing the effectiveness of real-world network simplificationNeli Blagus, Lovro Šubelj, Marko Bajec — 2014
Sampling from large graphsJure Leskovec, Christos Faloutsos — 2006

Cited by

Epidemic risk from friendship network data: an equivalence with a non-uniform sampling of contact networksJulie Fournet, Alain Barrat — 2016
Impact of spatially constrained sampling of temporal contact networks on the evaluation of the epidemic riskChristian L. Vestergaard, Eugenio Valdano, Mathieu Génois — 2016
Evaluation of Graph Sampling: A Visualization PerspectiveYanhong Wu, Nan Cao, Daniel Archambault — 2017
Network reconstruction via density samplingTiziano Squartini, Giulio Cimini, Andrea Gabrielli — 2016
List sampling for large graphsMuhammad Irfan Yousuf, Suhyun Kim — 2018
Reconstruction methods for networks: The case of economic and financial systemsTiziano Squartini, Guido Caldarelli, Giulio Cimini — 2018
Benchmarking API Costs of Network Sampling StrategiesMichele Coscia, Luca Rossi — 2018
Evaluating graph neural networks under graph sampling scenariosQiang Wei, Guangmin Hu — 2022

Empirical comparison of network sampling techniques

Summary

Keywords

References

Cited by

Related papers