Compression of Flow Can Reveal Overlapping-Module Organization in Networks

To better understand the organization of overlapping modules in large networks with respect to flow, we introduce the map equation for overlapping modules. In this information-theoretic framework, we use the correspondence between compression and regularity detection. The generalized map equation measures how well we can compress a description of flow in the network when we partition it into modules with possible overlaps. When we minimize the generalized map equation over overlapping network partitions, we detect modules that capture flow and determine which nodes at the boundaries between modules should be classified in multiple modules and to what degree. With a novel greedy-search algorithm, we find that some networks, for example, the neural network of the nematode Caenorhabditis elegans, are best described by modules dominated by hard boundaries, but that others, for example, the sparse European-roads network, have an organization of highly overlapping modules.

Popular Summary

Passengers traveling between airports, data packets transferred on the Internet, energy transmitted on a power grid, and ideas exchanged among colleagues or friends are all examples of flow that connect the individual components of complex systems and generate intercomponent dependence. For describing these integrated systems, the theoretical constructs of networks composed of nodes and links are used, with nodes representing the components and links representing the connections between the components. Identifying and understanding how the nodes are connected and the nature of their connections should therefore serve in a fundamental way our need to control or optimize the functions of these systems. While this kind of analyses has been at the center of the complex-networks research, the fact that flows underpin the structural organizations and functions of many network systems has often been overlooked. In this paper, we take a flow-centric perspective and provide an information-theoretic method for sorting the nodes of a network into possibly overlapping functional modules based on the nature and strength of the flows connecting the nodes.

We characterize the structural organization of a network by analyzing the flow on it and identifying the structural pattern of the flow: A group of nodes interconnected by a separate flow system whose integrity persists over a long time is identified as a module; modules are said to be overlapping when their corresponding flows run through a set of shared nodes; and the shared nodes define “fuzzy boundaries” between the modules. The questions for structural sorting of the nodes then become: What is the number of modules in a network? Which nodes belong to which modules? And which nodes should belong to multiple modules and to what degree?

We answer these questions in an information-theoretic framework that takes advantage of the principle that all regularities in data can be used to compress the data. Specifically, we describe the flow through a system as two distinct types of movements: within modules and between modules, very much like the way we use phone numbers for calls within cities and area codes for calls between cities. The length of such a module-aware description depends on how modules are identified and how nodes are assigned to the modules. With too many or too few modules, the description will be longer than it is if we use the optimal number of modules. The same will happen if we assign nodes to too many, too few, or inapt modules. Therefore, our task becomes compressing the description by finding the optimal assignments of nodes into modules. This approach allows us to resolve the fuzzy boundaries between modules by maximally compressing our module-aware description of the flow through the entire network system.

At a speed on par with the fastest methods that operate on the topological backbone of a system instead of on the flow through a system, our novel greedy-search algorithm can capture the overlapping flow systems of networks that are good candidates for functional components in social and biological systems.

Figure 1

(a) Map showing that part of the global air-traffic network in which Keflavik airport in Reykjavik, Iceland, connects Europe and North America. The map equation for overlapping modules can exploit regularities in the boundary flow between modules. The three colored lines in (b) show the description length as a function of the proportion of returning passengers for three different partitions: North America, Europe, and Reykjavik in one big module (green solid line); North America and Europe in two nonoverlapping modules, with Reykjavik in either of the modules (black dashed line); and North America and Europe in two overlapping modules, with Reykjavik in both modules (blue dashed-dotted line).

Figure 2

The code structure of the map equation (a) without overlapping modules and (b) with overlapping modules. The color of a node in the networks at the left and of the corresponding block in the code structures at the right represents the module assignment; the width of a block in the code structures represents the node-visit rate; and the height $H$of the code-structure blocks represents the average length of code words in the codebooks.

Figure 3

Network scientists organized in overlapping research groups. The colors of the nodes represent overlapping research groups identified by the map equation, the size of the nodes represents the importance of the researchers as quantified by the node-visit rates of the random walker; and the pie charts in certain nodes (for instance, for Amaral and Guimera in the upper right) represent the fractional association with the different research groups for researchers that have multiple assignments.

Figure 4

Movements between nodes that are possibly assigned to multiple modules. (a) Assuming that the random walker is in module $i$, she remains in module $i$ when moving to node $\beta$ if node $\beta$ is also assigned to module $i$. (b) However, if node $\beta$ is not assigned to module $i$, she switches with equal probability to any of the modules to which node $\beta$ is assigned.

Figure 5

General scheme of the two-step greedy-search algorithm for overlapping modules. (a) Pseudocode of the algorithm iteration [b] of first step [c] and second step [d]. Markers [b], [c], and [c] in the pseudocode correspond to figures (b), (c), and (d). Starting from a hard partition generated by Infomap [18], each iteration successively increases the overlap between modules to minimize the map equation for overlapping modules. In the first step (c), one by one, each boundary node is assigned to adjacent modules. In the second step (d), we first sort the local changes from best to worst and then iteratively apply quadratic fitting to find the number of best local changes that minimizes the map equation.