Sampling properties of directed networks
arXiv:1201.1507 · doi:10.1103/PhysRevE.86.046104
Abstract
For many real-world networks only a small "sampled" version of the original network may be investigated; those results are then used to draw conclusions about the actual system. Variants of breadth-first search (BFS) sampling, which are based on epidemic processes, are widely used. Although it is well established that BFS sampling fails, in most cases, to capture the IN-component(s) of directed networks, a description of the effects of BFS sampling on other topological properties are all but absent from the literature. To systematically study the effects of sampling biases on directed networks, we compare BFS sampling to random sampling on complete large-scale directed networks. We present new results and a thorough analysis of the topological properties of seven different complete directed networks (prior to sampling), including three versions of Wikipedia, three different sources of sampled World Wide Web data, and an Internet-based social network. We detail the differences that sampling method and coverage can make to the structural properties of sampled versions of these seven networks. Most notably, we find that sampling method and coverage affect both the bow-tie structure, as well as the number and structure of strongly connected components in sampled networks. In addition, at low sampling coverage (i.e. less than 40%), the values of average degree, variance of out-degree, degree auto-correlation, and link reciprocity are overestimated by 30% or more in BFS-sampled networks, and only attain values within 10% of the corresponding values in the complete networks when sampling coverage is in excess of 65%. These results may cause us to rethink what we know about the structure, function, and evolution of real-world directed networks.
arXiv comment21 pages, 11 figures
References in corpus (28)
- Statistical mechanics of complex networks
- The structure and function of complex networks
- Error and attack tolerance of complex networks
- Epidemic spreading in scale-free networks
- Lethality and centrality in protein networks
- The diameter of the world wide web
- Evolution of networks
- Resilience of the Internet to random breakdowns
- Epidemic dynamics and endemic states in complex networks
- Breakdown of the Internet under intentional attack
- Community structure in directed networks
- Small world effect in an epidemiological model
- Patterns of link reciprocity in directed networks
- Statistical properties of sampled networks
- Critical behavior of propagation on small-world networks
- Giant strongly connected component of directed networks
- Synchronization is optimal in non-diagonalizable networks
- Edge direction and the structure of networks
- Synchronization in scale-free network with asymmetric coupling
- Efficiency and reliability of epidemic data dissemination in complex networks
- Spreading gossip in social networks
- Local structure of directed networks
- Sampling properties of random graphs: the degree distribution
- Reciprocity of Networks with Degree Correlations and Arbitrary Degree Sequences
- Dynamic behaviors in directed networks
- Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters
- Towards Unbiased BFS Sampling
- On the bias of BFS
Cited by in corpus (9)
- Structure and dynamics of molecular networks: A novel paradigm of drug discovery. A comprehensive review
- Aggregate Characterization of User Behavior in Twitter and Analysis of the Retweet Graph
- Social Bootstrapping: How Pinterest and Last.fm Social Communities Benefit by Borrowing Links from Facebook
- Sampling promotes community structure in social and information networks
- Turing instability and pattern formation on directed networks
- PageRank and rank-reversal dependence on the damping factor
- Sampling networks by nodal attributes
- Degree distributions under general node removal: Power-law or Poisson?
- Sampling node group structure of social and information networks