Statistical properties of sampled networks by random walks

Abstract

We study the statistical properties of the sampled networks by a random walker. We compare topological properties of the sampled networks such as degree distribution, degree-degree correlation, and clustering coefficient with those of the original networks. From the numerical results, we find that most of topological properties of the sampled networks are almost the same as those of the original networks for $\gamma \lesssim 3$. In contrast, we find that the degree distribution exponent of the sampled networks for $\gamma >3$ somewhat deviates from that of the original networks when the ratio of the sampled network size to the original network size becomes smaller. We also apply the sampling method to various real networks such as collaboration of movie actor, world wide web, and peer-to-peer networks. All topological properties of the sampled networks show the essentially same as the original real networks.

5 pages, 4 figures

References in corpus (22)

• Emergence of scaling in random networks
• Statistical mechanics of complex networks
• Assortative mixing in networks
• The diameter of the world wide web
• Evolution of networks
• Who is the best connected scientist? A study of scientific coauthorship networks
• Hierarchical Organization in Complex Networks
• Dynamical and correlation properties of the Internet
• Universal Behavior of Load Distribution in Scale-free Networks
• Scale-free topology of e-mail networks
• Large-scale topological and dynamical properties of Internet
• Growing networks with local rules: preferential attachment, clustering hierarchy and degree correlations
• Statistical properties of sampled networks
• Characterizing the dynamical importance of network nodes and links
• Traceroute sampling makes random graphs appear to have power law degree distributions
• Accuracy and Scaling Phenomena in Internet Mapping
• Sampling properties of random graphs: the degree distribution
• Self-similar Scale-free Networks and Disassortativity
• Adaptive Random Walks on the Class of Web Graph
• Scaling of random spreading in small world networks
• Intrinsic degree-correlations in static model of scale-free networks
• Diffusive Capture Process on Complex Networks

Cited by in corpus (12)

• Network Sampling: From Static to Streaming Graphs
• Complex Network Analysis of the Bitcoin Transaction Network
• Diffusive capture processes for information search
• Sampling networks by nodal attributes
• Characterizing the intrinsic correlations of scale-free networks
• Rapid Bayesian Inference of Global Network Statistics Using Random Walks
• Linked Ego Networks: Improving Estimate Reliability and Validity with Respondent-driven Sampling
• Space-Efficient Sampling from Social Activity Streams
• Abstract Phase-space Networks Describing Reactive Dynamics
• Multiple predator based capture process on complex networks
• Towards Fast Evaluation of Unsupervised Link Prediction by Random Sampling Unobserved Links
• Mean First Hitting Time of Searching for Path Through Random Walks on Complex Networks