The Continuous Configuration Model and Community Detection for Weighted Networks

• Activity Number: 378
• Type: Contributed
• Date/Time: Tuesday, August 11, 2015 : 11:35 AM to 12:20 PM
• Sponsor: Section on Statistical Learning and Data Mining
• Author(s): John Palowitch* and Shankar Bhamidi and Andrew Nobel
• Companies: The University of North Carolina at Chapel Hill and The University of North Carolina and The University of North Carolina at Chapel Hill
• Keywords: Community Detection ; Networks ; Data Mining ; Weighted Networks ; Configuration Model ; Stochastic Block Model

Abstract

Community detection is a task in which nodes of a network are grouped into subsets with many in-connections and few out-connections. The accurate and efficient identification of communities within networks can facilitate scientific understanding of complex systems. Many network data sets include edge weights, revealing relative importance of edges: an additional layer of statistical information. However, most community detection methods are for un-weighted networks only. We introduce a community detection method for weighted networks based on a novel extension of the graph-theoretic configuration model. The method, which we call Continuous Configuration Model Extraction (CCME), iteratively extracts communities via node-wise multiple testing, and includes only one tuning parameter controlling the false discovery rate. This allows the decisions of community size and count to be automatic and principled. We show CCME to enjoy advantages in speed and accuracy over other methods on simulations, and on real data from social networks, traffic systems, and other sources. We also prove asymptotic consistency of CCME for detecting community structure in the weighted stochastic block model.