Identifying Modular Flows on Multilayer Networks Reveals Highly Overlapping Organization in Interconnected Systems

To comprehend interconnected systems across the social and natural sciences, researchers have developed many powerful methods to identify functional modules. For example, with interaction data aggregated into a single network layer, flow-based methods have proven useful for identifying modular dynamics in weighted and directed networks that capture constraints on flow processes. However, many interconnected systems consist of agents or components that exhibit multiple layers of interactions, possibly from several different processes. Inevitably, representing this intricate network of networks as a single aggregated network leads to information loss and may obscure the actual organization. Here, we propose a method based on a compression of network flows that can identify modular flows both within and across layers in nonaggregated multilayer networks. Our numerical experiments on synthetic multilayer networks, with some layers originating from the same interaction process, show that the analysis fails in aggregated networks or when treating the layers separately, whereas the multilayer method can accurately identify modules across layers that originate from the same interaction process. We capitalize on our findings and reveal the community structure of two multilayer collaboration networks with topics as layers: scientists affiliated with the Pierre Auger Observatory and scientists publishing works on networks on the arXiv. Compared to conventional aggregated methods, the multilayer method uncovers connected topics and reveals smaller modules with more overlap that better capture the actual organization.

Popular Summary

The convention of representing different types of interactions in a system with a single type of link is no longer the panacea of network science. Instead, temporal-, memory-, and multiplex-network representations have proven to be necessary to capture essential structural information in social and biological systems. Many tools that are useful in conventional network science have rapidly been generalized to multilayer networks, but generalizing community-detection algorithms has turned out to be a challenge characterized by two questions: What is a community in a multilayer network? How can it be identified? We demonstrate that the information-theoretic and flow-based community-detection method known as the map equation provides an effective answer to both questions.

We use numerical experiments to investigate the interconnectedness of complex networks, with the goal of identifying communities linked by some common attribute. These communities capture flow (of ideas, people, topics, etc.) within and across layers of the network. The map equation that we generalize measures how well a community partition can describe the flow, and it allows us to find the multilayer communities that reveal most regularities in the flow. We illustrate the mathematical machinery and test our method using two real-world examples: the cohort of scientists associated with the Pierre Auger Observatory (a center devoted to studying high-energy cosmic rays) and researchers publishing their studies on the website arXiv. We find that our algorithm is able to capture smaller communities than previous studies, effectively probing networks at a higher level of resolution.

We expect that our results will have applications to complex social and biological systems in which people, relationships, and cells, for instance, are linked in myriad ways.

Figure 1

Modular flow on the benchmark multilayer network. (a) A schematic multilayer network with physical nodes $i$, $j$, $k$, and $l$, and three layers $\alpha$, $\beta$, and $\gamma$ in blue, red, and orange, respectively. The physical nodes in each layer are connected with intralayer link weights $W_{jk}^{\alpha }$. (b) A random walker on the multilayer network moving between the physical nodes in each layer, twice relaxing the layer constraint and following a link from the physical node in any layer. (c) The three layers represented as a multiplex network with physical nodes in black and state nodes $i,\alpha$ in blue, red, and orange. (d) A random walker on the multiplex network moving between the state nodes. While the random walker moves according to the weights between the state nodes, only the physical nodes are considered to be observables, as illustrated by the sequence of physical nodes that the random walker has visited. When the random walker moves along links of the blue layer, it is trapped in the lower-right triangle. When the random walker moves along links of the red or orange layer, it is trapped in the upper-left triangle. As a consequence, the multilayer network has two overlapping modules with respect to flow.

Figure 2

Overlapping communities in multilayer benchmark networks. We generate the multilayer networks in two steps. (a) First, we generate $T$ LFR benchmark networks with well-defined communities, here illustrated with two network modes in blue and red. (b) Then, we sample $L$ network layers from each mode network, here illustrated with four network layers in total. (c) Each state node in the multilayer network is classified in a community, such that communities of physical nodes may overlap. In partition 1, each state node is correctly classified. In partition 2, however, the light and dark color shades are assigned to the same module, respectively. While these communities provide the correct partition of each slice, they fail to capture the communities of the two original mode networks. Generalized modularity favors partition 2, whereas the multiplex map equation favors partition 1.

Figure 3

Performance test on multilayer benchmark networks. (a,b) Performance of multiplex Infomap (Multiplex) compared with Infomap applied to the expanded network with state nodes interpreted as physical nodes (Expanded) and to each network layer separately (Single) as a function of number of network layers for 1 and 3 mode networks, respectively. We used relax rate $r=0.15$ and quantified the performance by the NMI between the planted and obtained partitions of state nodes. (c) Performance of multiplex Infomap as a function of the relax rate $r$. (d) Performance of generalized modularity optimization for $T=L=3$ as a function of the interlayer coupling $DX$, measured both as the NMI of state nodes (Multiplex) and averaged across network layers (Average).

Figure 4

Community structure in the Pierre Auger Collaboration network. (a) The overlapping community structure revealed by the multiplex map equation with relax rate $r=0.15$. Nodes for scientists are colored according to their module assignments, with node sizes proportional to the number of tasks in which they were active. Specifically, the area of a colored pie-chart slice is proportional to the number of tasks in which the corresponding scientist is active. (b) Subsets of nodes with direct comparison with the overlapping community structure obtained from dynamics with $r=1.0$.

Figure 5

Real multilayer networks with communities across network layers. The heat maps show the similarities between network layers, measured as the fraction of state nodes in different network layers that are assigned to the same communities.

Figure 6

Aggregation is responsible for significant changes in the community structure. The panels show module sizes, number of assignments per node (overlap), and NMI for communities revealed from the multilayer and the aggregated networks in the Pierre Auger Collaboration (top panels) and the arXiv (bottom panels) networks. For a given relax rate, the NMI measures the similarity between the obtained partition and the partitions obtained from the aggregated topology (blue curve) and the aggregated dynamics at relax rate $r=1.0$ (red curve), respectively.

Figure 7

Modules span more layers and overlap less with increased relax rate. Panels (a) and (c) show the number of nodes as a function of the memberships they have, i.e., the number of modules the nodes belong to, for several values of the relax rate. For each node, the maximum number of memberships is the number of layers where the node appears: This is very close to what we get for $r=0$, although the curves are not exactly the same. For $r=1$, we still have some overlap compared to the aggregated one, which is just a single point because each node belongs to one single module. Panels (b) and (d) show the number of modules that are present in the number of layers indicated on the $x$ axis. For small values of $r$, the modules tend to be localized in fewer layers.