Map equation with metadata: Varying the role of attributes in community detection

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 are 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.

Figure 1

Illustrating how our formulation of the content map equation extends the traditional map equation. (a) An example random walk on a weighted, undirected network. The thickness of each edge corresponds to its weight. (b) Encoding the location of the random walker with a Huffman encoding that assigns each node a unique codeword in a single codebook. (c) Compressing the description of the random walk with the traditional map equation, which encodes the location of the random walker using an intermodule codebook that contains module names and intramodule codebooks that contain node names and an “exit” keyword. The codewords to the left and right of the arrow for each module respectively show the corresponding module's name in the intermodule codebook and its “exit” keyword in its intramodule codebook. (d) Introducing four discrete metadata values, depicted by shape, to the nodes of the network. Our extension of the traditional map equation with the content map equation additionally encodes the metadata value at each step of the random walk by introducing metadata codebooks. The metadata codewords are underlined, and keys for the metadata codebooks are given by the hollowed-out shapes. Because the blue module contains only one distinct metadata value, encoding the walker's entrance to and exit from the blue module fully specifies the metadata without requiring a metadata codebook. [Panels (a)–(c) are from a figure by Rosvall and Bergstrom [15], Copyright (2008) National Academy of Sciences, U.S.A.]

Figure 2

Detectability experiments on a planted-partition stochastic block model with $N=200$ nodes evenly divided into two communities. Each node's attribute label corresponds with its planted partition community with probability noise, and $\mathrm{\Delta }$ measures the assortativity of the planted partition. We see that focusing on the metadata by increasing $\eta$ enables the algorithm to overcome the detectability limit when the metadata has strong signal, but increasing $\eta$ ceilings the algorithm's performance when the metadata are noisy.

Figure 3

The Lazega lawyers friendship network partitioned with the metadata attribute gender at (a) $\eta =0$, (b) $\eta =0.7$, and (c) $\eta =1.25$. Color encodes the partition while shape encodes the metadata.

Figure 4

Sums of various types of entropy when partitioning the Lazega lawyers (a) coworking, (b) friendship, and (c) advice networks. The sums are weighted by frequency of codebook use but not weighted by $\eta$.

Figure 5

The Lazega lawyers advice network partitioned with the metadata attribute status at (a) $\eta =0$ and (b) $\eta =0.5$. Color encodes the partition while shape encodes the metadata.

Figure 6

Pairwise AMIs of high school social network partitions at (a) $\eta =0$ and (b) $\eta =3$. For example, “grade” is the partition given by each node's grade, and “c_grade” is the algorithm's returned partition when partitioning with the grade metadadta.

Figure 7

Pairwise AMIs of high school social network partitions. For example, “grade” is the partition given by each node's grade, and “c_grade” is the algorithm's returned partition when partitioning with the grade metadata for a given value of $\eta$.

Figure 8

Topological entropy and AMI tradeoff when partitioning with metadata in the high school social network. Topological entropy, equal to the traditional map equation, is the sum of the intermodule codebook and intramodule codebook entropies. The AMI is between the node metadata and the algorithm's returned partition.