WP3: Multilayer Network Visualizations

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

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. 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.

• 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.

—

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

Back to home page