Community extraction in multilayer networks with heterogeneous community structure

Abstract

Multilayer networks are a useful way to capture and model multiple, binary or weighted relationships among a fixed group of objects. While community detection has proven to be a useful exploratory technique for the analysis of single-layer networks, the development of community detection methods for multilayer networks is still in its infancy. We propose and investigate a procedure, called Multilayer Extraction, that identifies densely connected vertex-layer sets in multilayer networks. Multilayer Extraction makes use of a significance based score that quantifies the connectivity of an observed vertex-layer set through comparison with a fixed degree random graph model. Multilayer Extraction directly handles networks with heterogeneous layers where community structure may be different from layer to layer. The procedure can capture overlapping communities, as well as background vertex-layer pairs that do not belong to any community. We establish consistency of the vertex-layer set optimizer of our proposed multilayer score under the multilayer stochastic block model. We investigate the performance of Multilayer Extraction on three applications and a test bed of simulations. Our theoretical and numerical evaluations suggest that Multilayer Extraction is an effective exploratory tool for analyzing complex multilayer networks. Publicly available R software for Multilayer Extraction is available at https://github.com/jdwilson4/MultilayerExtraction.

46 pages. Accepted at the Journal of Machine Learning Research (11/17)

References in corpus (7)

• Modularity and community structure in networks
• Finding community structure in networks using the eigenvectors of matrices
• Maps of random walks on complex networks reveal community structure
• Near linear time algorithm to detect community structures in large-scale networks
• Finding statistically significant communities in networks
• Emergence of network features from multiplexity
• Graph spectra and the detectability of community structure in networks

Cited by in corpus (10)

• A Framework for the Construction of Generative Models for Mesoscale Structure in Multilayer Networks
• Multiplex Communities and the Emergence of International Conflict
• Hierarchical Stochastic Block Model for Community Detection in Multiplex Networks
• A New Community Definition For MultiLayer Networks And A Novel Approach For Its Efficient Computation
• Structure-Preserving Community In A Multilayer Network: Definition, Detection, And Analysis
• Multiscale modeling of brain network organization
• A Systematic Survey on Multi-relational Community Detection
• Making a Case for MLNs for Data-Driven Analysis: Modeling, Efficiency, and Versatility
• An Efficient Framework for Computing Structure- And Semantics-Preserving Community in a Heterogeneous Multilayer Network
• Hyperbolic Multiplex Network Embedding with Maps of Random Walk