Sampling properties of random graphs: the degree distribution
arXiv:cond-mat/0507345 · doi:10.1103/PhysRevE.72.036118
Abstract
We discuss two sampling schemes for selecting random subnets from a network: Random sampling and connectivity dependent sampling, and investigate how the degree distribution of a node in the network is affected by the two types of sampling. Here we derive a necessary and sufficient condition that guarantees that the degree distribution of the subnet and the true network belong to the same family of probability distributions. For completely random sampling of nodes we find that this condition is fulfilled by classical random graphs; for the vast majority of networks this condition will, however, not be met. We furthermore discuss the case where the probability of sampling a node depends on the degree of a node and we find that even classical random graphs are no longer closed under this sampling regime. We conclude by relating the results to real {\it E.coli} protein interaction network data.
accepted for publication in Phys.Rev. E
References in corpus (1)
Cited by in corpus (29)
- Statistical properties of sampled networks
- Exploring Complex Networks through Random Walks
- Statistical properties of sampled networks by random walks
- Testing statistical laws in complex systems
- Network science: a review focused on tourism
- Estimating network degree distributions under sampling: An inverse problem, with applications to monitoring social media networks
- Estimation of global network statistics from incomplete data
- Revealing biases in the sampling of ecological interaction networks
- Sampling properties of directed networks
- What does Big Data tell? Sampling the social network by communication channels
- Sampling from naturally truncated power laws: The matchmaking paradox
- Finite size effects in Barabasi-Albert growing networks
- Diffusive capture processes for information search
- Stylized facts in social networks: Community-based static modeling
- Sampling on networks: estimating eigenvector centrality on incomplete graphs
- Sampling networks by nodal attributes
- Sampling-based Estimation of In-degree Distribution with Applications to Directed Complex Networks
- Degree distributions under general node removal: Power-law or Poisson?
- What you see is not what you get: how sampling affects macroscopic features of biological networks
- Inferring Degrees from Incomplete Networks and Nonlinear Dynamics
- Sampling on networks: estimating spectral centrality measures and their impact in evaluating other relevant network measures
- One-class Collaborative Filtering with Random Graphs: Annotated Version
- Emergence of Network Structure in Models of Collective Evolution and Evolutionary Dynamics
- Preserving Minority Structures in Graph Sampling
- Estimation of Vertex Degrees in a Sampled Network
- True Nonlinear Dynamics from Incomplete Networks
- Triangle Preferential Attachment Has Power-law Degrees and Eigenvalues; Eigenvalues Are More Stable to Network Sampling
- A Goodness-of-Fit Test for Sampled Subgraphs
- Distinguishing subsampled power laws from other heavy-tailed distributions