Taxonomies of networks from community structure

The study of networks has become a substantial interdisciplinary endeavor that encompasses myriad disciplines in the natural, social, and information sciences. Here we introduce a framework for constructing taxonomies of networks based on their structural similarities. These networks can arise from any of numerous sources: They can be empirical or synthetic, they can arise from multiple realizations of a single process (either empirical or synthetic), they can represent entirely different systems in different disciplines, etc. Because mesoscopic properties of networks are hypothesized to be important for network function, we base our comparisons on summaries of network community structures. Although we use a specific method for uncovering network communities, much of the introduced framework is independent of that choice. After introducing the framework, we apply it to construct a taxonomy for 746 networks and demonstrate that our approach usefully identifies similar networks. We also construct taxonomies within individual categories of networks, and we thereby expose nontrivial structure. For example, we create taxonomies for similarity networks constructed from both political voting data and financial data. We also construct network taxonomies to compare the social structures of 100 Facebook networks and the growth structures produced by different types of fungi.

Figure 1

(a) Schematic of some of the ways that a network can break up into communities as the value of $\lambda$ (or $\xi$) is increased. (b) Zachary Karate Club network [23] for different values of the effective fraction of antiferromagnetic edges $\xi$. All interactions are either ferromagnetic or antiferromagnetic; i.e., for the values of $\xi$ that we used, there are no neutral interactions. We color edges in blue if the corresponding interactions are ferromagnetic, and we color them in red if the interactions are antiferromagnetic. We color the nodes based on community affiliation. (c) The ${\mathcal{H}}_{\mathrm{eff}}$, $S_{\mathrm{eff}}$, and ${\eta }_{\mathrm{eff}}$ MRFs, and the interaction matrix $\mathbf{J}$ for different values of $\xi$. We color elements of the interaction matrix by depicting the absence of an edge in white, ferromagnetic edges in blue (dark gray), and antiferromagnetic edges in red (light gray).

Figure 2

Values of the three mesoscopic response functions [$H_{\mathrm{eff}}\left(\xi \right)$, $S_{\mathrm{eff}}\left(\xi \right)$, ${\eta }_{\mathrm{eff}}\left(\xi \right)$] as a function of $\xi \in [0,1]$. By construction, the MRFs start from the bottom front corner $[H_{\mathrm{eff}}(\xi =0),S_{\mathrm{eff}}(\xi =0)$, ${\eta }_{\mathrm{eff}}(\xi =0)]$ and end at the top back corner $[H_{\mathrm{eff}}(\xi =1),S_{\mathrm{eff}}(\xi =1)$, ${\eta }_{\mathrm{eff}}(\xi =1)]$. We show a schematic representation of $\left[H\right(\xi ),S(\xi ),\eta (\xi \left)\right]$ for two networks; one is in blue (solid curve) and the other is in red (dashed curve). The surface represents the mean value of ${\eta }_{\mathrm{eff}}\left(\xi \right)$ for binned values of $[{\mathcal{H}}_{\mathrm{eff}}\left(\xi \right),S_{\mathrm{eff}}\left(\xi \right)]$ computed using the 189 networks identified in the right column of Table I.

Figure 3

Example scalar mesoscopic response functions (MRFs). The curves show ${\mathcal{H}}_{\mathrm{eff}}$ (magenta, dashed), $S_{\mathrm{eff}}$ (blue, dash-dotted), and ${\eta }_{\mathrm{eff}}$ (black, solid) as a function of the effective fraction of antiferromagnetic edges $\xi$ for the following networks: (a) New York Stock Exchange (NYSE), 1980–1999 [27]; (b) fractal (10,2,8) [29]; (c) Biogrid D. melanogaster [35]; (d) Garfield scientometrics citations [36]; (e) United Kingdom House of Commons voting, 2001–2005 [30]; and (f) roll-call voting of 108th United States House of Representatives [31, 32, 33, 34].

Figure 4

MRFs for 1000 realizations of Erdős-Rényi (ER), Barabási-Albert (BA), and Watts-Strogatz (WS) networks. Each network has $N=1000$ nodes and mean degree $\langle k\rangle =10$. For each value of $\xi$, the upper curves show the maximum values of ${\mathcal{H}}_{\mathrm{eff}}$ (top row), $S_{\mathrm{eff}}$ (middle row), and ${\eta }_{\mathrm{eff}}$ (bottom row) for all networks in the ensemble; the lower curves show the corresponding minimum value, and the dashed curves show the corresponding mean.

Figure 5

Upper panels: MRFs for Watts-Strogatz networks for different values of the rewiring probability $p$. Each network has $N=1000$ nodes and mean degree $\langle k\rangle =10$. Lower panels: Distribution of ${\Lambda }_{ij}$ values for each network. The MRFs for $p=1$ are indistinguishable from those of an Erdős-Rényi network with $N=1000$ and $\langle k\rangle =10$.

Figure 6

Taxonomy for 189 networks (described in the text). We construct the dendrogram (tree) using the distance matrix ${\mathbf{D}}^p$ and average linkage clustering. We order the leaves of the dendrogram to minimize the distances between adjacent nodes (using the MATLAB option $\mathtt{\text{optimalleaforder}}$) and color the leaves to indicate the type of network.

Figure 7

MRFs for all of the network categories containing at least $\text{eight}$ networks (see Table ). At each value of $\xi$, the upper curve shows the maximum value of ${\mathcal{H}}_{\mathrm{eff}}$ (magenta, left panel in each category), $S_{\mathrm{eff}}$ (blue, center panels), and ${\eta }_{\mathrm{eff}}$ (black, right panels) for all networks in the category and the lower curve shows the minimum value. The dashed curves show the corresponding mean MRFs.

Figure 8

(a) Dendrogram for Senate roll-call voting networks for the 1st–110th Congresses. Each leaf in the dendrogram represents a single Senate. The two horizontal color bars below the dendrograms indicate polarization measured in terms of optimized modularity (upper bar) and DW-Nominate scores (lower bar). We color the branches in the dendrogram corresponding to periods of similar polarization. (b) Polarization of the US Senate as a function of time, which we label using the Congress number. The height of each stem indicates the level of polarization measured using optimized modularity, and the color of each stem gives the cluster membership of each Senate in (a). The black curve shows the DW-Nominate polarization. Note that we have normalized both measures to lie in the interval $[0,1]$.

Figure 9

Comparison of the (low-polarization) 85th Senate and the (high-polarization) 108th Senate. The panels show (a) the ${\mathcal{H}}_{\mathrm{eff}}$ MRFs and (b) the cumulative distributions of ${\Lambda }_{ij}$ values.

Figure 10

Dendrogram for the United Nations General Assembly resolution voting network for the 1st–63rd sessions (excluding the 19th session), covering the period 1946–2008. Each leaf in the dendrogram represents a single session. In the main text, we discuss the coloring of groups of dendrogram branches.

Figure 11

Dendrogram for 100 Facebook networks of US universities at a single-time snapshot in September 2005. We order the leaves of the dendrogram to minimize the distances between adjacent nodes. The color bars below the dendrogram indicate (top) the number of nodes $N$ in the networks and (bottom) the edge density $e_d$.

Figure 12

(a) Dendrogram of networks for six different species of Saprotrophic basidiomycetes and the slime mold Physarum polycephalum. Each leaf represents a replicate experiment. The colors and numbers correspond to the following species: (1) Resinicium bicolor, (2) Physarum polycephalum, (3) Phallus impudicus, (4) Phanerochaete velutina, (5) Stropharia caerulea, and (6) Agrocybe gibberosa. (b) Images illustrating the network structure of the different species [53]. (c) Dendrogram of network development in six replicate time series of Phanerochaete velutina. We color the leaves by time, and the color bar underneath the leaves indicates experiment number ($1,...,6$). In the inset, we show extracted networks that illustrate the transition from simple branching trees to increasing levels of interconnection (i.e., cross-linking) with time.

Figure 13

Dendrogram for 48 NYSE networks during the period 1985–2008. For each year, we include a network both for its first half (H1) and for its second half (H2) [27]. The split of the dendrogram into two clusters (a blue group on the left and a red group on the right) appears to correspond to volatility. Leaf color indicates mean daily volatility of the composite index.

Figure 14

The first column shows the block-diagonalized distance matrices ${\mathbf{D}}^{\mathcal{H}}$ (top row), ${\mathbf{D}}^S$ (middle row), and ${\mathbf{D}}^{\eta }$ (bottom row) for the 25 networks listed in bold in Table II of the Supplemental Material. The other columns show block-diagonalized mean-distance matrices following randomizations of the original networks in which a given percentage of edges are rewired and the degree distributions of the networks are preserved. (We also constrain each rewired network to consist of a single connected component.) The components of the mean-distance matrices are given by the mean pairwise distances between the randomized networks' MRFs (see the main text for a more detailed explanation). The ordering of the nodes in the plots is fixed for each row.

Figure 15

Block-diagonalized distance matrices ${\mathbf{D}}^{\mathcal{H}}$ (top row), ${\mathbf{D}}^S$ (middle row), and ${\mathbf{D}}^{\eta }$ (bottom row) for the 25 networks listed in bold in Table II of the Supplemental Material. The first column shows the distance matrices for the original networks. The second column shows the mean-distance matrices following randomizations of the original networks in which 10 times the total number of edges in the networks have been rewired such that the degree distributions are preserved and the rewired networks each consist of a single connected component. The third column shows the mean-distance matrices following randomizations of the original networks in which 10 times the total number of edges in the networks have been rewired but only the fact that the networks consist of single connected components is preserved (i.e., the degree distributions are not preserved). The components of the mean-distance matrices for the randomizations are given by the mean pairwise distances between the networks.

Figure 16

Comparison of the MRFs produced using spectral [19], Louvain [26], and simulated-annealing [59] optimization heuristics. We show the MRFs for (a) the Zachary Karate Club network [23], (b) the roll-call voting network of the 102nd US Senate [32, 33, 34], and (c) the Garfield small-world citation network [36].

Figure 17

Comparison of the dendrograms produced using a Louvain algorithm (top panel) and simulated annealing (bottom panel) for a subset of 15 networks. The only difference between the two dendrograms is the order in which the “Communication within a sawmill on strike” and the “BA: (100,2)” networks cluster together and the distances at which the other networks become assigned to the same cluster. The names of the networks are as they appear in Table II in the Supplemental Material.

Figure 18

Comparison of the distributions of correlation coefficients between empirical Louvain dendrograms and empirical (red, hollow) and randomized (blue, solid) simulated-annealing dendrograms. See the text for details.

Figure 19

Comparison of the effectiveness of the employed distance measures at clustering networks of the same category. As discussed in the main text, we quantify this using the clustering diagnostic $\alpha \left(h\right)$. We calculate dendrograms from four distance matrices (${\mathbf{D}}^{\mathcal{H}}$, ${\mathbf{D}}^S$, ${\mathbf{D}}^{\eta }$, and ${\mathbf{D}}^p$) and compare the resulting values of $\alpha \left(h\right)$ for different sets of categories. (a) The value of the clustering diagnostic $\alpha \left(h\right)$ as a function of dendrogram cut level $h$ (i.e., where the dendrogram is split to clusters) for the following eight categories of networks: Facebook, metabolic, political cosponsorship, political committee, political voting, financial, brain, and fungal. (b) The value of $\alpha \left(h\right)$ for the largest five of the above eight categories (Facebook, metabolic, political cosponsorship, political committee, and political voting) and (c) for the smallest five of the above eight categories (Facebook, metabolic, financial, brain, and fungal). The maximum possible value of $\alpha \left(h\right)$ in each panel is equal to the number of categories considered in each panel. The values of $\alpha \left(h\right)$ obtained using the PCA-distance matrix ${\mathbf{D}}^p$ (gray solid curve) are usually higher than those obtained using the other three distance measures. This suggests that PCA distance is the most effective of the four employed clustering measures.

Figure 20

Taxonomy for 189 networks. We constructed the dendrogram using the distance matrix ${\mathbf{D}}^p$ and average linkage clustering. We order the leaves of the dendrogram to minimize the distances between adjacent nodes, and we color the leaves to indicate the type of network. The three color bars below the dendrogram indicate whether the network corresponding to each leaf is weighted or unweighted (top), the number of nodes $N$ in the networks (middle), and the edge density $e_d$ (bottom).