A Map Equation with Metadata: Varying the Role of Attributes in Community Detection

Abstract

Much of the community detection literature studies structural communities, communities defined solely by the connectivity patterns of the network. Often, networks contain additional metadata which can inform community detection such as the grade and gender of students in a high school social network. In this work, we introduce a tuning parameter to the content map equation that allows users of the Infomap community detection algorithm to control the metadata's relative importance for identifying network structure. On synthetic networks, we show that our algorithm can overcome the structural detectability limit when the metadata is well-aligned with community structure. On real-world networks, we show how our algorithm can achieve greater 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.

References in corpus (16)

• Scikit-learn: Machine Learning in Python
• Fast unfolding of communities in large networks
• Community detection in graphs
• Maps of random walks on complex networks reveal community structure
• Link communities reveal multiscale complexity in networks
• Community detection in networks: A user guide
• The ground truth about metadata and community detection in networks
• Phase transition in the detection of modules in sparse networks
• Structure and inference in annotated networks
• Graph spectra and the detectability of community structure in networks
• Ranking and clustering of nodes in networks with smart teleportation
• Enhanced detectability of community structure in multilayer networks through layer aggregation
• Map equation for link community
• Network structure, metadata and the prediction of missing nodes and annotations
• Case studies in network community detection
• Stochastic Block Models with Multiple Continuous Attributes

Cited by in corpus (6)

• Community detection with node attributes in multilayer networks
• The Minimum Description Length Principle for Pattern Mining: A Survey
• Mapping flows on weighted and directed networks with incomplete observations
• Community Detection with the Map Equation and Infomap: Theory and Applications
• Detecting User Community in Sparse Domain via Cross-Graph Pairwise Learning
• Single-trajectory map equation