# WP3: Multilayer Network Visualizations

### General considerations on multilayer networks

This paragraph might be of interest to WP2 concerned with data structures relevant to design and implementing VA for multilayer networks.

#### Labeled graphs

This section presents the general notion of *labeled graphs*. This notion appears to be quite general and, in a sense, universal as it captures a set of definitions that have been proposed in the literature under different names: multiplex, multivariate or multi-dimensional networks to name just a few.

A *labeled graph* is a graph $G = (V, E)$ gathering *nodes* $V$ and *edges* $E$. Edges can be directed or non-directed. We moreover consider $G$ to be equipped with maps $f: V \to \cal X$ assigning nodes values taken in any sets $\cal X$. The graph $G$ can be equipped with multiple maps $f, f', f'', \ldots$. The set $\cal X$ can be any set, finite or infinite, countable (like $\mathbb N$) or non countable (like $\mathbb R$). We may use the term *node property* to denote a map $f: V \to \cal X$ (or a specific value $f(u)$ assigned to node $u$).

Edge properties $g: E \to \cal Y$ are defined similarly.

The goal of this section is to show that any and all proposed definitions for multiplex, multi-layer or multivariate networks fall under the scope of labeled graphs. This has a number of consequences.

- Labeled graphs turn out to be a useful conceptual approach and unifying abstraction – they actually can be found in the literature and in many areas of mathematics and computer science.
- Combinatorics use the notion of a labeled graph to denote graphs for which nodes are assigned integer values. Labeled graphs are then used to specify and solve enumerative and structural combinatorial problems (Gallian 2014).
- Conceptual graphs are labeled graphs supporting reasoning, where graphs can be seen as logical statements (Chein Mugnier 2009).
- Graph rewriting systems use labeled graph to specify node properties on which local rules match and act (Andrei Kirchner 2008).
- Numerous application domains use labeled graph – sometimes implicitly – to model phenomenon they study.
- Etc.

- Labeled graphs also offer a useful and flexible data structure.
- Most graph database systems actually implement (store and search) property based graphs.
- Most graph computation and visualization framework implement property based graphs (Angles Gutierrez 2008) (Angles 2012) (Webber 2012).

#### Kivelä et al. multilayer networks

(Kivelä et al. 2014) surveys the literature on *multilayer networks*. Kivelä considers nodes and edges as belonging to layers, although edges can connect nodes *between* layers. They also consider different *sets of layers*, $L_1, L_2, \ldots, L_d$. In other words, a node $u$ may be considered to have type $\alpha_1$ with respect to layer $L_1$, type $\alpha_2$ with respect to type $L_2$, and so forth.

In this setting we are brought to consider nodes $V_M$ as a subset of the cartesian product $V_M \subset V \times L_1 \times \cdots \times L_d$. That being said, the idea still is to think as $u \in V$ *as a node belonging to different layers*.

- The above definition allows a node $u$ to be mapped to several distinct tuples $(u, \alpha_1, \alpha_2, \ldots, \alpha_d)$ and $(u, \alpha'_1, \alpha'_2, \ldots, \alpha'_d)$. That is, a node does not necessarily have to be of
*one*type with respect to layer $L_i$, but may well be of type $\alpha_i$ and $\alpha'_i$. - More precisely, if $u$ appears in both $(u, \alpha_1, \alpha_2, \ldots, \alpha_d)$ and $(u, \alpha'_1, \alpha'_2, \ldots, \alpha'_d)$ then node $u$ may be considered to have type $\alpha_2$ on layer $L_2$ when it simultaneously has type $\alpha_1$ on layer $L_1$ while having type $\alpha'_2$ on layer $L_2$ when it simultaneously has type $\alpha'_1$ on layer $L_1$.

As a consequence, we cannot properly define a map from $V$ to $V_M$. Kivelä indeed considers a (usual) graph on the set $V_M$ with edges connecting tuples $(u, \alpha_1, \ldots, \alpha_d)$, $(v, \beta_1, \ldots, \beta_d)$. Different mappings can be defined on the graph $(V_M, E_M)$ to handle it in terms of the original nodes in $V$.

- The natural projection $\pi_V: V_M \to V$ identifies the node part of a tuple.
- Similarly, the natural projection $\pi_i: V_M \to 2^{L_i}$ computes the different values a node $u$ takes on layer $L_i$.
- Similar maps $\pi_{i,j}: V_M \to L_i \times L_j$ can be defined to obtain the simultaneous pairs of values on layers $L_i$ and $L_j$ assigned to node $u$.

That is to say, a *multilayer* graph in the sense of Kivelä is just a labeled graph: a usual graph $(V_M, E_M)$ equipped with several mappings. In this very special case, a series of mappings can be defined to recover the *semantics* Kivelä gives to the notion of a *layer*.

We now consider a series of special cases listed by Kivelä that he claims his general framework recovers.

#### References

- Andrei O., H. Kirchner (2008). A rewriting calculus for multigraphs with ports. Electronic Notes in Theoretical Computer Science, 219:67–82.
- Angles R. (2012). A comparison of current graph database models. In IEEE 28th International Conference on Data Engineering Workshops (ICDEW), pages 171–177.
- Angles R., C. Gutierrez (2008). Survey of graph database models. ACM Computing Surveys, 40(1):1–39.
- Chein M., M.-L. Mugnier (2009). Graph-based Knowledge Representation: Computational Foundations of Conceptual Graphs. Advanced Information and Knowledge Processing. Springer.
- J. A. Gallian (2014). A dynamic survey of graph labeling. Electronic J. of Combinatorics, 17(DS6): 1–384.
- Kivelä, M. et al. (2014). “Multilayer networks.” Journal of Complex Networks 2(3): 203 - 271.
- Webber J. (2012). A programmatic introduction to Neo4j. In 3rd Annual Conf. on Systems, programming, and applications: software for humanity, pages 217–218. ACM.

—

### State of The Art Report(STAR) and Survey

As part of WP3 we will be delivering a STAR report and survey covering Multilayer Graph visualization.