A Map Equation with Metadata: Varying the Role of Attributes in Community Detection
Preprint
Abstract
As the No Free Lunch theorem formally states [1], algorithms for detecting communities in networks must make tradeoffs. In this work, we present a method for using metadata to inform tradeoff decisions. We extend the content map equation, which adds metadata entropy to the traditional map equation, by introducing a tuning parameter allowing for explicit specification of the metadata's relative importance in assigning community labels. On synthetic networks, we show how tuning for node metadata relates to the detectability limit, and on empirical networks, we show how increased tuning for node metadata yields increased mutual information with the metadata at a cost in the traditional map equation. Our tuning parameter, like the focusing knob of a microscope, allows users to "zoom in" and "zoom out" on communities with varying levels of focus on the metadata.Keywords
All Related Versions
This publication has 12 references indexed in Scilit:
- The ground truth about metadata and community detection in networksScience Advances, 2017
- Community detection in networks: A user guidePhysics Reports, 2016
- Network Structure, Metadata, and the Prediction of Missing Nodes and AnnotationsPhysical Review X, 2016
- Structure and inference in annotated networksNature Communications, 2016
- Enhanced Detectability of Community Structure in Multilayer Networks through Layer AggregationPhysical Review Letters, 2016
- Community Detection in Networks with Node Attributes2013
- Graph Spectra and the Detectability of Community Structure in NetworksPhysical Review Letters, 2012
- Inference and Phase Transitions in the Detection of Modules in Sparse NetworksPhysical Review Letters, 2011
- Community detection in graphsPhysics Reports, 2010
- Maps of random walks on complex networks reveal community structureProceedings of the National Academy of Sciences of the United States of America, 2008