Approximate Conditional Sampling for Pattern Detection in Weighted Networks

Abstract

Assessing the statistical significance of network patterns is crucial for understanding whether such patterns indicate the presence of interesting network phenomena, or whether they simply result from less interesting processes, such as nodal-heterogeneity. Typically, significance is computed with reference to a null model. While there has been extensive research into such null models for unweighted graphs, little has been done for the weighted case. This article suggests a null model for weighted graphs. The model fixes node strengths exactly, and approximately fixes node degrees. A novel MCMC algorithm is proposed for sampling the model, and its stochastic stability is considered. We show empirically that the model compares favorably to alternatives, particularly when network patterns are subtle. We show how the algorithm can be used to evaluate the statistical significance of community structure.

References in corpus (18)

• Community structure in social and biological networks
• Community detection in graphs
• Fast algorithm for detecting community structure in networks
• Random graphs with arbitrary degree distributions and their applications
• Benchmark graphs for testing community detection algorithms
• Resolution limit in community detection
• Stochastic blockmodels and community structure in networks
• Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities
• Modularity from Fluctuations in Random Graphs and Complex Networks
• Pattern Detection in Complex Networks: Correlation Profile of the Internet
• Limited resolution in complex network community detection with Potts model approach
• Significant Scales in Community Structure
• Randomizing world trade. I. A binary network analysis
• When are networks truly modular?
• Correlations in weighted networks
• Deciphering Network Community Structure by Surprise
• Z-score-based modularity for community detection in networks
• The Grand Canonical ensemble of weighted networks