The map equation

It is shown that different methods highlight different aspects of a network's structure and that the the sort of information that the authors seek to extract about the system must guide us in their decision.

Abstract

\n \nMany real-world networks are so large that we must simplify their structure before we can extract useful information about the systems \nthey represent. As the tools for doing these simplifications proliferate within the network literature, researchers would benefit \nfrom some guidelines about which of the so-called community detection algorithms are most appropriate for the structures they are \nstudying and the questions they are asking. Here we show that different methods highlight different aspects of a network's structure \nand that the the sort of information that we seek to extract about the system must guide us in our decision. For example, many \ncommunity detection algorithms, including the popular modularity maximization approach, infer module assignments from an underlying \nmodel of the network formation process. However, we are not always as interested in how a system's network structure was formed, as \nwe are in how a network's extant structure influences the system's behavior. To see how structure influences current behavior, we \nwill recognize that links in a network induce movement across the network and result in system-wide interdependence. In doing so, we \nexplicitly acknowledge that most networks carry flow. To highlight and simplify the network structure with respect to this flow, we \nuse the map equation. We present an intuitive derivation of this flow-based and information-theoretic method and provide an interactive \non-line application that anyone can use to explore the mechanics of the map equation. The differences between the map equation and the \nmodularity maximization approach are not merely conceptual. Because the map equation attends to patterns of flow on the network and the \nmodularity maximization approach does not, the two methods can yield dramatically different results for some network structures. To \nillustrate this and build our understanding of each method, we partition several sample networks. We also describe an algorithm and \nprovide source code to efficiently decompose large weighted and directed networks based on the map equation.\n\n