††thanks: Corresponding author

# Mapping change in higher-order networks
with multilevel and overlapping communities

Anton Holmgren  0000-0001-5859-4073<EMAIL_ADDRESS>Integrated Science
Lab, Department of Physics, Umeå University, SE-901 87 Umeå, Sweden  Daniel
Edler  0000-0001-5420-0591 Integrated Science Lab, Department of Physics, Umeå
University, SE-901 87 Umeå, Sweden  Gothenburg Global Biodiversity Centre,
Department of Biological and Environmental Sciences, University of Gothenburg,
SE-405 30 Gothenburg, Sweden  Martin Rosvall  0000-0002-7181-9940
<EMAIL_ADDRESS>Integrated Science Lab, Department of Physics, Umeå
University, SE-901 87 Umeå, Sweden

###### Abstract

New network models of complex systems use layers, state nodes, or hyperedges
to capture higher-order interactions and dynamics. Simplifying how the higher-
order networks change over time or depending on the network model would be
easy with alluvial diagrams, which visualize community splits and merges
between networks. However, alluvial diagrams were developed for networks with
regular nodes assigned to non-overlapping flat communities. How should they be
defined for nodes in layers, state nodes, or hyperedges? How can they depict
multilevel, overlapping communities? Here we generalize alluvial diagrams to
map change in higher-order networks and provide an interactive tool for anyone
to generate alluvial diagrams. We use the alluvial generator to illustrate the
effect of modeling network flows with memory in a citation network,
distinguishing multidisciplinary from field-specific journals.

## Introduction

Complex systems are inherently dynamic. Their components influence each other
through various informational and physical processes, changing interaction
patterns over time. Researchers represent these interactions with networks 1,
2, 3, 4, 5, 6, 7 and simplify their organization with community-detection
algorithms 8, 9, 10, 11, 12. For example, community-detection algorithms that
model the various processes as flows on networks assign nodes to possibly
nested modules of typically densely connected nodes, among which the network
flows persist relatively long 8. Identifying modules in multiple networks with
shared nodes enables exploring organizational changes when the systems they
represent change over time or between states: Modules merge and split when
groups in students’ social networks form and dissolve during school days, or
new research fields emerge when old fields fuse or break and move apart.
Various summary statistics can quantify these structural changes 13, 14, 15,
but they destroy essential information about how the networks change.

Alluvial diagrams with modules represented as stacks of blocks joined by
stream fields were introduced to reveal network organizational changes by
depicting merging and splitting modules 16. Researchers have successfully used
them to map shifting regional tendencies in urban networks 17, study dynamics
of hot topics in research fields 18, 19, track changing bitcoin user activity
20, and explore evolving media channel preferences across crisis phases 21.
Generating alluvial diagrams requires dedicated software to remove tedious
manual work. However, current applications to generate alluvial diagrams work
only for standard networks partitioned into modules.

Today researchers use temporal, multilayer, and memory networks to capture
interactions in complex systems with higher accuracy 22, 23, 24, 25, 26, 27
and multilevel modular solutions to reveal more regularities in their
organization 28, 29. Multilayer networks can represent networks over time with
links in time-windowed layers. Memory networks can represent higher-order
network flow models where the transition rates depend on the current node and
previously visited nodes. Both representations enable overlapping modules.
Mapping change in these rich network representations requires generalizing
alluvial diagrams and their generators to higher-order networks with
multilevel and overlapping modular solutions.

(a)

(b)

(c)

(d)

(e)

\begin{overpic}[width=433.62pt]{figs/modular_schematic_new.pdf}
\put(0.0,41.0){\small{{a}\hskip 2.0pt Modular network}}
\put(18.0,41.0){\small{{b}\hskip 2.0pt Two-level solution}}
\put(39.5,41.0){\small{{c}\hskip 2.0pt Alluvial diagram}}
\put(61.0,41.0){\small{{d}\hskip 2.0pt Multilevel solution}}
\put(82.0,41.0){\small{{e}\hskip 2.0pt Multilevel network}}
\par\put(18.0,-3.0){\small Level} \put(26.4,-3.0){\small$1$}
\put(32.3,-3.0){\small$2$} \put(61.6,-3.0){\small$3$}
\put(68.0,-3.0){\small$2$} \put(73.0,-3.0){\small$1$} \end{overpic}

Figure 1: Schematic alluvial diagram of a multilevel network structure. a) A
weighted network with modular structure, organized into a two-level solution
in b). c) An alluvial diagram representation of the solutions in panels (b)
and (d) using the same colors. Columns of blocks represent modules with
heights proportional to the contained flow volume. The leftmost column is an
ordinary two-level alluvial diagram representation. The multilevel
representation to the right shows multiple levels, with the background showing
the top-level organization. Stream fields connect modules in the left and
right columns that share nodes. d) Multilevel solution of the network in (e).

Here we introduce alluvial diagrams for multilayer and memory networks with
multilevel and overlapping modular solutions. We demonstrate a new alluvial
generator for higher-order networks available for anyone to use at
https://www.mapequation.org/alluvial30, and illustrate how we use it in three
case studies revealing: significant changes in the multilevel organization of
science over six years using parametric bootstrap resampling,
multidisciplinary journals in a second-order network representation of
citation flows, and the effects of multilayer representation of a
collaboration hypergraph.

## Methods

Alluvial diagrams depict changes in the modular composition between networks
with stacks of blocks representing the modules (Fig. 1). Each block’s height
is proportional to the flow volume of the corresponding module – the total
visit probability of all nodes in the module. To highlight structural change
between multiple networks, a vertical stack of blocks represent each network’s
modular structure, and horizontal stream fields connect blocks that share
nodes across neighboring networks. Like block heights, stream-field heights
are proportional to the flow volume of the node overlap between corresponding
modules. To reduce clutter, we order stream fields to minimize their overlap.

We use Infomap to search for multilevel modular structures with nested
submodules.31, 28 Infomap optimizes the map equation, the average per-step
codelength on a modular description of a random walk modeling network flows.8
The modules are groups of nodes where the random walker spends a relatively
long time compared to exiting it and entering other modules. While we focus on
modules derived from Infomap, alluvial diagrams work with output from any
community detection or hierarchical data clustering method.

### Mapping change in networks with multilevel communities

We extend alluvial diagrams to multilevel network partitions by nesting
submodules in super-modules with adaptive module distances. The right
multilayer stack of the schematic alluvial diagram in Fig. 1c illustrates. In
the spirit of cartography, we put blocks corresponding to the top-level
modules in a bottom layer to highlight the large-scale organization and
provide a cleaner visualization. Optionally, we display finer-level structures
in layers above the bottom layer. The right multilayer stack in Fig. 1c
expands the left stack’s single layer with one such extra layer corresponding
to the four submodules of the multilevel modular solution. To show that deeper
submodules are more closely related than their larger parent modules, we draw
sibling submodules closer together than other modules. Specifically, we halve
the distance between two adjacent modules for each level down in the
multilevel solution.

#### Multilevel significance clustering

To separate trends from mere noise in the module assignments, we extend the
significance clustering method described in ref. 16 to multilevel partitions.
The approach has three main steps: First, we search for optimal multilevel
partitions for each network using Infomap. Then, to assess these partitions’
robustness to slight perturbations in the data, we create a large number of
independent bootstrap networks. For each bootstrap network, we search for the
optimal multilevel partition using Infomap as for the original network.
Finally, we summarize the variability in the bootstrap partitions by applying
the significance clustering method introduced in ref. 16 extended to
multilevel partitions. For each level in the multilevel solution of the
original network, we search for the largest subset of nodes in each module or
submodule that are also clustered together in at least a fraction $p$ of
solutions obtained from the parametric bootstrap procedure.

Searching for significant subsets in multilevel solutions is computationally
more demanding than for ordinary two-level partitions. To improve the
performance, we trivially parallelize the algorithm by running each module or
submodule in separate threads.

### Mapping change in higher-order networks

We generalize alluvial diagrams to multilayer and memory networks. Multilayer
networks can model different modes of interaction or interactions that change
over time in different layers. Memory networks can model dynamics that depend
on from where the flows come. Infomap represents both higher-order networks
with so-called _state nodes_.32 In higher-order networks, we call ordinary
nodes _physical nodes_ to distinguish them from state nodes. In a multilayer
network, one state node for each physical node and layer represents the
physical node in the layer.24 In a second-order memory network with memory of
the previous step, one state node for each physical node and incoming link
represents the physical node for flows incoming along that link.23 Physical
nodes with multiple state nodes and different outgoing links can model higher-
order dynamics on the network.

(a)

(b)

(c)

\begin{overpic}[width=433.62pt]{figs/higher_order_schematic_new.pdf}
\put(5.0,51.0){\small{{a}}} \put(35.0,51.0){\small{{b}}}
\put(73.0,51.0){\small{{c}}} \end{overpic}

Figure 2: Schematic first-order and higher-order networks and alluvial diagram
representation. a) A first-order network with pseudo-states (white dashed
circles) matching the state nodes in (c). b) An alluvial diagram
representation. c) A higher-order network with state nodes (small blue and
purple circles) in the physical nodes. We only show the state nodes whose
physical nodes are present in two modules.

In theory, using alluvial diagrams for higher-order networks is no different
than for ordinary networks. In practice, the many possible combinations of
first- and higher-order networks, memory networks with different memory, and
multilayer networks with different layers make it challenging to determine
node equality in different networks because we need to match nodes across
networks to draw stream fields between modules. While alluvial diagrams
require networks to share a significant fraction of physical nodes, we also
need their state nodes to match since they are the smallest components of
higher-order networks. With no universal solution to this node-matching
problem, we discuss some challenges and how we choose to solve them.

#### First- and higher-order networks

Alluvial diagrams with first- and higher-order networks require matching
different node types: First-order networks have only physical nodes, but
higher-order networks have physical nodes and state nodes. We illustrate this
schematically in Fig. 2 with a first-order network in Fig. 2a and a higher-
order network with state nodes as smaller circles inside the physical nodes in
Fig. 2c. We consider only hard module boundaries in the first-order network,
whereas modules overlap in the higher-order network when physical nodes’ state
nodes are assigned to different modules. In Fig. 2c, the modules overlap in
the physical nodes containing the purple and blue state nodes.

As we need a one-to-one match across networks to draw stream fields, we cannot
match all state nodes in the higher-order network to one first-order node. To
overcome this problem, we first split the first-order nodes into pseudo-state
nodes, which we depict with small dashed circles in Fig. 2a. We create as many
pseudo-state nodes as there are state nodes in the matching physical node in
the higher-order network. Then, we divide first-order node $i$’s flow volume
$\pi_{i}^{(1)}$ among its pseudo-states $\alpha$ proportionally to their
matching state nodes’ fraction of the flow $\pi_{i\alpha}^{(2)}$ as

$\pi_{i\alpha}^{(1)}=\pi_{i}^{(1)}\frac{\pi_{i\alpha}^{(2)}}{\pi_{i}^{(2)}}.$
(1)

This procedure gives a one-to-one match between nodes in first- and higher-
order networks, and we can draw multiple stream fields from a single first-
order node (Fig. 2b).

#### Memory networks

Drawing alluvial diagrams for memory networks requires matching state nodes
representing corresponding memory in different networks. We match state nodes
across networks by encoding their memory in their ids such that state nodes
representing the same memory share the same id in different networks. As long
as the networks are not too large, we can encode memory of order $n$ into a
single binary number by dividing the binary number into $n$ parts: We divide
the number into two parts in a second-order memory network with memory of the
previous step. With $N$ physical nodes, we use the $b=\lceil\log_{2}N\rceil$
most significant bits of the state id to encode the previously visited node
$i$ and the $b$ least significant bits to encode the currently visited node
$j$, resulting in the state id

$\alpha_{i\to j}=i\ll b+1\,\lor\,j,$ (2)

where $\ll$ is the arithmetic left-shift operator and $\lor$ is the logical
or. For example, we encode the link from physical node 2 to physical node 3
along the path represented by the trigram $1\to 2\to 3$ as

$\displaystyle\alpha_{1\to 2}$ $\displaystyle=1\ll 2+1\lor 2=1000_{2}\lor
10_{2}=1010_{2}=10,$ $\displaystyle\alpha_{2\to 3}$ $\displaystyle=2\ll
2+1\lor 3=10000_{2}\lor 11_{2}=10011_{2}=19,$

resulting in the directed link $10\to 19$ between state nodes 10 and 19. This
encoding scheme works for up to $N=2^{16}=65,536$ physical nodes with 32-bit
ids and second-order memory.

#### Multilayer networks

When comparing multiple multilayer networks with $N$ layers, we encode the
physical node $i$ in layer $l$ with id

$\alpha_{i,l}=i\ll b+1\,\lor\,l,$ (3)

where $N$ is the largest layer id represented with $b=\lceil\log_{2}N\rceil$
bits. For multilayer networks, this encoding scheme is available in Infomap
using the flag \--matchable-multilayer-ids N.

Alluvial diagrams can also visualize the layers of multilayer networks, each
as a separate network. In this case, node matching is trivial as physical
nodes are unique in each layer. The stream fields then connect modules that
span layers.

### Alluvial diagram generator

We have implemented an interactive web application that generates alluvial
diagrams, available for anyone to use at https://www.mapequation.org/alluvial.
We implemented it as a client-side web application to enable researchers to
use our application without programming experience or those working with
sensitive data. All code runs locally in the user’s web browser, and the web
application does not store or upload network data to any server. We
implemented it using TypeScript and React, and we display the diagrams using
scalable vector graphics (SVG) (see Fig. S2 in the SI for how we model the
data structures).

While the most efficient community detection pipeline is to run the stand-
alone C++ version of Infomap and load the resulting partitions, we have
embedded a version of Infomap compiled to JavaScript with Emscripten.33 This
embedded Infomap version supports the same network inputs as C++ Infomap, but
only a subset of Infomap’s features, including reading directed or undirected
input, choosing the number of optimization trials, and searching for
multilevel or two-level solutions (Fig. 3). We defer the specification of
input formats to Sec. SI.1. We also support loading solutions from Infomap
Online,34 a fully featured web-based version of Infomap.

Figure 3: Loading networks in the alluvial diagram generator. Three networks
are loaded in different stages, shown as gray rectangles. The leftmost network
has communities detected by Infomap. Infomap runs on the second network and
has completed two out of five optimization trials. Infomap has yet to start
identifying communities in the rightmost network. When all have finished, or
when loading networks with communities from C++ Infomap, the user can select
“Create Diagram” to create an alluvial diagram.

With loaded networks, the interface shows the user a top-level view of the
alluvial diagram (Fig. S1). The user can manipulate the diagram in several
ways: expand modules to reveal their submodules, reorganize networks and
modules for clarity, highlight modules or individual nodes with different
colors, and change the diagram width and height. While we have implemented the
features and use cases we think most researchers use, we can imagine feature
requests for specific use cases. By supporting export to SVG, researchers can
modify the diagrams to their needs in any vector graphics application.

Figure 4: Multilevel organization of science, 2001–2007. The journals organize
into five large research areas, further divided into research fields. We show
the top-level organization of earth sciences, economics, and computer science
(the three small modules at the top). We show the finer division into research
fields for the physical and life sciences. We sort the fields or areas by
their citation flow and show the top-ranking journal in each research field or
area. Finally, we highlight the insignificant assignment of journals clustered
with Ecology in 2001 to a significantly distinct research field since 2003. At
the top level shown in the inset, the same journals cluster significantly with
the life sciences since 2007.

## Results

We highlight different visualization challenges in three case studies using
multilevel, higher-order, and multilayer networks. In all cases, we use
Infomap to identify optimal multilevel solutions using unrecorded
teleportation to links with minimal impact from the teleportation rate on the
results.35

### Robust multilevel citation networks

First, we highlight the multilevel organization of science into research areas
and fields. We use data from Thomson-Reuters Journal Citation Reports.16 The
data include citations between journals published from 2001–2007, divided into
four two-year periods. The networks have, on average, $7,490$ nodes
representing journals and $586,295$ integer-weighted links representing the
citation flow between them. For each year, we use Infomap with 100
optimization trials to search for the optimal multilevel solution. We use the
multilevel significance clustering approach described in the Methods section
to assess the solution’s robustness to slight perturbations in the data.
First, we create 1000 independent bootstrap networks by sampling each citation
weight $w_{uv}$ from a Poisson distribution,
$\hat{w}_{uv}\sim\text{Poisson}(w_{uv})$. Then, we use Infomap to search for
the optimal multilevel solution for each bootstrap network. The bootstrap
solutions have similar codelengths, with a variance of around $10^{-5}$.
Finally, we use the significance clustering algorithm to search for the
largest fraction of nodes clustered together in at least a fraction $p=0.95$
of the bootstrap solutions.

The resulting multilevel partitions organize science into research areas,
further divided into research fields (Fig. 4). With the multilevel solution
and unrecorded teleportation scheme, we do not exactly reproduce the results
presented in Ref. 16. The life sciences show higher diversification, with more
significant research fields and lower citation flows in molecular- and cell
biology containing J. Biol. Chem., Nature, PNAS, Science, Cell, and so on.

### First- and second-order citation networks

In the second case study, we visualize the effects of using higher-order
network models with alluvial diagrams. We organize the citation data from the
Thomson-Reuters Journal Citation Reports into citation pathways.36, 37 The
data contain citations between articles published from 2007 to 2012 in the
$10\,000$ journals with the highest impact factor, and all citation pathways
contain at least one article published in 2009. When aggregated to journals,
we are left with $69,738,205$ weighted trigrams.

To study the effect of a second-order model, we model the data using both
first- and second-order Markov chains. We create a first-order network by
discarding the first step from each trigram. For example, the trigram $i\to
j\to k$ with weight $w$ becomes the directed link $j\to k$ with the same
weight, resulting in 69 million links between the $10,000$ nodes. Using the
complete trigram data, we create a second-order network. For each trigram
$i\to j\to k$ with weight $w$, we create two state nodes if they do not
already exist:

  * •

$\alpha_{i\to j}$ in physical node $j$ representing the memory of coming from
$i$,

  * •

$\alpha_{j\to k}$ in physical node $k$ representing the memory of coming from
$j$.

We connect the state nodes with a directed link $\alpha_{i\to
j}\to\alpha_{j\to k}$ with weight $w$. The resulting second-order network has
around $3.9$ million state nodes connected by 69 million links.

Because the second-order network has two orders of magnitude more state nodes
than the first-order network has physical nodes, the community detection
search space is much larger, significantly impacting the computational time.
The first-order network takes around two minutes for ten optimization trials,
while the second-order network takes around nine hours for the same task. The
resulting first-order partition has codelength $L^{(1)}=8.44$ bits, five top
modules, and four levels. The second-order partition has codelength
$L^{(2)}=7.83$ bits, around $4,700$ top modules, and five levels. Although the
second-order partition has many top modules, most are tiny, containing only
one or a few state nodes. To downplay small modules at the fringe of the
citation data, we compare the partition’s effective number of top modules
using the perplexity $M_{\text{eff}}=2^{H(M)}$, with Shannon entropy

$H(M)=-\sum_{m}\pi_{m}\log_{2}\pi_{m},$ (4)

where $\pi_{m}=\sum_{i\in m}\pi_{i}$ is the total flow volume of the nodes $i$
in module $m$. With this metric, the first- and second-order partitions are
similar with $M_{\text{eff}}^{(1)}=2.35$ and $M_{\text{eff}}^{(2)}=2.73$
effective top modules, respectively.

After detecting communities, we aggregate redundant state nodes in the second-
order network before visualization for better performance. We lump state nodes
in the same physical node and leaf module and aggregate their flows, reducing
the number of states to visualize from 3.9 million to 355 thousand. After
lumping, we remove any state nodes with zero flow that would not contribute to
the alluvial diagram layout, further reducing the number of states to 271
thousand. Then, we create pseudo-states in the first-order network to match
the higher-order state nodes. After this step, both networks contain 271
thousand state nodes. In the first-order network, all state nodes are in the
same module as their physical node.

Figure 5: A second-order Markov model results in overlapping multidisciplinary
journals. The leftmost network is first-order, and the rightmost is second-
order. Colors indicate the journal’s weighted overlap in the second-order
network.

The alluvial diagram shows how the second-order model separates cosmology and
astrophysics from the physical sciences (Fig. 4). The cell- and molecular
biology submodule containing Nature, PNAS, and Science grows, and the
multidisciplinary journals’ submodules in the life sciences divide into
smaller modules.

Figure 6: Influential multidisciplinary journals. The weighted overlap is the
product of the journal’s citation flow and its effective number of research
fields. We limit the x-axis to six fields, but some small journals are in more
than 30 research fields.

Above all, Nature, Science, and PNAS are all recognized as multidisciplinary
journals represented in multiple research fields. To quantify how a higher-
order model captures their citation flows, we investigate in how many research
fields journals are present. Since a single research field dominates most
journals’ citation flows, we measure the effective number of research fields.
With journal $i$’s module-aggregated state node flow
$\boldsymbol{\pi}_{i}=\\{\pi_{i\alpha}\\}$, we calculate its effective number
of research fields $r_{i}=2^{H(\boldsymbol{\pi}_{i})}$ with the entropy
$H(\boldsymbol{\pi}_{i})=-\sum_{\alpha}\pi_{i\alpha}\log_{2}\pi_{i\alpha}$.
With this metric, the most overlapping journals are Bratislava Medical J.,
Quality and Quantity, and Harvard Business Review – tiny journals with only
around $10^{-4}$ percent of the total citation flow. To highlight prominent,
multidisciplinary journals and mesoscale changes in the citation flows, we
weigh each journal’s effective number of research fields with its total
citation flow $\pi_{i}=\sum_{\alpha}\pi_{i\alpha}$ for a weighted overlap

$o_{i}=r_{i}\pi_{i}.$ (5)

The journals with the highest weighted overlap are Nature, Science, and PNAS
(Fig. 6).

The life sciences contain more of the multidisciplinary citation flow than the
other research areas. By aggregating the weighted overlap $o_{i}$ on the leaf
modules $m$,

$o_{m}=\sum_{i\in m}o_{i},$ (6)

around 60 percent of the 1000 most overlapping leaf modules are in the life
sciences, followed by the physical sciences with 18 percent.

### Collaboration hypergraph using different representations

(a)

(b)

(c)

\begin{overpic}[width=390.25534pt]{figs/hypergraph-color.pdf}
\put(0.0,23.0){\small{{a}}} \put(29.0,23.0){\small{{b}}}
\put(64.0,23.0){\small{{c}}} \end{overpic}

Figure 7: Schematic hypergraph with edge-dependent node weights (a) and flow-
equivalent network representations. b) A bipartite representation where
hyperedges form hyperedge-nodes connecting all nodes in the hyperedge. c) A
multilayer representation where each hyperedge forms a layer containing the
hyperedge’s nodes. The figure is adapted from Ref. 38, licensed under CC BY
4.0.

Finally, we study how a hypergraph’s different first-order and multilayer
network representations affect the detected communities. We use a
collaboration hypergraph extracted from the 734 references in the review
article “Networks beyond pairwise interactions: structure and dynamics.”38, 39
The referenced articles form hyperedges linking their authors. These
hyperedges overlap in those authors who authored multiple papers, with the
largest connected component containing 361 author nodes in 220 hyperedges.

The hypergraph has article hyperedge weights $w(e)=\ln(c+1)+1$ where $c$ is
the number of citations for that article in December 2020.38 To model the
author’s unequal contributions to articles, we use hyperedge-dependent node
weights40

$\gamma_{e}(i)=\begin{cases}2\quad\text{if $i$ is first or last author},\\\
1\quad\text{otherwise.}\end{cases}$ (7)

We weigh alphabetically sorted authors uniformly because their contributions
are hard to determine.

From this hypergraph, we generate bipartite and multilayer hypergraph
representations with identical node visit rates using the method described in
Ref. 38 (Fig. 7). We also generate a multilayer network using a so-called
hyperedge-similarity model that increases the probability of a random walk
staying among similar hyperedges.38 This model reinforces community structure
with modules formed by similar sets of collaborators. We let Infomap search
for optimal multilevel solutions in the three network representations. As
before, we create pseudo-state nodes in the bipartite network to match them
with the multilayer networks’ state nodes.

The resulting partitions have effectively three or four levels. The top-level
organization is most coarse-grained for the bipartite representation and most
fine-grained for the hyperedge-similarity representation (Fig. 8). Only the
multilayer representation assigns the submodule “Peixoto” together with the
top module in which Bianconi is the highest-ranking author. It also assigns
Fortunato to a different top module than the hyperedge-similarity partition.
Finally, Bocaletti overlaps as the highest-ranking author in two submodules in
the hyperedge-similarity partition in the same top module as Bianconi.

Figure 8: Network science collaboration hypergraph represented with two visit-
rate-equivalent networks and a model that favors flow staying inside similar
hyperedges. Modules are sorted to minimize overlap and show the names of their
highest-ranking researchers. Here, we show the second-deepest level. Author
groups that change top-level assignments in different networks are
highlighted.

## Conclusions

We have extended alluvial diagrams to higher-order networks with multilevel
and overlapping communities and implemented an interactive web application
available for anyone to use. In three case studies, we have used alluvial
diagrams to show how the multilevel organization of science changes over time,
how a second-order model compares to a first-order model, and how different
hypergraph-flow equivalent networks influence the flow of ideas among network
scientists.

We have focused on flow-based community detection using the map equation
framework and the search algorithm Infomap. The generalized alluvial diagrams
apply to any community-detection algorithm and are particularly relevant for
simplifying and highlighting complex multilevel and overlapping modular
descriptions of large higher-order networks.

## Data and source code availability

The interactive web application is available at
https://www.mapequation.org/alluvial, and its source code at
https://github.com/mapequation/alluvial-generator. The multilevel significance
clustering code is available at https://github.com/mapequation/multilevel-
significance-clustering. All other relevant data and code are available at
https://github.com/mapequation/mapping-change-2.

## Author contributions

A.H. and M.R. devised the study. A.H. performed the experiments. A.H. and D.E.
implemented the interactive web application. A.H. and M.R. wrote the
manuscript. All authors edited and accepted the manuscript in its final form.

## Competing interests

The authors declare that they have no competing interests.

###### Acknowledgements.

A.H. was supported by the Swedish Foundation for Strategic Research, Grant No.
SB16-0089. D.E. and M.R. were supported by the Swedish Research Council
(2016-00796).

## References

  * Edler et al. [2017a] D. Edler, T. Guedes, A. Zizka, M. Rosvall, and A. Antonelli, Systematic biology 66, 197 (2017a).
  * Calatayud et al. [2020] J. Calatayud, E. Andivia, A. Escudero, C. J. Melián, R. Bernardo-Madrid, M. Stoffel, C. Aponte, N. G. Medina, R. Molina-Venegas, X. Arnan, et al., Nature ecology & evolution 4, 40 (2020).
  * Farage et al. [2021] C. Farage, D. Edler, A. Eklöf, M. Rosvall, and S. Pilosof, Methods in Ecology and Evolution 12, 778 (2021).
  * Calatayud et al. [2021] J. Calatayud, M. Neuman, A. Rojas, A. Eriksson, and M. Rosvall, eLife 10 (2021).
  * Neuman [2022] M. Neuman, Plos one 17, e0267040 (2022).
  * Edler et al. [2022a] D. Edler, A. Holmgren, A. Rojas, M. Rosvall, and A. Antonelli (2022a).
  * Rojas et al. [2022] A. Rojas, A. Eriksson, M. Neuman, D. Edler, C. Blocker, and M. Rosvall, bioRxiv (2022).
  * Rosvall and Bergstrom [2008] M. Rosvall and C. T. Bergstrom, Proceedings of the National Academy of Sciences 105, 1118 (2008).
  * Fortunato [2010] S. Fortunato, Physics reports 486, 75 (2010).
  * Schaub et al. [2017] M. T. Schaub, J.-C. Delvenne, M. Rosvall, and R. Lambiotte, Applied network science 2, 1 (2017).
  * Traag et al. [2019] V. A. Traag, L. Waltman, and N. J. Van Eck, Scientific reports 9, 1 (2019).
  * Peixoto [2019] T. P. Peixoto, Advances in network clustering and blockmodeling pp. 289–332 (2019).
  * Danon et al. [2005] L. Danon, A. Diaz-Guilera, J. Duch, and A. Arenas, Journal of statistical mechanics: Theory and experiment 2005, P09008 (2005).
  * Amelio and Pizzuti [2017] A. Amelio and C. Pizzuti, Computational Intelligence 33, 579 (2017).
  * Newman et al. [2020] M. E. Newman, G. T. Cantwell, and J.-G. Young, Physical Review E 101, 042304 (2020).
  * Rosvall and Bergstrom [2010] M. Rosvall and C. T. Bergstrom, PloS one 5, e8694 (2010).
  * Liu et al. [2013] X. Liu, B. Derudder, G. Csomós, and P. Taylor, Environment and Planning A 45, 1005 (2013).
  * Ruan et al. [2017] W. Ruan, H. Hou, and Z. Hu, Journal of Data and Information Science 2, 37 (2017).
  * Pal et al. [2022] R. Pal, H. Chopra, R. Awasthi, H. Bandhey, A. Nagori, T. Sethi, et al., Journal of medical Internet research 24, e34067 (2022).
  * Remy et al. [2017] C. Remy, B. Rym, and L. Matthieu, in _International conference on complex networks and their applications_ (Springer, 2017), pp. 166–177.
  * Petrun Sayers et al. [2021] E. L. Petrun Sayers, A. M. Parker, R. Seelam, and M. L. Finucane, Journal of Contingencies and Crisis Management 29, 342 (2021).
  * Kivelä et al. [2014] M. Kivelä, A. Arenas, M. Barthelemy, J. P. Gleeson, Y. Moreno, and M. A. Porter, Journal of complex networks 2, 203 (2014).
  * Rosvall et al. [2014] M. Rosvall, A. V. Esquivel, A. Lancichinetti, J. D. West, and R. Lambiotte, Nature communications 5, 1 (2014).
  * De Domenico et al. [2015] M. De Domenico, A. Lancichinetti, A. Arenas, and M. Rosvall, Physical Review X 5, 011027 (2015).
  * De Domenico et al. [2016] M. De Domenico, C. Granell, M. A. Porter, and A. Arenas, Nature Physics 12, 901 (2016).
  * Xu et al. [2016] J. Xu, T. L. Wickramarathne, and N. V. Chawla, Science advances 2, e1600028 (2016).
  * Lambiotte et al. [2019] R. Lambiotte, M. Rosvall, and I. Scholtes, Nature physics 15, 313 (2019).
  * Rosvall and Bergstrom [2011] M. Rosvall and C. T. Bergstrom, PloS one 6, e18209 (2011).
  * Peixoto [2014] T. P. Peixoto, Physical Review X 4, 011047 (2014).
  * Holmgren et al. [2022a] A. Holmgren, D. Edler, and M. Rosvall, _The MapEquation Alluvial Diagram Generator_ (2022a), URL https://mapequation.org/alluvial.
  * Edler et al. [2022b] D. Edler, A. Holmgren, and M. Rosvall, _The MapEquation software package_ (2022b), URL https://mapequation.org.
  * Edler et al. [2017b] D. Edler, L. Bohlin, et al., Algorithms 10, 112 (2017b).
  * Zakai [2011] A. Zakai, in _Proceedings of the ACM international conference companion on Object oriented programming systems languages and applications companion_ (2011), pp. 301–312.
  * Holmgren et al. [2022b] A. Holmgren, D. Edler, and M. Rosvall, _Infomap Online_ (2022b), URL https://mapequation.org/infomap.
  * Lambiotte and Rosvall [2012] R. Lambiotte and M. Rosvall, Phys. Rev. E 85, 056107 (2012).
  * Persson et al. [2016] C. Persson, L. Bohlin, D. Edler, and M. Rosvall, arXiv preprint arXiv:1606.08328 (2016).
  * Wang and Waltman [2016] Q. Wang and L. Waltman, Journal of informetrics 10, 347 (2016).
  * Eriksson et al. [2021] A. Eriksson, D. Edler, A. Rojas, M. de Domenico, and M. Rosvall, Communications Physics 4, 1 (2021).
  * Battiston et al. [2020] F. Battiston, G. Cencetti, I. Iacopini, V. Latora, M. Lucas, A. Patania, J.-G. Young, and G. Petri, Physics Reports 874, 1 (2020).
  * Chitra and Raphael [2019] U. Chitra and B. Raphael, in _International Conference on Machine Learning_ (PMLR, 2019), pp. 1172–1181.

##  SI Supplementary information

###  1 Input formats

The alluvial diagram generator accepts the following input formats: clu, tree,
and json (LABEL:lst:clu, LABEL:lst:clu_states, LABEL:lst:clu_multilayer,
LABEL:lst:tree, LABEL:lst:tree_states, LABEL:lst:tree_multilayer,
LABEL:lst:json, LABEL:lst:json_states and LABEL:lst:json_multilayer). It also
accepts the ftree format, which is the same as the tree format with aggregated
intra-module links, which are not used by the web application. In addition, it
also understands any network format readable by Infomap and any combinations
of the above files compressed as a zip file.

The “flow” column in the clu format can be substituted with any node weighting
scheme to make the web application available to more researchers.

Listing S1: clu format

⬇

# node_id module flow

1 1 0.214286

2 1 0.142857

3 1 0.142857

4 2 0.214286

5 2 0.142857

6 2 0.142857

Listing S2: clu states format

⬇

# state_id module flow node_id

1 1 0.166667 1

2 1 0.166667 2

3 1 0.166667 3

4 2 0.166667 1

5 2 0.166667 4

6 2 0.166667 5

Listing S3: clu multilayer format

⬇

# state_id module flow node_id layer_id

3 1 0.166667 1 2

4 1 0.166667 2 2

5 1 0.166667 3 2

0 2 0.166667 1 1

1 2 0.166667 4 1

2 2 0.166667 5 1

Listing S4: tree format

⬇

# path flow name node_id

1:1 0.214286 "1" 1

1:2 0.142857 "2" 2

1:3 0.142857 "3" 3

2:1 0.214286 "4" 4

2:2 0.142857 "5" 5

2:3 0.142857 "6" 6

Listing S5: tree states format

⬇

# path flow name state_id node_id

1:1 0.166667 "i" 1 1

1:2 0.166667 "j" 2 2

1:3 0.166667 "k" 3 3

2:1 0.166667 "i" 4 1

2:2 0.166667 "l" 5 4

2:3 0.166667 "m" 6 5

Listing S6: tree multilayer format

⬇

# path flow name state_id node_id layer_id

1:1 0.166667 "i" 3 1 2

1:2 0.166667 "j" 4 2 2

1:3 0.166667 "k" 5 3 2

2:1 0.166667 "i" 0 1 1

2:2 0.166667 "l" 1 4 1

2:3 0.166667 "m" 2 5 1

Listing S7: json format

⬇

{

"nodes": [

{ "path": [1, 1], "name": "1", "flow": 0.214286, "id": 1 },

{ "path": [1, 2], "name": "2", "flow": 0.142857, "id": 2 },

{ "path": [1, 3], "name": "3", "flow": 0.142857, "id": 3 },

{ "path": [2, 1], "name": "4", "flow": 0.214286, "id": 4 },

{ "path": [2, 2], "name": "5", "flow": 0.142857, "id": 5 },

{ "path": [2, 3], "name": "6", "flow": 0.142857, "id": 6 }

]

}

Listing S8: json states format

⬇

{

"nodes": [

{ "path": [1, 1], "name": "i", "flow": 0.166667, "stateId": 1, "id": 1 },

{ "path": [1, 2], "name": "j", "flow": 0.166667, "stateId": 2, "id": 2 },

{ "path": [1, 3], "name": "k", "flow": 0.166667, "stateId": 3, "id": 3 },

{ "path": [2, 1], "name": "i", "flow": 0.166667, "stateId": 4, "id": 1 },

{ "path": [2, 2], "name": "l", "flow": 0.166667, "stateId": 5, "id": 4 },

{ "path": [2, 3], "name": "m", "flow": 0.166667, "stateId": 6, "id": 5 }

]

}

Listing S9: json multilayer format

⬇

{

"nodes": [

{ "path": [1, 1], "name": "i", "flow": 0.166667,

"stateId": 3, "layerId": 2, "id": 1 },

{ "path": [1, 2], "name": "j", "flow": 0.166667,

"stateId": 4, "layerId": 2, "id": 2 },

{ "path": [1, 3], "name": "k", "flow": 0.166667,

"stateId": 5, "layerId": 2, "id": 3 },

{ "path": [2, 1], "name": "i", "flow": 0.166667,

"stateId": 0, "layerId": 1, "id": 1 },

{ "path": [2, 2], "name": "l", "flow": 0.166667,

"stateId": 1, "layerId": 1, "id": 4 },

{ "path": [2, 3], "name": "m", "flow": 0.166667,

"stateId": 2, "layerId": 1, "id": 5 }

]

}

###  2 Supplementary figures

Figure S1: Example session of the alluvial diagram generator. The main diagram
view can be zoomed in by scrolling in and out. Clicking any empty area and
dragging pans the view. Clicking any module (dark rectangles) selects it.
Double-clicking a module (keyboard shortcut E) expands and shows its
submodules if they exist. Holding the shift key while double-clicking a
submodule (keyboard shortcut C) contracts and regroups the submodules’
siblings into their super-module. A selected module can be moved around with
the W and S keys, and networks can be re-ordered left-to-right with the A and
D keys. The sidebar to the right contains all settings and controls, some
available only when a module is selected by clicking on it. From top to
bottom: “Load or arrange” opens the dialogue box in Fig 3. “Help” displays a
help dialogue. “Colors” allows the user to color all or selected modules with
the chosen color scheme. “Module” contains information about the currently
selected module. “Layout” controls various diagram layout settings, such as
size, module order, font sizes, etc. Finally, “Export” allows the user to
export the diagram to an SVG file. Figure S2: Alluvial diagram object model.
Each network partition is modeled as a Network whose children are Modules. To
allow highlighting individual nodes, we divide each module into many
HighlightGroups. To connect stream fields between HighlightGroups in different
Networks, each HighlightGroup has two Branches, left and right, each
containing as many StreamLineNodes as there are connected stream fields.
StreamLineNodes contain many LeafNodes, representing the original nodes in the
network. Finally, StreamLineLinks connect StreamLineNodes in different
Networks.