An empirical study of network reduction: the measurement and comparison

Network reduction and clustering are important techniques for analyzing large-scale network. This study proposed an analytic framework that considers degree distribution, clustering coefficient distribution, K-core, KS-statistic, and normalized adjusted ratio sampling (NARS) to measure and compare the social network dataset before and after reduction. The proposed NARS is to ensure that the comparison metric can obtain a fair share of nodes based on cluster size. To evaluate the framework, 20 datasets of undirected networks were examined. Results show that the proposed framework can provide multiple aspects of measurements to evaluate the reduced network and original network. The study also found that random walk, one of network reduction method, and its improved version, induced subgraph random walk methods, seems to perform equivalently if considering multiple metrics although random walk has faster computational time.