Resampling effects on significance analysis of network clustering and ranking

Abstract

Community detection helps us simplify the complex configuration of networks, but communities are reliable only if they are statistically significant. To detect statistically significant communities, a common approach is to resample the original network and analyze the communities. But resampling assumes independence between samples, while the components of a network are inherently dependent. Therefore, we must understand how breaking dependencies between resampled components affects the results of the significance analysis. Here we use scientific communication as a model system to analyze this effect. Our dataset includes citations among articles published in journals in the years 1984-2010. We compare parametric resampling of citations with non-parametric article resampling. While citation resampling breaks link dependencies, article resampling maintains such dependencies. We find that citation resampling underestimates the variance of link weights. Moreover, this underestimation explains most of the differences in the significance analysis of ranking and clustering. Therefore, when only link weights are available and article resampling is not an option, we suggest a simple parametric resampling scheme that generates link-weight variances close to the link-weight variances of article resampling. Nevertheless, when we highlight and summarize important structural changes in science, the more dependencies we can maintain in the resampling scheme, the earlier we can predict structural change.

arXiv comment12 pages, 7 figures

References in corpus (24)

• Fast unfolding of communities in large networks
• Statistical mechanics of complex networks
• The structure and function of complex networks
• Community structure in social and biological networks
• Modularity and community structure in networks
• Community detection in graphs
• Fast algorithm for detecting community structure in networks
• Uncovering the overlapping community structure of complex networks in nature and society
• Maps of random walks on complex networks reveal community structure
• The large-scale organization of metabolic networks
• Defining and identifying communities in networks
• Hierarchical structure and the prediction of missing links in networks
• Link communities reveal multiscale complexity in networks
• Finding statistically significant communities in networks
• An information-theoretic framework for resolving community structure in complex networks
• Mapping change in large networks
• Extracting the hierarchical organization of complex systems
• Robustness of community structure in networks
• Community Detection as an Inference Problem
• Finding instabilities in the community structure of complex networks
• Statistical significance of communities in networks
• Measuring Significance of Community Structure in Complex Networks
• Significant communities in large sparse networks
• Effect of size heterogeneity on community identification in complex networks

Cited by in corpus (5)

• Structure and dynamics of molecular networks: A novel paradigm of drug discovery. A comprehensive review
• Significant Scales in Community Structure
• Clustering scientific publications based on citation relations: A systematic comparison of different methods
• Link-Prediction Enhanced Consensus Clustering for Complex Networks
• Non-parametric resampling of random walks for spectral network clustering