Unweighted multilayer networks

In elementary network theory, a network is represented by a graph ${\displaystyle G=(V,E)}$ in which ${\displaystyle V}$ is the set of nodes and ${\displaystyle E}$ the links between nodes, typically represented as a tuple of nodes ${\displaystyle u,v\in V}$. While this basic formalization is useful for analyzing many systems, real world networks often have added complexity in the form of multiple types of relations between system elements. An early formalization of this idea came through its application in the field of social network analysis (see, e.g.,^[33] and papers on relational algebras in social networks) in which multiple forms of social connection between people were represented by multiple types of links.^[34]

To accommodate the presence of more than one type of link, a multidimensional network is represented by a triple ${\displaystyle G=(V,E,D)}$, where ${\displaystyle D}$ is a set of dimensions (or layers), each member of which is a different type of link, and ${\displaystyle E}$ consists of triples ${\displaystyle (u,v,d)}$ with ${\displaystyle u,v\in V}$ and ${\displaystyle d\in D}$.^[6]

Note that as in all directed graphs, the links ${\displaystyle (u,v,d)}$ and ${\displaystyle (v,u,d)}$ are distinct.

By convention, the number of links between two nodes in a given dimension is either 0 or 1 in a multidimensional network. However, the total number of links between two nodes across all dimensions is less than or equal to ${\displaystyle |D|}$.

Weighted multilayer networks

In the case of a weighted network, this triplet is expanded to a quadruplet ${\displaystyle e=(u,v,d,w)}$, where ${\displaystyle w}$ is the weight on the link between ${\displaystyle u}$ and ${\displaystyle v}$ in the dimension ${\displaystyle d}$.

The multiplex network of European airports. Each airline denotes a different layer. Visualization made with the muxViz software

Further, as is often useful in social network analysis, link weights may take on positive or negative values. Such signed networks can better reflect relations like amity and enmity in social networks.^[31] Alternatively, link signs may be figured as dimensions themselves,^[35] e.g. ${\displaystyle G=(V,E,D)}$ where ${\displaystyle D=\{-1,0,1\}}$ and ${\displaystyle E=\{(u,v,d);u,v\in V,d\in D\}}$ This approach has particular value when considering unweighted networks.

This conception of dimensionality can be expanded should attributes in multiple dimensions need specification. In this instance, links are n-tuples ${\displaystyle e=(u,v,d_{1}\dots d_{n-2})}$. Such an expanded formulation, in which links may exist within multiple dimensions, is uncommon but has been used in the study of multidimensional time-varying networks.^[36]

The World Economic Forum map of global risks and global trends, modeled as an interdependent network (also known as network of networks).

General formulation in terms of tensors

Whereas unidimensional networks have two-dimensional adjacency matrices of size ${\displaystyle V\times V}$, in a multidimensional network with ${\displaystyle D}$ dimensions, the adjacency matrix becomes a multilayer adjacency tensor, a four-dimensional matrix of size ${\displaystyle (V\times D)\times (V\times D)}$.^[3] By using index notation, adjacency matrices can be indicated by ${\displaystyle A_{j}^{i}}$, to encode connections between nodes ${\displaystyle i}$ and ${\displaystyle j}$, whereas multilayer adjacency tensors are indicated by ${\displaystyle M_{j\beta }^{i\alpha }}$, to encode connections between node ${\displaystyle i}$ in layer ${\displaystyle \alpha }$ and node ${\displaystyle j}$ in layer ${\displaystyle \beta }$. As in unidimensional matrices, directed links, signed links, and weights are all easily accommodated by this framework.

In the case of multiplex networks, which are special types of multilayer networks where nodes can not be interconnected with other nodes in other layers, a three-dimensional matrix of size ${\displaystyle (V\times V)\times D}$ with entries ${\displaystyle A_{ij}^{\alpha }}$ is enough to represent the structure of the system^[8][37] by encoding connections between nodes ${\displaystyle i}$ and ${\displaystyle j}$ in layer ${\displaystyle \alpha }$.

The multiplex social network of Star Wars saga. Each layer denotes a different episode and two nodes are connected each other if the corresponding characters acted together in one or more scenes. Visualization made with muxViz software

Multi-layer neighbors

In a multidimensional network, the neighbors of some node ${\displaystyle v}$ are all nodes connected to ${\displaystyle v}$ across dimensions.

Multi-layer path length

A path between two nodes in a multidimensional network can be represented by a vector r ${\displaystyle =(r_{1},\dots r_{|D|})}$ in which the ${\displaystyle i}$th entry in r is the number of links traversed in the ${\displaystyle i}$th dimension of ${\displaystyle G}$.^[38] As with overlapping degree, the sum of these elements can be taken as a rough measure of a path length between two nodes.

Network of layers

The existence of multiple layers (or dimensions) allows to introduce the new concept of network of layers,^[3] peculiar of multilayer networks. In fact, layers might be interconnected in such a way that their structure can be described by a network, as shown in the figure.

Network of layers in multilayer systems

The network of layers is usually weighted (and might be directed), although, in general, the weights depends on the application of interest. A simple approach is, for each pair of layers, to sum all of the weights in the connections between their nodes to obtain edge weights that can be encoded into a matrix ${\displaystyle q_{\alpha \beta }}$. The rank-2 adjacency tensor, representing the underlying network of layers in the space ${\displaystyle \mathbb {R} ^{L\times L}}$ is given by

${\displaystyle \Psi _{\delta }^{\gamma }=\sum \limits _{\alpha ,\beta =1}^{L}q_{\alpha \beta }E_{\delta }^{\gamma }(\alpha \beta )}$

where ${\displaystyle E_{\delta }^{\gamma }(\alpha \beta )}$ is the canonical matrix with all components equal to zero except for the entry corresponding to row ${\displaystyle \alpha }$ and column ${\displaystyle \beta }$, that is equal to one. Using the tensorial notation, it is possible to obtain the (weighted) network of layers from the multilayer adjacency tensor as ${\displaystyle \Psi _{\delta }^{\gamma }=M_{j\delta }^{i\gamma }U_{i}^{j}}$.^[3]

Degree

In a non-interconnected multidimensional network, where interlayer links are absent, the degree of a node is represented by a vector of length ${\displaystyle |D|:\mathbf {k} =(k_{i}^{1},\dots k_{i}^{|D|})}$. Here ${\displaystyle |D|}$ is an alternative way to denote the number of layers ${\displaystyle L}$ in multilayer networks. However, for some computations it may be more useful to simply sum the number of links adjacent to a node across all dimensions.^[3][39] This is the overlapping degree:^[4] ${\displaystyle \sum _{\alpha =1}^{|D|}k_{i}^{\alpha }}$. As with unidimensional networks, distinction may similarly be drawn between incoming links and outgoing links. If interlayer links are present, the above definition must be adapted to account for them, and the multilayer degree is given by

${\displaystyle k^{i}=M_{j\beta }^{i\alpha }U_{\alpha }^{\beta }u^{j}=\sum _{\alpha ,\beta =1}^{L}\sum _{j=1}^{N}M_{j\beta }^{i\alpha }}$

where the tensors ${\displaystyle U_{\alpha }^{\beta }}$ and ${\displaystyle u^{j}}$ have all components equal to 1. The heterogeneity in the number of connections of a node across the different layers can be taken into account through the participation coefficient.^[4]

Versatility as multilayer centrality

When extended to interconnected multilayer networks, i.e. those systems where nodes are connected across layers, the concept of centrality is better understood in terms of versatility.^[10] Nodes that are not central in each layer might be the most important for the multilayer systems in certain scenarios. For instance, this is the case where two layers encode different networks with only one node in common: it is very likely that such a node will have the highest centrality score because it is responsible for the information flow across layers.

Modularity maximization

A generalization of the well-known modularity maximization method for community discovery has been originally proposed by Mucha et al.^[8] This multiresolution method assumes a three-dimensional tensor representation of the network connectivity within layers, as for edge-colored multigraphs, and a three-dimensional tensor representation of the network connectivity across layers. It depends on the resolution parameter ${\displaystyle \gamma }$ and the weight ${\displaystyle \omega }$ of interlayer connections. In a more compact notation, making use of the tensorial notation, modularity can be written as ${\displaystyle Q\propto S_{i\alpha }^{a}B_{j\beta }^{i\alpha }S_{a}^{j\beta }}$, where ${\displaystyle B_{j\beta }^{i\alpha }=M_{j\beta }^{i\alpha }-P_{j\beta }^{i\alpha }}$, ${\displaystyle M_{j\beta }^{i\alpha }}$ is the multilayer adjacency tensor, ${\displaystyle P_{j\beta }^{i\alpha }}$ is the tensor encoding the null model and the value of components of ${\displaystyle S_{a}^{i\alpha }}$ is defined to be 1 when a node ${\displaystyle i}$ in layer ${\displaystyle \alpha }$ belongs to a particular community, labeled by index ${\displaystyle a}$, and 0 when it does not.^[3]

Tensor decomposition

Non-negative matrix factorization has been proposed to extract the community-activity structure of temporal networks.^[46] The multilayer network is represented by a three-dimensional tensor ${\displaystyle T_{ij}^{\tau }}$, like an edge-colored multigraph, where the order of layers encode the arrow of time. Tensor factorization by means of Kruskal decomposition is thus applied to ${\displaystyle T_{ij}^{\tau }}$ to assign each node to a community across time.

Statistical inference

Methods based on statistical inference, generalizing existing approaches introduced for unidimensional networks, have been proposed. Stochastic block model is the most used generative model, appropriately generalized to the case of multilayer networks.^[47][48]

As for unidimensional networks, principled methods like minimum description length can be used for model selection in community detection methods based on information flow.^[9]

Degree correlations

The question of degree correlations in unidimensional networks is fairly straightforward: do networks of similar degree tend to connect to each other? In multidimensional networks, what this question means becomes less clear. When we refer to a node's degree, are we referring to its degree in one dimension, or collapsed over all? When we seek to probe connectivity between nodes, are we comparing the same nodes across dimensions, or different nodes within dimensions, or a combination?^[6] What are the consequences of variations in each of these statistics on other network properties? In one study, assortativity was found to decrease robustness in a duplex network.^[50]

Path dominance

Given two multidimensional paths, r and s, we say that r dominates s if and only if: ${\displaystyle \forall d\in \langle 1,|D|\rangle ,r_{l}\leq s_{l}}$ and ${\displaystyle \exists i}$ such that ${\displaystyle r_{l}<s_{l}}$.^[38]

Shortest path discovery

Among other network statistics, many centrality measures rely on the ability to assess shortest paths from node to node. Extending these analyses to a multidimensional network requires incorporating additional connections between nodes into the algorithms currently used (e.g., Dijkstra's). Current approaches include collapsing multi-link connections between nodes in a preprocessing step before performing variations on a breadth-first search of the network.^[28]

Multidimensional distance

One way to assess the distance between two nodes in a multidimensional network is by comparing all the multidimensional paths between them and choosing the subset that we define as shortest via path dominance: let ${\displaystyle MP(u,v)}$ be the set of all paths between ${\displaystyle u}$ and ${\displaystyle v}$. Then the distance between ${\displaystyle u}$ and ${\displaystyle v}$ is a set of paths ${\displaystyle P\subseteq MP}$ such that ${\displaystyle \forall p\in P,\nexists p'\in MP}$ such that ${\displaystyle p'}$ dominates ${\displaystyle p}$. The length of the elements in the set of shortest paths between two nodes is therefore defined as the multidimensional distance.^[38]

Dimension relevance

In a multidimensional network ${\displaystyle G=(V,E,D)}$, the relevance of a given dimension (or set of dimensions) ${\displaystyle D'}$ for one node can be assessed by the ratio: ${\displaystyle {\frac {{\text{Neighbors}}(v,D')}{{\text{Neighbors}}(v,D)}}}$.^[39]

Dimension connectivity

In a multidimensional network in which different dimensions of connection have different real-world values, statistics characterizing the distribution of links to the various classes are of interest. Thus it is useful to consider two metrics that assess this: dimension connectivity and edge-exclusive dimension connectivity. The former is simply the ratio of the total number of links in a given dimension to the total number of links in every dimension: ${\displaystyle {\frac {|\{(u,v,d)\in E|u,v\in V\}|}{|E|}}}$. The latter assesses, for a given dimension, the number of pairs of nodes connected only by a link in that dimension: ${\displaystyle {\frac {|\{(u,v,d)\in E|u,v\in V\wedge \forall j\in D,j\neq d:(u,v,j)\notin E\}|}{|\{(u,v,d)\in E|u,v\in V\}|}}}$.^[39]

Burst detection

Burstiness is a well-known phenomenon in many real-world networks, e.g. email or other human communication networks. Additional dimensions of communication provide a more faithful representation of reality and may highlight these patterns or diminish them. Therefore, it is of critical importance that our methods for detecting bursty behavior in networks accommodate multidimensional networks.^[51]

Random walks

As for unidimensional networks, it is possible to define random walks on the top of multilayer systems. However, given the underlying multilayer structure, random walkers are not limited to move from one node to another within the same layer (jump), but are also allowed to move across layers (switch).^[15]

Random walks can be used to explore a multilayer system with the ultimate goal to unravel its mesoscale organization, i.e. to partition it in communities,^[8][9] and have been recently used to better understand navigability of multilayer networks and their resilience to random failures,^[15] as well as for exploring efficiently this type of topologies.^[54]

In the case of interconnected multilayer systems, the probability to move from a node ${\displaystyle i}$ in layer ${\displaystyle \alpha }$ to node ${\displaystyle j}$ in layer ${\displaystyle \beta }$ can be encoded into the rank-4 transition tensor ${\displaystyle T_{j\beta }^{i\alpha }}$ and the discrete-time walk can be described by the master equation

${\displaystyle p_{j\beta }(t+1)=\sum _{\alpha =1}^{L}\sum _{i=1}^{N}T_{j\beta }^{i\alpha }p_{i\alpha }(t)=\sum _{\alpha =1}^{L}\sum _{i=1}^{N}(T^{t})_{j\beta }^{i\alpha }p_{i\alpha }(0)}$

where ${\displaystyle p_{i\alpha }(t)}$ indicates the probability of finding the walker in node ${\displaystyle i}$ in layer ${\displaystyle \alpha }$ at time ${\displaystyle t}$.^[3][15]

There are many different types of walks that can be encoded into the transition tensor ${\displaystyle T_{j\beta }^{i\alpha }}$, depending on how the walkers are allowed to jump and switch. For instance, the walker might either jump or switch in a single time step without distinguishing between inter- and intra-layer links (classical random walk), or it can choose either to stay in the current layer and jump, or to switch layer and then jump to another node in the same time step (physical random walk). More complicated rules, corresponding to specific problems to solve, can be found in the literature.^[23] In some cases, it is possible to find, analytically, the stationary solution of the master equation.^[15][54]

Classical diffusion

The problem of classical diffusion in complex networks is to understand how a quantity will flow through the system and how much time it will take to reach the stationary state. Classical diffusion in multiplex networks has been recently studied by introducing the concept of supra-adjacency matrix,^[55] later recognized as a special flattening of the multilayer adjacency tensor.^[3] In tensorial notation, the diffusion equation on the top of a general multilayer system can be written, concisely, as

${\displaystyle {\frac {dX_{j\beta }(t)}{dt}}=-L_{j\beta }^{i\alpha }X_{i\alpha }(t)}$

where ${\displaystyle X_{i\alpha }(t)}$ is the amount of diffusing quantity at time ${\displaystyle t}$ in node ${\displaystyle i}$ in layer ${\displaystyle \alpha }$. The rank-4 tensor governing the equation is the Laplacian tensor, generalizing the combinatorial Laplacian matrix of unidimensional networks. It is worth remarking that in non-tensorial notation, the equation takes a more complicated form.

Many of the properties of this diffusion process are completely understood in terms of the second smallest eigenvalue of the Laplacian tensor. It is interesting that diffusion in a multiplex system can be faster than diffusion in each layer separately, or in their aggregation, provided that certain spectral properties are satisfied.^[55]

Information and epidemics spreading

Recently, how information (or diseases) spread through a multilayer system has been the subject of intense research. ^{[56][1] [57][58][59]}