Statistical properties of sampled networks by random walks

Area of Science:

• Network Science
• Statistical Physics
• Data Analysis

Background:

• Understanding the statistical properties of complex networks is crucial for various scientific domains.
• Network sampling methods are essential for analyzing large-scale networks efficiently.
• Random walker sampling is a technique used to explore network structures.

Purpose of the Study:

• To investigate the statistical properties of networks sampled by a random walker.
• To compare topological characteristics (degree distribution, degree-degree correlation, clustering coefficient) between original and sampled networks.
• To assess the validity of random walker sampling across different network types and parameters.

Main Methods:

• Simulating random walker sampling on synthetic networks with varying parameters (gamma).
• Analyzing key topological properties of both original and sampled networks.
• Applying the sampling method to real-world networks, including movie actor collaborations, the World Wide Web, and peer-to-peer networks.

Main Results:

• For gamma < 3, most topological properties of sampled networks closely match those of original networks.
• For gamma > 3, degree distribution exponents in sampled networks show deviations when the sampled network size is significantly smaller than the original.
• Topological properties of sampled real-world networks remain largely consistent with their original counterparts.

Conclusions:

• Random walker sampling is a reliable method for preserving the essential topological properties of complex networks, especially for gamma < 3.
• Care must be taken when analyzing networks with gamma > 3 and small sampling ratios, as degree distribution may be affected.
• The findings support the applicability of random walker sampling for analyzing diverse real-world complex systems.