Reconsidering the Foundations of Network Sampling
Published 1 January 2010
Nesreen K. Ahmed, Jennifer Neville, Ramana Rao Kompella
Citations32
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This paper reconsider the foundations of network sampling and attempt to formalize the goals, and process of, sampling, in order to frame future development and analysis of sampling algorithms.
Abstract
Recently, there has been a great deal of research focusing on the development of sampling algorithms for networks with small-world and/or power-law structure. The peer-to-peer research community (e.g., [7]) have used sampling
Keywords
Computer SciencePhysics and Astronomy
Sampling from large graphs
1,192 Citations2006Jure Leskovec, Christos Faloutsos
The best performing methods are the ones based on random-walks and "forest fire"; they match very accurately both static as well as evolutionary graph patterns, with sample sizes down to about 15% of the original graph.
Analysis of topological characteristics of huge online social networking services
950 Citations2007Yong‐Yeol Ahn, Seungyeop Han +3 more
Cyworld, MySpace, and orkut, each with more than 10 million users, are compared and it is shown that they deviate from close-knit online social networks which show a similar degree correlation pattern to real-life social networks.
Proceedings of the National Academy of SciencesSubnets of scale-free networks are not scale-free: Sampling properties of networks
573 Citations2005Michael P. H. Stumpf, Carsten Wiuf +1 more
The sampling properties of a network's degree distribution under the most parsimonious sampling scheme is discussed and it is shown that this condition is indeed satisfied for some important classes of networks, notably classical random graphs and exponential random graphs.
Physical Review EStatistical properties of sampled networks
464 Citations2006Sang Hoon Lee, Pan‐Jun Kim +1 more
It is found that the quantities related to those properties in sampled networks appear to be estimated quite differently for each sampling method, and it is explained why such a biased estimation of quantities would emerge from the sampling procedure.
Metropolis Algorithms for Representative Subgraph Sampling
146 Citations2008Christian Hübler, Hans‐Peter Kriegel +2 more
Novel Metropolis algorithms for sampling a 'representative' small subgraph from the original large graph are presented, with 'Representative' describing the requirement that the sample shall preserve crucial graph properties of the original graph.
On unbiased sampling for unstructured peer-to-peer networks
86 Citations2006Daniel Stutzbach, Reza Rejaie +3 more
A detailed examination of the ways that the behavior of peer-to-peer systems can introduce bias is presented and the Metropolized Random Walk with Backtracking (MRWB) is suggested as a viable and promising technique for collecting nearly unbiased samples.
Physical Review EStatistical properties of sampled networks by random walks
79 Citations2007S. Y. Yoon, Sungmin Lee +2 more
The sampling method is applied to various real networks such as collaboration of movie actor, Worldwide Web, and peer-to-peer networks and all topological properties of the sampled networks are essentially the same as those of the original real networks.
Time-based sampling of social network activity graphs
56 Citations2010Nesreen K. Ahmed, Fredrick J. Berchmans +2 more
This paper proposes a novel sampling algorithm called Streaming Time Node Sampling (STNS) that exploits temporal clustering often found in real social networks and significantly out-performs state-of-the-art sampling mechanisms such as node sampling and Forest Fire sampling, across both averages and distributions of several graph properties.