The structure and dynamics of multilayer networks

Abstract

In the past years, network theory has successfully characterized the interaction among the constituents of a variety of complex systems, ranging from biological to technological, and social systems. However, up until recently, attention was almost exclusively given to networks in which all components were treated on equivalent footing, while neglecting all the extra information about the temporal- or context-related properties of the interactions under study. Only in the last years, taking advantage of the enhanced resolution in real data sets, network scientists have directed their interest to the multiplex character of real-world systems, and explicitly considered the time-varying and multilayer nature of networks. We offer here a comprehensive review on both structural and dynamical organization of graphs made of diverse relationships (layers) between its constituents, and cover several relevant issues, from a full redefinition of the basic structural measures, to understanding how the multilayer nature of the network affects processes and dynamics.

1 Introduction

1.1 The multilayer network approach to nature

If we just turn our eyes to the immense majority of phenomena that occur around us (from those influencing our social relationships, to those transforming the overall environment where we live, to even those affecting our own biological functioning), we realize immediately that they are nothing but the result of the emergent dynamical organization of systems that, on their turn, involve a multitude of basic constituents (or entities) interacting with each other via somehow complicated patterns.

One of the major effort of modern physics is then providing proper and suitable representations of these systems, where constituents are considered as nodes (or units) of a network, and interactions are modeled by links of that same network. Indeed, having such a representation in one hand and the arsenal of mathematical tools for extracting information in the other (as inherited by several gifted centuries of thoughts, concepts and activities in applied mathematics and statistical mechanics) is the only suitable way through which we can even dare to understand the observed phenomena, identify the rules and mechanisms that are lying behind them, and possibly control and manipulate them conveniently.

The last fifteen years have seen the birth of a movement in science, nowadays very well known under the name of complex networks theory. It involved the interdisciplinary effort of some of our best scientists in the aim of exploiting the current availability of big data in order to extract the ultimate and optimal representation of the underlying complex systems and mechanisms. The main goals were i) the extraction of unifying principles that could encompass and describe (under some generic and universal rules) the structural accommodation that is being detected ubiquitously, and ii) the modeling of the resulting emergent dynamics to explain what we actually see and experience from the observation of such systems.

It would look like even pleonastic to report here on each and every original work that was carried out in specific contexts under study (a reader, indeed, will find, along this review, all the relevant literature that was produced so far on this subject, properly addressed and organized in the different sections of the report). At this initial stage, instead, and together with the pioneering articles [1, 2, 3, 4] and classical books [5, 6, 7, 8] on complex networks, we address the interested reader to some other reports [9, 10, 11, 12, 13] that were published recently on this same Journal, which we believe may constitute very good guides to find orientation into the immensely vast literature on the subject. In particular, Ref. [9] is a complete compendium of the ideas and concepts involved in both structural and dynamical properties of complex networks, whereas Refs. [12, 13] have the merit of accompanying and orienting the reader through the relevant literature discussing modular networks [12], and space-embedded networks [13]. Finally, Refs. [10, 11] constitute important accounts on the state of the art for what concerns the study of synchronous organization of networking systems [11], and processes like evolutionary games on networks [10].

The traditional complex network approach to nature has mostly been concentrated to the case in which each system’s constituent (or elementary unit) is charted into a network node, and each unit-unit interaction is represented as being a (in general real) number quantifying the weight of the corresponding graph’s connection (or link). However, it is easy to realize that treating all the network’s links on such an equivalent footing is too big a constraint, and may occasionally result in not fully capturing the details present in some real-life problems, leading even to incorrect descriptions of some phenomena that are taking place on real-world networks.

The following three examples are representative, in our opinion, of the major limitation of that approach.

The first example is borrowed from sociology. Social networks analysis is one of the most used paradigms in behavioral sciences, as well as in economics, marketing, and industrial engineering [14], but some questions related to the real structure of social networks have been not properly understood. A social network can be described as a set of people (or groups of people) with some pattern of contacts or interactions between them [14, 15]. At a first glance, it seems natural to assume that all the connections or social relationships between the members of the network take place at the same level. But the real situation is far different. The actual relationships amongst the members of a social network take place (mostly) inside of different groups (levels or layers), and therefore they cannot be properly modeled if only the natural local-scale point of view used in classic complex network models is taken into account. Let us for a moment think to the problem of spreading of information, or rumors, on top of a social network like Facebook. There, all users can be seen as nodes of a graph, and all the friendships that users create may be considered as the network’s links. However, friendships in Facebook may result from relationships of very different origins: two Facebook’s users may share a friendship because they are colleagues in their daily occupations, or because they are fans of the same football team, or because they occasionally met during their vacation time in some resort, or for any other possible social reason. Now, suppose that a given user gets aware of a given information and wants to spread it to its Facebook’s neighborhood of friends. It is evident that the user will first select that subgroup of friends that he/she believes might be potentially interested to the specific content of the information, and only after will proceed with spreading it to that subgroup. As a consequence, representing Facebook as a unique network of acquaintances (and simulating there a classical diffusion model) would result in drawing incorrect conclusions and predictions of the real dynamics of the system. Rather, the correct way to proceed is instead to chart each social group into a different layer of interactions, and operating the spreading process separately on each layer. As we will see in Section 5, such a multilayer approach leads actually to a series of dramatic and important consequences.

A second paradigmatic example of intrinsically multirelational (or multiplex) systems is the situation that one has to tackle when trying to describe transportation networks, as for instance the Air Transportation Network (ATN) [16] or subway networks [17, 18]. In particular, the traditional study of ATN is by representing it as a single-layer network, where nodes represent airports, while links stand for direct flights between two airports. On the other hand, it is clear that a more accurate mapping is considering that each commercial airline corresponds instead to a different layer, containing all the connections operated by the same company. Indeed, let us suppose for a moment that one wants to make predictions on the propagation of the delays in the flight scheduling through the system, or the effects of such a dynamics on the movement of passengers [19]. In particular, Ref. [16] considered the problem of passenger rescheduling when a fraction of the ATN links, i.e. of flights, is randomly removed. It is well known that each commercial airline incurs in a rather high cost whenever a passenger needs to be rescheduled on a flight of another company, and therefore it tries first to reschedule the passenger by the use of the rest of its own network. As we will see in full details in Section 7, the proper framework where predictions about such dynamical processes can be made suitably is, in fact, considering the ATN as a fully multilayer structure.

Moving on to biology, the third example is the effort of scientists in trying to rank the importance of a specific component in a biological system. For instance, the Caenorhabditis elegans or C. elegans is a small nematode, and it is actually the first ever organism for which the entire genome was sequenced. Recently, biologists were even able to get a full mapping of the C. elegans’ neural network, which actually consists of 281 neurons and around two thousands of connections. On their turn, neurons can be connected either by a chemical link, or by an ionic channel, and the two types of connections have completely different dynamics. As a consequence, the only proper way to describe such a network is a multiplex graph with 281 nodes and two layers, one for the chemical synaptic links and a separate one for the gap junctions’ interactions. The most important consequence is that each neuron can play a very different role in the two layers, and a proper ranking should be then able to distinguish those cases in which a node of high centrality in a layer is just marginally central in the other.

These three examples, along with the many others that the reader will be presented with throughout the rest of this report, well explain why the last years of research in network science have been characterized by more and more attempts to generalize the traditional network theory by developing (and validating) a novel framework for the study of multilayer networks, i.e. graphs where constituents of a system are the nodes, and several different layers of connections have to be taken into account to accurately describe the network’s unit-unit interactions, and/or the overall system’s parallel functioning.

Multilayer networks explicitly incorporate multiple channels of connectivity and constitute the natural environment to describe systems interconnected through different categories of connections: each channel (relationship, activity, category) is represented by a layer and the same node or entity may have different kinds of interactions (different set of neighbors in each layer). For instance, in social networks, one can consider several types of different actors’ relationships: friendship, vicinity, kinship, membership of the same cultural society, partnership or coworker-ship, etc.

Such a change of paradigm, that was termed in disparate ways (multiplex networks, networks of networks, interdependent networks, hypergraphs, and many others), led already to a series of very relevant and unexpected results, and we firmly believe that: i) it actually constitutes the new frontier in many areas of science, and ii) it will rapidly expand and attract more and more attention in the years to come, stimulating a new movement of interdisciplinary research.

Therefore, in our intentions, the present report would like to constitute a survey and a summary of the current state of the art, together with a weighted and meditated outlook to the still open questions to be addressed in the future.

1.2 Outline of the report

Together with this introductory Preamble, the Report is organized along other 8 sections.

In the next section, we start by offering the overall mathematical definitions that will accompany the rest of our discussion. Section 2 contains several parts that are necessarily rather formal, in order to properly introduce the quantities (and their mathematical properties and representation) that characterize the structure of multilayer networks. The reader will find there the attempt of defining an overall mathematical framework encompassing the different situations and systems that will be later extensively treated. If more interested instead in the modeling or physical applications of multilayer networks, the reader is advised, however, to take Section 2 as a vocabulary that will help and guide him/her in the rest of the paper.

Section 3 summarizes the various (growing and not growing) models that have been introduced so far for generating artificial multilayer networks with specific structural features. In particular, we extensively review the available literature for the two classes of models considered so far: that of growing multiplex networks (in which the number of nodes grows in time and fundamental rules are imposed to govern the dynamics of the network structure), and that of multiplex network ensembles (which are ultimately ensembles of networks satisfying a certain set of structural constraints).

Section 4 discusses the concepts, ideas, and available results related to multilayer networks’ robustness and resilience, together with the process of percolation on multilayer networks, which indeed has attracted a huge attention in recent years. In particular, Section 4 will manifest the important differences, as far as these processes are concerned, between the traditional approach of single-layer networks, and the case where the structure of the network has a multilayer nature.

In Section 5, we summarize the state of current understanding of spreading processes taking place on top of a multilayer structure, and discuss explicitly linear diffusion, random walks, routing and congestion phenomena and spreading of information and disease. The section includes also a complete account on evolutionary games taking place on a multilayer network.

Section 6 is devoted to synchronization, and we there describe the cases of both alternating and coexisting layers. In the former, the different layers correspond to different connectivity configurations that alternate to define a time-dependent structure of coupling amongst a given set of dynamical units. In the latter, the different layers are simultaneously responsible for the coupling of the network’s units, with explicit additional layer-layer interactions taken into account.

Section 7 is a large review of applications, especially those that were studied in social sciences, technology, economy, climatology, ecology and biomedicine.

Finally, Section 8 presents our conclusive remarks and perspective ideas.

2 The structure of multilayer networks

Complexity science is the study of systems with many interdependent components, which, in turn, may interact through many different channels. Such systems – and the self-organization and emergent phenomena they manifest – lie at the heart of many challenges of global importance for the future of the Worldwide Knowledge Society. The development of this science is providing radical new ways of understanding many different mechanisms and processes from physical, social, engineering, information and biological sciences. Most complex systems include multiple subsystems and layers of connectivity, and they are often open, value-laden, directed, multilevel, multicomponent, reconfigurable systems of systems, and placed within unstable and changing environments. They evolve, adapt and transform through internal and external dynamic interactions affecting the subsystems and components at both local and global scale. They are the source of very difficult scientific challenges for observing, understanding, reconstructing and predicting their multiscale and multicomponent dynamics. The issues posed by the multiscale modeling of both natural and artificial complex systems call for a generalization of the “traditional” network theory, by developing a solid foundation and the consequent new associated tools to study multilayer and multicomponent systems in a comprehensive fashion. A lot of work has been done during the last years to understand the structure and dynamics of these kind of systems [20, 21, 22, 23, 24]. Related notions, such as networks of networks [25, 26], multidimensional networks [20], multilevel networks, multiplex networks, interacting networks, interdependent networks, and many others have been introduced, and even different mathematical approaches, based on tensor representation [21, 22] or otherwise [23, 24], have been proposed. It is the purpose of this section to survey and discuss a general framework for multilayer networks and review some attempts to extend the notions and models from single layer to multilayer networks. As we will see, this framework includes the great majority of the different approaches addressed so far in the literature.

2.1 Definitions and notations

2.1.1 The formal basic definitions

A multilayer network is a pair $ℳ=(𝒢,𝒞)$ where $𝒢=\{G_{\alpha };\alpha \in \{1,\mathrm{\cdots },M\}\}$ is a family of (directed or undirected, weighted or unweighted) graphs $G_{\alpha }=(X_{\alpha },E_{\alpha })$ (called layers of $ℳ$) and

$$𝒞=\{E_{\alpha \beta }\subseteq X_{\alpha }\times X_{\beta };\alpha ,\beta \in \{1,\mathrm{\cdots },M\},\alpha \ne \beta \}$$ (1)

is the set of interconnections between nodes of different layers $G_{\alpha }$ and $G_{\beta }$ with $\alpha \ne \beta$. The elements of $𝒞$ are called crossed layers, and the elements of each $E_{\alpha }$ are called intralayer connections of $ℳ$ in contrast with the elements of each $E_{\alpha \beta }$ ($\alpha \ne \beta$) that are called interlayer connections.

In the remainder, we will use Greek subscripts and superscripts to denote the layer index. The set of nodes of the layer $G_{\alpha }$ will be denoted by $X_{\alpha }=\{x_1^{\alpha },\mathrm{\cdots },x_{N_{\alpha }}^{\alpha }\}$ and the adjacency matrix of each layer $G_{\alpha }$ will be denoted by $A^{[\alpha ]}=(a_{ij}^{\alpha })\in {ℝ}^{N_{\alpha }\times N_{\alpha }}$, where

(2)

for $1\le i,j\le N_{\alpha }$ and $1\le \alpha \le M$. The interlayer adjacency matrix corresponding to $E_{\alpha \beta }$ is the matrix $A^{[\alpha ,\beta ]}=(a_{ij}^{\alpha \beta })\in {ℝ}^{N_{\alpha }\times N_{\beta }}$ given by:

(3)

The projection network of $ℳ$ is the graph $proj(ℳ)=(X_{ℳ},E_{ℳ})$ where

$$X_{ℳ}=\bigcup _{\alpha =1}^M{X}_{\alpha },E_{ℳ}=\left(\bigcup _{\alpha =1}^M{E}_{\alpha }\right)\bigcup \left(\bigcup _{\begin{array}{c}\alpha ,\beta =1\\ \alpha \ne \beta \end{array}}^M{E}_{\alpha \beta }\right).$$ (4)

We will denote the adjacency matrix of $proj(ℳ)=(X_{ℳ},E_{ℳ})$ by $\overline{A_{ℳ}}$.

This mathematical model is well suited to describe phenomena in social systems, as well as many other complex systems. An example is the dissemination of culture in social networks in the Axelrod Model [27], since each social group can be understood as a layer within a multilayer network. By using this representation we simultaneously take into account:

• the links inside the different groups,

• the nature of the links and the relationships between elements that (possibly) belong to different layers,

• the specific nodes belonging to each layer involved.

A multiplex network [28] is a special type of multilayer network in which $X_1=X_2=\mathrm{\cdots }=X_M=X$ and the only possible type of interlayer connections are those in which a given node is only connected to its counterpart nodes in the rest of layers, i.e., $E_{\alpha \beta }=\{(x,x);x\in X\}$ for every $\alpha ,\beta \in \{1,\mathrm{\cdots },M\},\alpha \ne \beta$. In other words, multiplex networks consist of a fixed set of nodes connected by different types of links. The paradigm of multiplex networks is social systems, since these systems can be seen as a superposition of a multitude of complex social networks, where nodes represent individuals and links capture a variety of different social relations.

A given multiplex network $ℳ$, can be associated to several (monolayer) networks providing valuable information about it. A specific example is the projection network $proj(ℳ)=(X_{ℳ},E_{ℳ})$. Its adjacency matrix $\overline{A_{ℳ}}$ has elements

(5)

A first approach to the concept of multiplex networks could suggest that these new objects are actually (monolayer) networks with some (modular) structure in the mesoscale. It is clear that if we take a multiplex $ℳ$, we can associate to it a (monolayer) network $\widetilde{ℳ}=(\tilde{X},\tilde{E})$, where $\tilde{X}$ is the disjoint union of all the nodes of $G_1,\mathrm{\cdots },G_M$, i.e.

$$\tilde{X}=\underset{1\le \alpha \le M}{⨆}{X}_{\alpha }=\left\{x^{\alpha };x\in X_{\alpha }\right\}$$ (6)

and $\tilde{E}$ is given by

$$\left(\bigcup _{\alpha =1}^M\left\{(x_i^{\alpha },x_j^{\alpha });(x_i^{\alpha },x_j^{\alpha })\in E_{\alpha }\right\}\right)\bigcup \left(\bigcup _{\begin{array}{c}\alpha ,\beta =1\\ \alpha \ne \beta \end{array}}^M\left\{(x_i^{\alpha },x_i^{\beta });x_i\in X\right\}\right).$$ (7)

Note that $\widetilde{ℳ}$ is a (monolayer) graph with $N\times M$ nodes whose adjacency matrix, called supra-adjacency matrix of $ℳ$, can be written as a block matrix

(8)

where $I_N$ is the $N$-dimensional identity matrix.

The procedure of assigning a matrix to a multilayer network is often called $flattening$, $unfolding$ or $matricization$. It is important to remark that the behaviors of $ℳ$ and $\widetilde{ℳ}$ are related but different, since a single node of $ℳ$ corresponds to different nodes in $\widetilde{ℳ}$. Therefore, the properties and behavior of a multiplex $ℳ$ can be understood as a type of non-linear quotient of the properties of the corresponding (monolayer) network $\widetilde{ℳ}$.

It is important to remark that the concept of multilayer network extends that of other mathematical objects, such as:

1. Multiplex networks. As we stated before, a multiplex network [28] $ℳ$, with $M$ layers is a set of layers $\{G_{\alpha };\alpha \in \{1,\mathrm{\cdots },M\}\}$, where each layer is a (directed or undirected, weighted or unweighted) graph $G_{\alpha }=(X_{\alpha },E_{\alpha })$, with $X_{\alpha }=\{x_1,\mathrm{\cdots },x_N\}$. As all layers have the same nodes, this can be thought of as a multilayer network by taking $X_1=\mathrm{\cdots }=X_M=X$ and $E_{\alpha \beta }=\{(x,x);x\in X\}$ for every $1\le \alpha \ne \beta \le M$.

2. Temporal networks [29]. A temporal network ${(G(t))}_{t=1}^T$ can be represented as a multilayer network with a set of layers $\{G_1,\mathrm{\cdots },G_T\}$ where $G_t=G(t)$, $E_{\alpha \beta }=\mathrm{\varnothing }$ if $\beta \ne \alpha +1$, while

   $$E_{\alpha ,\alpha +1}=\{(x,x);x\in X_{\alpha }\cap X_{\alpha +1}\}$$ (9)

   (see the schematic illustration of Fig. 1). Notice that here $t$ is an integer, and not a continuous parameter as it will be used later on in Sec. 6.1.1.

   

   Figure 1: (Color online). Schematic illustration of the mapping of a temporal network into a multilayer network. (Left side) At each time $t=1,2,3$, a different graph characterizes the structure of interactions between the system’s constituents. (Right side) The corresponding multilayer network representation where each time instant is mapped into a different layer.

3. Interacting or interconnected networks [24]. If we consider a family of networks $\{G_1,\mathrm{\cdots },G_L\}$ that interact, they can be modeled as a multilayer network of layers $\{G_1,\mathrm{\cdots },G_L\}$ and whose crossed layers $E_{\alpha \beta }$ correspond to the interactions between network $G_{\alpha }$ and $G_{\beta }$ (see Fig. 2).

4. Multidimensional networks [20, 30, 31, 32, 33]. Formally, an edge-labeled multigraph (multidimensional network) [30] is a triple $G=(V,E,D)$ where $V$ is a set of nodes, $D$ is a set of labels representing the dimensions, and $E$ is a set of labeled edges, i.e. it is a set of triples $E=\{(u,v,d);u,v\in V,d\in D\}$.

   It is assumed that given a pair of nodes $u,v\in V$ and a label $d\in D$, there may exist only one edge $(u,v,d)$. Moreover, if the model considered is a directed graph, the edges $(u,v,d)$ and $(v,u,d)$ are distinct. Thus, given $|D|=m$, each pair of nodes in $G$ can be connected by at most $m$ possible edges. When needed, it is possible to consider weights, so that the edges are no longer triplets, but quadruplets $(u,v,d,w)$, where $w$ is a real number representing the weight of the relation between nodes $u,v\in V$ and labeled with $d\in D$. A multidimensional network $G=(V,E,D)$ can be modeled as a multiplex network (and therefore, as a multilayer network) by mapping each label to a layer. Specifically, $G$ can be associated to a multilayer network of layers $\{G_1,\mathrm{\cdots },G_{|D|}\}$ where for every $\alpha \in D$, $G_{\alpha }=(X_{\alpha },E_{\alpha })$, $X_{\alpha }=V$,

   $$E_{\alpha }=\{(u,v)\in V\times V;(u,v,d)\in E\mathrm{and}d=\alpha \}$$ (10)

   and $E_{\alpha \beta }=\{(x,x);x\in V\}$ for every $1\le \alpha \ne \beta \le |D|$.

5. Interdependent (or layered) networks [34, 25, 35]. An interdependent (or layered) network is a collection of different networks, the layers, whose nodes are interdependent to each other. In practice, nodes from one layer of the network depend on control nodes in a different layer. In this kind of representation, the dependencies are additional edges connecting the different layers. This structure, in between the network layers, is often called mesostructure. A preliminary study about interdependent networks was presented in Ref. [34] (there called layered networks). Similarly to the previous case of multidimensional networks, we can consider an interdependent (or layered) network as a multilayer network by identifying each network with a layer.

   

   Figure 2: (Color online). Schematic illustration of the rather straightforward mapping of interacting networks into multilayer networks. Each different colored network on the left side corresponds to a different blue layer on the right side.

6. Multilevel networks [36]. The formal definition of a multilevel network is the following. Let $G=(X,E)$ be a network. A multilevel network is a triple $𝐌=(X,E,𝒮)$, where $𝒮=\{S_1,\mathrm{\dots },S_p\}$ is a family of subgraphs $S_j=(X_j,E_j),j=1,\mathrm{\dots },p$ of $G$ such that

   $$X=\bigcup _{j=1}^p{X}_j,E=\bigcup _{j=1}^p{E}_j.$$ (11)

   The network $G$ is the projection network of $𝐌$ and each subgraph $S_j\in 𝒮$ is called a slice of the multilevel network $𝐌$. Obviously, every multilevel network $𝐌=(X,E,𝒮)$ can be understood as a multilayer network with layers $\{S_1,\mathrm{\dots },S_p\}$ and crossed layers $E_{\alpha \beta }=\{(x,x);x\in X_{\alpha }\cap X_{\beta }\}$ for every $1\le \alpha \ne \beta \le p$. It is straightforward to check that every multiplex network is a multilevel network, and a multilevel network $𝐌=(X,E,𝒮)$ is a multiplex network if and only if $X_{\alpha }=X_{\beta }$ for all $1\le \alpha ,\beta \le p$.

7. Hypernetworks (or hypergraphs) [37, 38, 17, 39, 40, 41, 42, 43]. A hypergraph is a pair $\mathscr{H}=(X,H)$ where $X$ is a non-empty set of nodes and $H=\{H_1,\mathrm{\dots },H_p\}$ is a family of non-empty subsets of $X$, each of them called a hyperlink of $\mathscr{H}$. Now, if $G=(X,E)$ is a graph, a hyperstructure $S=(X,E,H)$ is a triple formed by the vertex set $X$, the edge set $E$, and the hyper-edge set $H$. If $\mathscr{H}=(X,H)$ is a hypernetwork (or hypergraph), then it can be modeled as a multilayer network, such that for every hyperlink $h=(x_1,\mathrm{\cdots },x_k)\in H$ we define a layer $G_h$ which is a complete graph of nodes $x_1,\mathrm{\cdots },x_k$, and the crossed layers are $E_{\alpha \beta }=\{(x,x);x\in X_{\alpha }\cap X_{\beta }\}$ (see Fig. 3).

Figure 3: (Color online). Schematic illustration of the transformation of a hypergraph into a multilayer network. The set of red nodes on the left side defines three hyperlinks ($H_1$, $H_2$, and $H_3$), each of which is mapped to a layer consisting of a complete graph of its nodes.

2.1.2 A small (and less formal) handbook

A large amount of studies has shown how representing the elements of a complex system and their interactions with nodes and links can help us to provide insights into the system’s structure, dynamics, and function. However, except for a number of complex systems, the simple abstraction of their organization into a single layer of nodes and links is not sufficient. As we have discussed in the previous section, several extensions of complex networks to multistructure or multirelational networks have been developed in recent years [20, 21, 22, 24, 28, 25, 35, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 16, 58, 59, 60]. In the following, we briefly describe the characteristics of the main ones.

Amongst the mathematical models that consider non-local structures are the hypergraphs (or hypernetworks) [37] and the hyperstructures [17]. However, these models are not able to combine the local scale with the global and the mesoscale structures of the system. For instance, if one wants to model how a rumor spreads within a social network, it is necessary to have in mind not only that different groups are linked through some of their members, but also that two people who know the same person do not necessarily know each other. In fact, these two people may very well belong to entirely different groups or levels. If one tries to model this situation with hypernetworks, then one only takes into account the social groups, and not the actual relationships between their members. In contrast, if one uses the hyperstructure model, then one cannot determine to which social group each contact between two nodes belongs. The key-point that makes hypernetworks and hyperstructures not the best mathematical model for systems with mesoscale structures is that they are both node-based models, while many real systems combine a node-based point of view with a link-based perspective.

Following on with the social network example, when one considers a relationship between two members of a social group, one has to take into account not only the social groups that hold the members, but also the social groups that hold the relationship itself. In other words, if there is a relationship between two people that share two distinct social groups, such as a work and a sporting environment, one has to specify if the relationship arises in the work place, or if it has a sport nature. A similar situation characterizes also public transport systems, where a link between two stations belonging to several transport lines can occur as a part of different lines.

Nevertheless, the use of hypergraph analysis is far from being inadequate. In Ref. [61], the Authors investigate the theory of random tripartite hypergraphs with given degree distributions, providing an extension of the configuration model for traditional complex networks, and a theoretical framework in which analytical properties of these random graphs are investigated. In particular, the conditions that allow the emergence of giant components in tripartite hypergraphs are analyzed, along with classical percolation events in these structures. Moreover, in Ref. [62] a collection of useful metrics on tripartite hypergraphs is provided, making this model very robust for basic analysis.

Another mathematical model capturing multiple different relations that act at the same time is that of multidimensional networks [20, 30, 31, 32, 33, 14, 63, 64, 65, 66, 67]. In a multidimensional network, a pair of entities may be linked by different kinds of links. For example, two people may be linked because they are acquaintances, friends, relatives or because they communicate to each other by phone, email, or other means. Each possible type of relation between two entities is considered as a particular dimension of the network. In the case of a multidimensional network model, a network is a labeled multigraph, that is, a graph where both nodes and edges are labeled and where there can exist two or more edges between two nodes. Obviously, it is possible to consider edge-only labeled multigraphs as particular models of multidimensional networks.

When edge-labeled multigraphs are used to model a multidimensional network, the set of nodes represents the set of entities or actors in the networks, the edges represent the interactions and relations between them, and the edge labels describe the nature of the relations, i.e. the dimensions of the network. Given the strong correlation between labels and dimensions, often the two terms are used interchangeably. In this model, a node $u$ belongs to (or appears in) a given dimension $d$ if $u$ has at least one edge labeled with $d$. So, given a node $u\in V$, $n_u$ is the number of dimensions in which $u$ appears, i.e.

$$n_u=\left|\{d\in D;\mathrm{there}\mathrm{is}v\in V\mathrm{s}.\mathrm{t}.(u,v,d)\in E\}\right|.$$ (12)

Similarly, given a pair of nodes $u,v\in V$, $n_{uv}$ is the number of dimensions which label the edges between $u$ and $v$, i.e. $n_{uv}=|\{d\in D;(u,v,d)\in E\}|$. A multidimensional network can be considered as a multilayer network by making every label equivalent to a layer.

Other alternative models focus on the study of networks with multiple kinds of interactions in the broadest as possible sense. For example, interdependent networks were used to study the interdependence of several real world infrastructure networks in Refs. [25] and [35], where the Authors also explore several properties of these structures such as cascading failures and percolation. Related to this concept, in Ref. [35] the Authors report the presence of a critical threshold in percolation processes, creating an analogy between interdependent networks and ideal gases. The main advantage of interdependent networks is their ability of mapping a node in one relation with many different nodes in another relation. Thus, the mesostructure can connect a single node in a network $N_1$ to several different nodes in a network $N_2$. This is not possible in other models where there is no explicitly defined mesostructure, and therefore a node is a single, not divisible entity.

Multilevel networks [36] lie in between the multidimensional and the interdependent networks, as they extend both the classic complex network model and the hypergraph model [37]. Multilevel networks are completely equivalent (isomorphic) to multidimensional networks by considering a dimension $d$ in conjunction with the equivalent slice $S_d$. The set $D$ corresponding to dimension $d$ is the collection of edges labeled with the label $d$, i.e. $D=\{(u,v,x);x=d\}$, while $S_d$ is the collection of nodes and edges of relation $d$, i.e. all the $u$ and $v$ that are present in at least one edge labeled with $d$. In order to perform more advanced studies such as the shortest path detection, in Ref. [36] Authors introduced also a mesostructure called auxiliary graph. Every vertex of the multilevel network $𝐌$ is represented by a vertex in the auxiliary graph and, if a vertex in $𝐌$ belongs to two or more slice graphs in $𝐌$, then it is duplicated as many times as the number of slice graphs it belongs to. Every edge of $E$ is an edge in the auxiliary graph and there is one more (weighted) edge for each vertex duplication between the duplicated vertex and the original one. This operation breaks the isomorphism with multidimensional networks and brings this representation very close to a layered network [30]. However, these two models are not completely equivalent, since in the multilevel network the one-to-one correspondence of nodes in different slices is strict, while this condition does not hold for layered networks. In Ref. [36], the Authors also define some extensions of classical network measures for multilevel networks, such as the slice clustering coefficient and the efficiency, as well as a collection of network random generators for multilevel structures.

In Ref. [68] the Authors introduce the concept of multiplex networks by extending the popular modularity function for community detection, and by adapting its implicit null model to fit a layered network. The main idea is to represent each layer with a slice. Each slice has an adjacency matrix describing connections between nodes belonging to the previously considered slice. This concept also includes a mesostructure, called interslice couplings which connects a node of a specific slice $S_{\alpha }$ to its copy in another slice $S_{\beta }$. The mathematical formulation of multiplex networks has been recently developed through many works [23, 28, 45, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 59, 60]. For instance, in Ref. [23] a comprehensive formalism to deal with multiplex systems is proposed, and a number of metrics to characterize multiplex systems with respect to node degree, edge overlap, node participation to different layers, clustering coefficient, reachability and eigenvector centrality is provided.

Other recent extensions include multivariate networks [69], multinetworks [70, 71], multislice networks [68, 72, 73, 74], multitype networks [75, 76, 77], multilayer networks [21, 22, 78, 79], interacting networks [24, 80, 81], and networks of networks [46], most of which can be considered particular cases of the definition of multilayer networks given in Sec. 2.1.1. Finally, it is important to remark that the terminology referring to networks with multiple different relations has not yet reached a consensus. In fact, different scientists from various fields still use similar terminologies to refer to different models, or distinct names for the same model. It is thus clear that the introduction of a sharp mathematical model that fits these new structures is crucial to properly analyze the dynamics that takes place in these complex systems which even nowadays are far from being completely understood.

The notation proposed in Sec. 2.1.1 is just one of the possible ways of dealing with multilayer networks, and indeed there have been other recent attempts to define alternative frameworks. In particular, the tensor formalism proposed in Refs. [21] and [22], which we will extensively review in Sec. 2.3, seems promising, since it allows the synthetic and compact expression of multiplex metrics. Nevertheless, we believe that the notation we propose here is somehow more immediate to understand and easier to use for the study of real-world systems.

In the following, we describe the extension to the context of multilayer networks of the parameters that are traditionally used to characterize the structural properties of a monolayer graph.

2.2 Characterizing the structure of multilayer networks

2.2.1 Centrality and ranking of nodes

The problem of identifying the nodes that play a central structural role is one of the main topics in the traditional analysis of complex networks. In monolayer networks, there are many well-known parameters that measure the structural relevance of each node, including the node degree, the closeness, the betweenness, eigenvector-like centralities and PageRank centrality. In the following, we discuss the extension of these measures to multilayer networks.

One of the main centrality measures is the degree of each node: the more links a node has, the more relevant it is. The degree of a node $i\in X$ of a multiplex network $ℳ=(𝒢,𝒞)$ is the vector [20, 23]

$${𝐤}_i=(k_i^{[1]},\mathrm{\cdots },k_i^{[M]}),$$ (13)

where $k_i^{[\alpha ]}$ is the degree of the node $i$ in the layer $\alpha$, i.e. $k_i^{[\alpha ]}={\sum }_j{a}_{ij}^{[\alpha ]}$. This vector-type node degree is the natural extension of the established definition of the node degree in a monolayer network.

One of the main goals of any centrality measure is ranking the nodes to produce an ordered list of the vertices according to their relevance in the structure. However, since the node degree in a multiplex network is a vector, there is not a clear ordering in ${ℝ}^M$ that could produce such a ranking. In fact, one can define many complete orders in ${ℝ}^M$, and therefore we should clarify which of these are relevant. Once one has computed the vector-type degree of the nodes, one can aggregate this information and define the overlapping degree [23] of the node $i\in X$, as

$$o_i=\sum _{\alpha =1}^M{k}_i^{[\alpha ]},$$ (14)

i.e. $o_i={\Vert {𝐤}_i\Vert }_1$. In fact, many other aggregation measures $f({𝐤}_i)$ could be alternatively used to compute the degree centrality, such as a convex combination of $k_i^{[1]},\mathrm{\cdots },k_i^{[M]}$, or any norm of ${𝐤}_i$.

Other centrality measures, such as closeness and betweenness centrality, are based on the metric structure of the network. These measures can be easily extended to multilayer networks, once the metric and geodesic structure are defined. In Sec. 2.2.3, the reader will find a complete discussion of the metric structures in multilayer networks, which allow straightforward extensions of this kind of centrality measures.

A different approach to measure centrality employs the spectral properties of the adjacency matrix. In particular, the eigenvector centrality considers not only the number of links of each node but also the quality of such connections [82]. There are several different ways to extend this idea to multilayer networks, as discussed in Ref. [28], or in Ref. [83] where eigenvector centrality is used to optimize the outcome of interacting competing networks. In the former reference, several definitions of eigenvector-like centrality measures for multiplex networks are presented, along with studies of their existence and uniqueness.

The simplest way to calculate eigenvector-like centralities in multiplex networks is to consider the eigenvector centrality ${𝐜}_{\alpha }=(c_1^{[\alpha ]},\mathrm{\cdots },c_N^{[\alpha ]})$ in each layer $1\le \alpha \le M$ separately. With this approach, for every node $i\in X$ the eigenvector centrality ${𝐜}_i$ is another vector

$${𝐜}_i=(c_i^{[1]},\mathrm{\cdots },c_i^{[M]})\in {ℝ}^M,$$ (15)

where each coordinate is the centrality in the corresponding layer. Once all the eigenvector centralities have been computed, the independent layer eigenvector-like centrality [28] of $ℳ$ is the matrix

(16)

Notice that $C$ is column stochastic, since all components of ${𝐜}_{\alpha }$ are semipositive definite and ${\Vert {𝐜}_{\alpha }\Vert }_1=1$ for every $1\le \alpha \le M$, and the centrality ${𝐜}_i$ of each node $i\in X$ is the $i^{th}$ row of $C$. As for the degree-type indicators, a numeric centrality measure of each node can be obtained by using an aggregation measure $f({𝐜}_i)$ such as the sum, the maximum, or the ${\mathrm{\ell }}_p$-norm. The main limitation of this parameter is that it does not fully consider the multilevel interactions between layers and its influence in the centrality of each node.

If one now bears in mind that the centrality of a node must be proportional to the centrality of its neighbors (that are distributed among all the layers), and if one considers that all the layers have the same importance, one has that

$$\forall x_i^{\alpha },x_j^{\alpha }\in X_{\alpha },c(x_i^{\alpha })\propto c(x_j^{\alpha })\text{if}(x_j^{\alpha }\to x_i^{\alpha })\in G_{\alpha },\alpha \in \{1,\mathrm{\dots },M\},$$ (17)

so the uniform eigenvector-like centrality is defined [28] as the positive and normalized eigenvector $\tilde{c}$ (if it exists) of the matrix $\tilde{A}$ given by

$$\tilde{A}=\sum _{\alpha =1}^M{(A^{[\alpha ]})}^{\mathrm{T}},$$ (18)

where ${(A^{[\alpha ]})}^{\mathrm{T}}$ is the transpose of the adjacency matrix of layer $\alpha$. This situation happens, for instance, in social networks, where different people may have different relationships with other people, while one is generically interested to measure the centrality of the network of acquaintances.

A more complex approach is to consider different degrees of importance (or influence) in different layers of the network, and to include this information in the definition of a matrix that defines the mutual influence between the layers. Thus, to calculate the importance of a node within a specific layer, one must take into account also all the other layers, as some of them may be highly relevant for the calculation. Consider, for instance, the case of a boss living in the same block of flats as one of his employees: the relationship between the two fellows within the condominium layer formed by all the neighbors has a totally different nature from that occurring inside the office layer, but the role of the boss (i.e. his centrality) in this case can be even bigger than if he was the only person from the office living in that block of flats. In other words, one needs to consider the situation where the influence amongst layers is heterogeneous.

To this purpose, one can introduce an influence matrix $W=(w_{\alpha \beta })\in {ℝ}^{M\times M}$, defined as a non-negative matrix $W\ge 0$ such that $w_{\alpha \beta }$ measures the influence on the layer $G_{\alpha }$ given by the layer $G_{\beta }$. Once $𝒢$ and $W=(w_{\alpha \beta })$ have been fixed, the local heterogeneous eigenvector-like centrality of $𝒢$ on each layer $G_{\alpha }$ is defined [28] as a positive and normalized eigenvector $c_{\alpha }^{\star }\in {ℝ}^N$ (if it exists) of the matrix

$$A_{\alpha }^{\star }=\sum _{\beta =1}^M{w}_{\alpha \beta }{(A^{[\beta ]})}^{\mathrm{T}}.$$ (19)

So, the local heterogeneous eigenvector-like centrality matrix can be defined as

(20)

A similar approach was introduced in Ref. [23], but using a matrix

$$A_{\alpha }^{\star }=\sum _{\beta =1}^M{b}_{\beta }{(A^{[\beta ]})}^{\mathrm{T}},$$ (21)

where $b_{\beta }\ge 0$ and ${\sum }_{\beta }{b}_{\beta }=1$.

Another important issue is that, in general, the centrality of a node $x_i^{\alpha }$ within a specific layer $\alpha$ may depend not only on the neighbors that are linked to $x_i^{\alpha }$ within that layer, but also on all other neighbors of $x_i^{\alpha }$ that belong to the other layers. Consider the case of scientific citations in different areas of knowledge. For example, there could be two scientists working in different subject areas (a chemist and a physicist) with one of them awarded the Nobel Prize: the importance of the other scientist will increase even though the Nobel prize laureate had few citations within the area of the other researcher. This argument leads to the introduction of another concept of centrality [28]. Given a multiplex network $ℳ$ and an influence matrix $W=(w_{\alpha \beta })$, the global heterogeneous eigenvector-like centrality of $ℳ$ is defined as a positive and normalized eigenvector $c^{\otimes }\in {ℝ}^{NM}$ (if it exists) of the matrix

(22)

Note that $A^{\otimes }$ is the Khatri-Rao product of the matrices

(23)

In analogy with what done before, one can introduce the notation

$$c^{\otimes }=\left(\begin{array}{c}{𝐜}_1^{\otimes }\\ \\ {𝐜}_2^{\otimes }\\ \\ \mathrm{⋮}\\ \\ {𝐜}_M^{\otimes }\end{array}\right),$$ (24)

where ${𝐜}_1^{\otimes },\mathrm{\cdots },{𝐜}_M^{\otimes }\in {ℝ}^N$. Then, the global heterogeneous eigenvector-like centrality matrix of $ℳ$ is defined as the matrix given by

(25)

Note that, in general $C^{\otimes }$ is neither column stochastic nor row stochastic, but the sum of all the entries of $C^{\otimes }$ is 1.

Other spectral centrality measures include parameters based on the stationary distribution of random walkers with additional random jumps, such as the PageRank centrality [84]. The extension of these measures and the analysis of random walkers in multiplex networks will be discussed in Sec. 5.

2.2.2 Clustering

The graph clustering coefficient introduced by Watts and Strogatz in Ref. [85] can be extended to multilayer networks in many ways. This coefficient quantifies the tendency of nodes to form triangles, following the popular saying “the friend of your friend is my friend”.

Recall that given a network $𝒢=(X,E)$ the clustering coefficient of a given node $i$ is defined as

$$c_{𝒢}(i)=\frac{\text{\# of links between the neighbors of}i}{\text{largest possible \# of links between the neighbors of}i}.$$ (26)

If we think of three people $i$, $j$ and $k$ with mutual relations between $i$ and $j$ as well as between $i$ and $k$, the clustering coefficient of $i$ represents the likelihood that $j$ and $k$ are also related to each other. The global clustering coefficient of $𝒢$ is further defined as the average of the clustering coefficients of all nodes. Obviously, the local clustering coefficient is a measure of transitivity [86], and it can be interpreted as the density of the local node’s neighborhood.

Notice that the global clustering coefficient is sometimes defined differently, with an expression that relates it directly to the global features of a network. This alternative definition is not equivalent to the previous one, and it is commonly used in the social sciences [87]. Its expression, sometimes called network transitivity [14], is

$$T=\frac{\text{\# of triangles in the network}}{\text{\# of triads in the network}}.$$ (27)

In order to extend the concept of clustering to the context of multilayer networks, it is necessary to consider not only the intralayer links, but also the interlayer links. In Ref. [36], the Authors establish some relations between the clustering coefficient of a multilevel network, the clustering coefficient of its layers and the clustering coefficient of its projection network. This generalization is obtained straightforwardly by identifying each slice $S_q$ of a multilevel network $ℳ$ with a layer $G_{\alpha }$ of the corresponding multiplex network $ℳ=(𝒢,𝒞)$. Before giving a definition of the clustering coefficient of a node $i\in X$ within a multilevel network $ℳ$, we need to introduce some notation.

For every node $i\in X$ let $𝒩(i)$ be the set of all neighbors of $i$ in the projection network $proj(ℳ)$. For every $\alpha \in \{1,\mathrm{\cdots },M\}$ let ${𝒩}_{\alpha }(i)=𝒩(i)\cap X_{\alpha }$ and $\overline{S_{\alpha }}(i)$ be the subgraph of the layer $G_{\alpha }$ induced by ${𝒩}_{\alpha }(i)$, i.e. $\overline{S_{\alpha }}(i)=({𝒩}_{\alpha }(i),\overline{E_{\alpha }}(i))$, where

$$\overline{E_{\alpha }}(i)=\left\{(k,j)\in E_{\alpha };k,j\in {𝒩}_{\alpha }(i)\right\}.$$ (28)

Similarly, we will define $\overline{S}(i)$ as the subgraph of the projection network $proj(ℳ)$ induced by $𝒩(i)$. In addition, the complete graph generated by ${𝒩}_{\alpha }(i)$ will be denoted by $K_{{𝒩}_{\alpha }(i)}$, and the number of links in $K_{{𝒩}_{\alpha }(i)}$ by $|\overline{E_{\alpha }}(i)|$. With this notation we can define the clustering coefficient of a given node $i$ in $ℳ$ as

$${\text{C}}_{ℳ}(i)=\frac{2{\displaystyle \sum _{\alpha =1}^M}|\overline{E_{\alpha }}(i)|}{{\displaystyle \sum _{\alpha =1}^M}|{𝒩}_{\alpha }(i)|(|{𝒩}_{\alpha }(i)|-1)}.$$ (29)

Then, the clustering coefficient of $ℳ$ can be defined as the average of all ${\text{C}}_{ℳ}(i)$.

Once again, the clustering coefficient may be defined in several different ways. For instance, we may consider the average of the clustering coefficients of each layer $G_{\alpha }$. However, it is natural to opt for a definition that considers the possibility that a given node $i$ has two neighbors $k$ and $j$ with $(i,k)\in E_{\alpha }$, $(i,j)\in E_{\beta }$ with $\alpha \ne \beta$, and $(j,k)\in E_{\gamma }$ with $\gamma \ne \alpha ,\beta$. This is a situation occurring in social networks: one person $i$ may know $j$ from the aerobic class and $k$ from a reading club, while $j$ and $k$ know each other from the supermarket. Averaging the clustering coefficients of the layers does not help in describing such situations, and an approach based on the projection network seems more relevant, as evidenced by the following example: consider the multiplex network $ℳ$ with layers $\{G_1,G_2,G_3\}$ and $X=\{x_1,x_2,x_3,x_4\}$ (Fig. 4); it is easy to check that $c_{proj(ℳ)}(x_i)=1$ for all $x_i\in X$ but $c_{G_{\alpha }}(x_i)=0$ for all $x_i$ and $\alpha$.

Figure 4: (Color online). An example of the difference between clustering coefficients. The local clustering coefficient of all nodes is 0 in each single layer, but 1 in the projection network.

In order to establish a relation between the clustering coefficients of the nodes in the multiplex network, ${\text{C}}_{ℳ}(i)$, and the clustering coefficients of the nodes in the projected network, $c_{proj(ℳ)}(i)$, we can use the same arguments employed in Ref. [36] for multilevel networks. Define $\theta (i)$ as the number of layers in which $i$ has less than two neighbors. Then,

$$\frac{1}{M-\theta (i)}{c}_{proj(ℳ)}(i)\le {\text{C}}_{ℳ}(i)\le c_{proj(ℳ)}(i).$$ (30)

Note that Eq. (30) shows that the range of ${\text{C}}_{ℳ}(i)$ increases with $\theta (i)$.

While the previous example (Fig. 4) shows the implicit limitations in defining the clustering coefficient of nodes in a multiplex from that of individual layers, still it makes sense to provide an alternative “layers” definition. Similarly to the previous case, let ${𝒩}_{\alpha }^{\ast }(i)=\{j\in X;j\text{is a neighbor of}i\text{in}{G}_{\alpha }\}$ and $S_{\alpha }(i)=({𝒩}_{\alpha }^{\ast }(i),E_{\alpha }(i))$, where $E_{\alpha }(i)=\left\{(k,j)\in E_{\alpha };k,j\in {𝒩}_{\alpha }^{\ast }(i)\right\}$. Note that $S_{\alpha }(i)$ is the subgraph of the layer $G_{\alpha }$ induced by ${𝒩}_{\alpha }^{\ast }(i)$. Then, the layer clustering coefficient of node $i$ is defined as

$${\text{C}}_{ℳ}^{ly}(i)=\frac{2{\displaystyle \sum _{\alpha =1}^M}|E_{\alpha }(i)|}{{\displaystyle \sum _{\alpha =1}^M}|{𝒩}_{\alpha }^{\ast }(i)|(|{𝒩}_{\alpha }^{\ast }(i)|-1)}.$$ (31)

Notice that $S_{\alpha }(i)$ is a subgraph of $\overline{S_{\alpha }}(i)$. Accordingly, ${𝒩}_{\alpha }^{\ast }(i)\subseteq {𝒩}_{\alpha }(i)$ and so the largest possible number of links between neighbors of $i$ in layer $\alpha$ cannot exceed the corresponding largest possible number of links between neighbors of $i$ in ${𝒩}_{\alpha }(i)$. Also, we have the relation

(32)

where the last sum has $\left(\genfrac{}{}{0pt}{}{M}{2}\right)$ terms. We can further assume that the nodes can be rearranged so that $|{𝒩}_{\alpha }^{\ast }(i)|\le |{𝒩}_{\alpha +1}^{\ast }(i)|$ for all $1\le \alpha \le M$. Thus, using the method described in Ref. [36], we can obtain a relation between the clustering coefficient in the projected network $c_{proj(ℳ)}(i)$ and the layer clustering coefficient ${\text{C}}_{ℳ}^{ly}(i)$:

$${\text{C}}_{ℳ}^{ly}(i)\le M\cdot c_{proj(𝒢)}(i)\left[1+(M-1)\left(4+\frac{\theta (i)}{M-\theta (i)}\right)\right].$$ (33)

Another possible definition of the layer clustering coefficient of a node $i$ is the average over the clustering coefficients $c_{G_{\alpha }}(i)$ of the slices

$${\text{C}}_{proj(ℳ)}^{\overline{ly}}(i)=\frac{1}{M}\sum _{\alpha =1}^M{c}_{G_{\alpha }}.$$ (34)

The following relationship between both clustering coefficients holds [36]:

$$M\cdot \underset{1\le \alpha \le M}{\min }\frac{|{𝒩}_{\alpha }^{\ast }(i)|(|{𝒩}_{\alpha }^{\ast }(i)|-1)}{2}{\text{C}}_{proj(ℳ)}^{\overline{ly}}(i)\le {\text{C}}_{proj(ℳ)}^{ly}(i)\le M\cdot \underset{1\le \alpha \le M}{\max }\frac{|{𝒩}_{\alpha }^{\ast }(i)|(|{𝒩}_{\alpha }^{\ast }(i)|-1)}{2}{\text{C}}_{proj(ℳ)}^{\overline{ly}}(i).$$ (35)

Further generalizations of the notion of clustering coefficient to multilayer networks have been proposed in Refs. [23] and [47]. In Ref. [23], the Authors point out the necessity of extending the notion of triangle to take into account the richness added by the presence of more than one layer. They define a 2-triangle as a triangle formed by an edge belonging to one layer and two edges belonging to a second layer. Similarly, a 3-triangle is a triangle which is composed by three edges all lying in different layers. In order to quantify the added value provided by the multiplex structure in terms of clustering, they consider two parameters of clustering interdependence, $I_1$ and $I_2$. $I_1$ ($I_2$) is the ratio between the number of triangles in the multiplex which can be obtained only as 2-triangles (3-triangles), and the number of triangles in the aggregated system. Then, $I=I_1+I_2$ is the total fraction of triangles of the aggregated network which cannot be found entirely in one of the layers. They also define a $1$-triad centered at node $i$, for instance $j-i-k$, as a triad in which both edge $(j-i)$ and edge $(i-k)$ are on the same layer. Similarly, a $2$-triad is a triad whose two links belong to two different layers of the systems. This way, they establish two further definitions of clustering coefficient for multiplex networks. For each node $i$ the clustering coefficient $C_{i1}$ is the ratio between the number of $2$-triangles with a vertex in $i$ and the number of $1$-triads centered in $i$. A second clustering coefficient $C_{i2}$ is defined as the ratio between the number of $3$-triangles with node $i$ as a vertex, and the number of $2$-triads centered in $i$. As the Authors point out, while $C_{i1}$ is a suitable definition for multiplexes with $M\ge 2$, $C_{i2}$ can only be defined for systems composed of at least three layers, and both coefficients are poorly correlated, so it is necessary to use both clustering coefficients in order to properly quantify the abundance of triangles in multilayer networks. Averaging over all the nodes of the system, they obtain the network clustering coefficients $C_1$ and $C_2$.

In Ref. [23] the Authors also generalize the definition of transitivity. They propose two measures of transitivity: $T_1$ as the ratio between the number of $2$-triangles and the number of $1$-triads, and $T_2$ as the ratio between the number of $3$-triangles and the number of $2$-triads. As it is stressed by the Authors, clustering interdependencies $I_1$ and $I_2$, average multiplex clustering coefficients $C_1$ and $C_2$, and multiplex transitivities $T_1$ and $T_2$ are all global network variables which give a different perspective on the multilayer patterns of clustering and triadic closure with respect to the clustering coefficient and the transitivity computed for each layer of the network.

In Ref. [47], the Authors derive measurements of transitivity for multiplex networks by developing several multiplex generalizations of the clustering coefficient, and provide a comparison between some different formulations of multiplex clustering coefficients. For instance, Authors point out that the balance between intralayer versus interlayer clustering is different in social versus transportation networks, reflecting the fact that transitivity emerges from different mechanisms in these cases. Such differences are rooted in the new degrees of freedom that arise from interlayer connections, and are invisible to calculations of clustering coefficients on single-layer networks obtained via aggregation. Generalizing clustering coefficients for multiplex networks thus makes it possible to explore such phenomena and to gain deeper insights into different types of transitivity in networks. Further multiplex clustering coefficients are defined in Refs. [64, 88, 89].

2.2.3 Metric structures: Shortest paths and distances

The metric structure of a complex network is related to the topological distance between nodes, written in terms of walks and paths in the graph. So, in order to extend the classical metric concepts to the context of multilayer networks, it is necessary to establish first the notions of path, walk and length. In order to introduce all these concepts, we will follow a similar scheme to that used in Ref. [90]. Given a multilayer network $ℳ=(𝒢,𝒞)$, we consider the set

$$E(ℳ)=\{E_1,\mathrm{\cdots },E_M\}\bigcup 𝒞.$$ (36)

A walk (of length $q-1$) in $ℳ$ is a non-empty alternating sequence

$$\{x_1^{{\alpha }_1},{\mathrm{\ell }}_1,x_2^{{\alpha }_2},{\mathrm{\ell }}_2,\mathrm{\cdots },{\mathrm{\ell }}_{q-1},x_q^{{\alpha }_q}\},$$ (37)

of nodes and edges with ${\alpha }_1,{\alpha }_2,\mathrm{\cdots },{\alpha }_q\in \{1,\mathrm{\cdots },M\}$, such that for all there exists an $ℰ\in E(ℳ)$ with

$${\mathrm{\ell }}_r=(x_r^{{\alpha }_r},x_{r+1}^{{\alpha }_{r+1}})\in ℰ.$$ (38)

If the edges ${\mathrm{\ell }}_1,{\mathrm{\ell }}_2,{\mathrm{\ell }}_{q-1}$ are weighted, the length of the walk can be defined as the sum of the inverse of the corresponding weights. If $x_1^{{\alpha }_1}=x_q^{{\alpha }_q}$, the walk is said to be closed.

A path $\omega =\{x_1^{{\alpha }_1},x_2^{{\alpha }_2},\mathrm{\cdots },x_q^{{\alpha }_q}\},$ between two nodes $x_1^{{\alpha }_1}$ and $x_q^{{\alpha }_q}$ in $ℳ$ is a walk through the nodes of $ℳ$ in which each node is visited only once. A cycle is a closed path starting and ending at the same node. If it is possible to find a path between any pair of its nodes, a multilayer network $ℳ$ is referred to as connected; otherwise it is called disconnected. However, different types of reachability may be considered [20, 23] depending, for example, on whether we are considering only the edges included in some layers.

The length of a path is the number of edges of that path. Of course, in a multilayer network there are at least two types of edges, namely intralayer and interlayer edges. Thus, this definition changes depending on whether we consider interlayer and intralayer edges to be equivalent. Other metric definitions may be easily generalized from monolayer to multilayer networks. So, a geodesic between two nodes $u$ and $v$ in $ℳ$ is one of the shortest path that connects $u$ and $v$. The distance $d_{uv}$ between $u$ and $v$ is the length of any geodesic between $u$ and $v$. The maximum distance $D(ℳ)$ between any two vertices in $ℳ$ is called the diameter of $ℳ$. By $n_{uv}$ we will denote the number of different geodesics that join $u$ and $v$. If $x$ is a node and $\mathrm{\ell }$ is a link, then $n_{uv}(x)$ and $n_{uv}(\mathrm{\ell })$ will denote the number of geodesics that join the nodes $u$ and $v$ passing through $x$ and $\mathrm{\ell }$ respectively.

A multilayer network $𝒩=({𝒢}^{\prime },{𝒞}^{\prime })$ is a subnetwork of $ℳ=(𝒢,𝒞)$ if for every $\gamma ,\delta$ with $\gamma \ne \delta$, there exist $\alpha ,\beta$ with $\alpha \ne \beta$ such that $X_{\gamma }^{\prime }\subseteq X_{\alpha }$, $E_{\gamma }^{\prime }\subseteq E_{\alpha }$ and $E_{\gamma \delta }^{\prime }\subseteq E_{\alpha \beta }$. A connected component of $ℳ$ is a maximal connected subnetwork of $ℳ$. Two paths connecting the same pair of vertices in a multilayer network are said to be vertex-independent if they share no vertices other than the starting and ending ones. A $k$-component is a maximal subset of the vertices such that every vertex in the subset is connected to every other by $k$ independent paths. For the special cases $k=2$, $k=3$, the $k$-components are called bi-components and three-components of the multilayer network. For any given network, the $k$-components are nested: every three-component is a subset of a bi-component, and so forth.

The characteristic path length is defined as

$$L(ℳ)=\frac{1}{N(N-1)}\sum _{\begin{array}{c}u,v\in X_{ℳ}\\ u\ne v\end{array}}{d}_{uv},$$ (39)

where $|X_{ℳ}|=N$, and is also a way of measuring the performance of a graph.

The concept of efficiency, introduced by Latora and Marchiori in Ref. [91] may also be extended to multilayer networks in a similar way to the one used in Ref. [36]. With the same notation, the efficiency of a multilayer network $ℳ$ is defined as

$$E(ℳ)=\frac{1}{N(N-1)}\sum _{\begin{array}{c}u,v\in X_{ℳ}\\ u\ne v\end{array}}\frac{1}{d_{uv}}.$$ (40)

It is quite natural to try to establish comparisons between the efficiency $E(ℳ)$ of a multilayer network $ℳ$, the efficiency $E(proj(ℳ))$ of its projection and the efficiencies of the different layers $E(G_{\alpha })$. In Ref. [36] there are some analytical results that establish some relationships between these parameters.

If we consider interlayer and intralayer edges not to be equivalent, we can give alternative definitions of the metric quantities. Let $ℳ=(𝒢,𝒞)$ be a multilayer network, and

$$\omega =\{x_1^{{\alpha }_1},{\mathrm{\ell }}_1,x_2^{{\alpha }_2},{\mathrm{\ell }}_2,\mathrm{\cdots },{\mathrm{\ell }}_q,x_{q+1}^{{\alpha }_{q+1}}\},$$ (41)

be a path in $ℳ$. The length of $\omega$ can be defined as the non-negative value

$$\mathrm{\ell }(\omega )=q+\beta \sum _{j=2}^q\mathrm{\Delta }(j),$$ (42)

where

(43)

and $\beta$ is an arbitrarily chosen non-negative parameter.

In this case, the distance in $ℳ$ between two nodes $i$ and $j$ is the minimal length among all possible paths in from $i$ to $j$.

Notice that for $\beta =0$, the previous definition reduces to the natural metric in the projection network $proj(ℳ)$, while positive values of $\beta$ correspond to metrics that take into account also the interplay between the different layers.

One can generalize the definition of path length even further by replacing the jumping weight $\beta$ with an $M\times M$ non-negative matrix $\mathrm{\Theta }=(\beta (G_{\lambda },G_{\mu }))$, to account for different distances between layers. Thus, the length of a path $\omega$ becomes

$$\tilde{\mathrm{\ell }}(\omega )=q+\sum _{j=2}^q\tilde{\mathrm{\Delta }}(j),$$ (44)

where

(45)

The jumping weights can be further extended to include a dependence not only on the two layers involved in the layer jump, but also on the node from which the jump starts.

For a multiplex network, it is also important to quantify the participation of single nodes to the structure of each layer in terms of node reachability [23]. Reachability is an important feature in networked systems. In single-layer networks it depends on the existence and length of shortest paths connecting pairs of nodes. In multilevel systems, shortest paths may significantly differ between different layers, as well as between each layer and the aggregated topological networks. To address this, the so-called node interdependence was introduced in Refs. [57] and [92]. The interdependence ${\lambda }_i$ of a node $i$ is defined as:

$${\lambda }_i=\sum _{j\ne i}\frac{{\psi }_{ij}}{{\sigma }_{ij}},$$ (46)

where ${\sigma }_{ij}$ is the total number of shortest paths between node $i$ and node $j$ on the multiplex network, and ${\psi }_{ij}$ is the number of shortest paths between node $i$ and node $j$ which make use of links in two or more layers. Therefore, the node interdependence is equal to $1$ when all shortest paths make use of edges laying on at least two layers, and equal to $0$ when all shortest paths use only one layer of the system. Averaging ${\lambda }_i$ over all nodes, we obtain the network interdependence.

The interdependence is a genuine multiplex measure that provides information in terms of reachability. It is slightly anti-correlated to measures of degree such as the overlapping degree. In fact, a node with high overlapping degree has a higher number of links that can be the first step in a path toward other nodes; as such, it is likely to have a low ${\lambda }_i$. Conversely, a node with low overlapping degree is likely to have a high value of ${\lambda }_i$, since its shortest paths are constrained to a smaller set of edges and layers as first step. This measure is validated in Ref. [23] on the data set of Indonesian terrorists, where information among 78 individuals are recorded with respect to mutual trust, common operations, exchanged communications and business relationships.

2.2.4 Matrices and spectral properties

It is well known that the spectral properties of the adjacency and Laplacian matrices of a network provide insights into its structure and dynamics [93, 94, 9]. A similar situation is possible for multilayer networks, if proper matrix representations are introduced.

Given a multilayer network $ℳ$, several adjacency matrices can give information about its structure: amongst others, the most used are the adjacency matrix $A^{[\alpha ]}$ of each layer $G_{\alpha }$, the adjacency matrix $\overline{A_{ℳ}}$ of the projection network $proj(ℳ)$ and the supra-adjacency matrix $A_{ℳ}$. The spectrum of the supra-adjacency matrix is directly related to several dynamical processes that take place on a multilayer network. Using some results from interlacing of eigenvalues of quotients of matrices [93, 94, 95], in Ref. [79] it was proven that if ${\lambda }_1\le \mathrm{\cdots }\le {\lambda }_N$ is the spectrum of the supra-adjacency matrix $A_{ℳ}$ of an undirected multilayer network and ${\mu }_1\le \mathrm{\cdots }\le {\mu }_{n_{\alpha }}$ is the spectrum of the adjacency matrix $A^{[\alpha ]}$ of layer $G_{\alpha }$, then for every $1\le k\le n_{\alpha }$

$${\lambda }_k\le {\mu }_k\le {\lambda }_{k+N-n_{\alpha }}.$$ (47)

A similar situation occurs for the Laplacian matrix of a multiplex network. The Laplacian matrix ${ℒ}_{ℳ}=ℒ$ (also called supra-Laplacian matrix) of a multiplex $ℳ$ is defined as the $MN\times MN$ matrix of the form:

(48)

In the equation above, I is the $N\times N$ identity matrix and ${𝐋}^{\alpha }$ is the usual $N\times N$ Laplacian matrix of the network layer $\alpha$ whose elements are $L_{ij}^{\alpha }=s_i^{\alpha }{\delta }_{ij}-w_{ij}^{\alpha }$ where $s_i^{\alpha }$ is the strength of node $i$ in layer $\alpha$, $s_i^{\alpha }={\sum }_j{w}_{ij}^{\alpha }$. We will see in Sec. 5 that the diffusion dynamics on a multiplex network is strongly related to the spectral properties of $ℒ$. In Ref. [79], the Authors prove that if ${\lambda }_1\le \mathrm{\cdots }\le {\lambda }_N$ is the spectrum of the Laplacian matrix $ℒ$ of an undirected multilayer network and ${\mu }_1\le \mathrm{\cdots }\le {\mu }_{n_{\alpha }}$ is the spectrum of the Laplacian matrix ${𝐋}^{\alpha }$ of layer $G_{\alpha }$, then for every $1\le k\le n_{\alpha }$

$${\mu }_k\le {\lambda }_{k+N-n_{\alpha }}.$$ (49)

Similar results can be found using perturbative analysis [59, 96].

In addition to the spectra of the adjacency and Laplacian matrices, other types of spectral properties have been studied for multiplex network, such as the irreducibility [97]. Several problems in network theory involve the analysis not only of the eigenvalues, but also of the eigenvectors of a matrix [9]. This analysis typically includes the study of the existence and uniqueness of a positive and normalized eigenvector (Perron vector), whose existence is guaranteed if the corresponding matrix is irreducible (by using the classic Perron-Frobenius theorem). As for the spectral properties, it is possible to relate the irreducibility of such a matrix with the irreducibility in each layer and on the projection network. In Refs. [28, 97] it was shown that if $w_{ij}>0$ and the adjacency matrix $\overline{A_{ℳ}}$ of the projection network $proj(ℳ)$ is irreducible, then the matrix $A^{\otimes }$ defining the global heterogeneous eigenvector-like centrality is irreducible. A similar situation occurs when we consider random walkers in multiplex networks [98]. In this case, the uniqueness of a stationary state of the Markov process is guaranteed by the irreducibility of a matrix of the form

(50)

where $P_{\alpha \beta }=W_{\alpha \beta }\odot A^{[\beta ]}+v_{\alpha \beta }𝐈$, $W_{\alpha \beta }\in {ℝ}^{N\times N}$, $v_{\alpha \beta }\in {ℝ}^N$, and $W_{\alpha \beta }\odot A^{[\beta ]}$ is the Hadamard product of matrices $W_{\alpha \beta }$ and $A^{[\beta ]}$ (see Ref. [97]). It can be proven that, under some hypotheses, if the adjacency matrix $\overline{A_{ℳ}}$ of the projection network $proj(ℳ)$ is irreducible, then $𝔹$ is irreducible and hence the random walkers proposed in Ref. [98] have a unique stationary state.

2.2.5 Mesoscales: Motifs and modular structures

An essential method of network analysis is the detection of mesoscopic structures known as communities (or cohesive groups). These communities are disjoint groups (sets) of nodes which are more densely connected to each other than they are to the rest of the network [12, 99, 100]. Modularity is a scalar that can be calculated for any partition of a network into disjoint sets of nodes. Effectively, modularity is a quality function that counts intracommunity edges compared to what one would expect at random. Thus, one tries to determine a partition that maximizes modularity to identify communities within a network.

In Ref. [21], there is a definition of modularity for multilayer networks in which the Authors introduce a tensor that encodes the random connections defining the null model. Ref. [68] provides a framework for the study of community structure in a very general setting, covering networks that evolve over time, have multiple types of links (multiplexity), and have multiple scales. The Authors generalize the determination of community structure via quality functions to multislice networks that are defined by coupling multiple adjacency matrices.

As described above, communities are mesoscale structures mainly defined at a global level. One may ask whether more local mesoscales, i.e. those defined slightly above the single node level, can also be extended to multilayer networks. Without doubts, the most important of them are motifs, i.e. small sub-graphs recurring within a network with a frequency higher than expected in random graphs [101]. Their importance resides in the fact that they can be understood as basic building blocks, each associated with specific functions within the global system [102].

Little attention so far has been devoted to understanding the meaning of motifs in multilayer networks. An important exception is presented in Ref. [63] in the framework of the analysis of the Pardus social network, an on-line community that comprises $300.000$ players interacting in a virtual universe. When links are grouped in two layers, corresponding to positively and negatively connoted interactions, some resulting structures, which can be seen as multilayered motifs, appear with a frequency much higher (e.g. triplets of users sharing positive relations) or lower (e.g. two enemy users that both have a positive relation with a third) than expected in random networks.

Figure 5: Schematic illustration of the monoplex network discussed in Sec. 2.3 and whose adjacency matrix is given in Table 1.

2.3 Matrices and tensor representation: Spectral properties

There have been some attempts in the literature for modeling multilayer networks properly by using the concept of tensors [21, 22, 47]. Before describing these results, we recall some basic tensor analysis concepts.

There are two main ways to think about tensors:

• tensors as multilinear maps;

• tensors as elements of a tensor product of two or more vector spaces.

The former is more applied. The latter is more abstract but more powerful. The tensor product of two real vector spaces $𝒱$ and $ℒ$, denoted by $𝒱\otimes ℒ$, consists of finite linear combinations of $v\otimes w$, where $v\in 𝒱$ and $w\in ℒ$.

The dual vector space of a real vector space $𝒱$ is the vector space of linear functions $f:𝒱⟶ℝ$, indicated by ${𝒱}^{\ast }$. Denoting by $Hom({𝒱}^{\ast },ℒ)$ the set of linear functions from ${𝒱}^{\ast }$ to $ℒ$, there is a natural isomorphism between the linear spaces $𝒱\otimes ℒ$ and $Hom({𝒱}^{\ast },ℒ)$. Moreover, if $𝒱$ is a finite dimensional vector space, then there exists a natural isomorphism (depending on the bases considered) between the linear spaces $𝒱$ and ${𝒱}^{\ast }$. In fact, if $𝒱$ is finite-dimensional, the relationship between $𝒱$ and ${𝒱}^{\ast }$ reflects in an abstract way the relation between the $(1\times N)$ row-vectors and the $(N\times 1)$ column-vectors of a $(N\times N)$ matrix. However, if $𝒱$ and $ℒ$ are finite-dimensional, then we can identify the linear spaces $𝒱\otimes ℒ$ with $Hom(𝒱,ℒ)$. Thus, a tensor $\sigma \in 𝒱\otimes ℒ$ can be understood as a linear function $\sigma :𝒱⟶ℒ$, and therefore, once two bases of the corresponding vector spaces have been fixed, a tensor may be identified with a specific matrix.

Now, let us consider a multiplex network $ℳ$ made of $M$ layers $\{G_{\alpha };1\le \alpha \le M\}$, $G_{\alpha }=(X_{\alpha },E_{\alpha })$, with $X_1=\mathrm{\cdots }=X_M=\{x_1,\mathrm{\cdots },x_N\}=X$, in order to describe it as a tensor product

$$ℳ=⟨X⟩\otimes ⟨\{{\mathrm{\ell }}_1,\mathrm{\cdots },{\mathrm{\ell }}_M\}⟩,$$ (51)

where ${\mathrm{\ell }}_i$ represents the layer $G_i$.

Linear combinations of a family of vectors are obtained by multiplying a finite number among them by nonzero scalars (usually real numbers) and adding up the results. The span of a family of vectors is the set of all their linear combinations. In the following, we will denote the span of a family of vectors $\{v_1,\mathrm{\cdots },v_m\}$ by

$$span(\{v_1,\mathrm{\cdots },v_m\})=⟨\{v_1,\mathrm{\cdots },v_m\}⟩.$$ (52)

Given the sets $\{x_1,\mathrm{\cdots },x_N\}$ and $\{{\mathrm{\ell }}_1,\mathrm{\cdots },{\mathrm{\ell }}_M\}$, we consider the formal vector spaces on $ℝ$ of all their linear combinations as follows:

$$𝒱=⟨\{x_1,\mathrm{\cdots },x_N\}⟩,$$ (53)

$$ℒ=⟨\{{\mathrm{\ell }}_1,\mathrm{\cdots },{\mathrm{\ell }}_M\}⟩.$$ (54)

It is straightforward to check that $\{x_1,\mathrm{\cdots },x_N\}$ and $\{{\mathrm{\ell }}_1,\mathrm{\cdots },{\mathrm{\ell }}_M\}$ are basis of $𝒱$ and $ℒ$ respectively, and therefore

$$\{x_i\otimes {\mathrm{\ell }}_{\alpha };1\le i\le N,1\le \alpha \le M\}$$ (55)

is a basis of $𝒱\otimes ℒ$. So, we may give $x_i\otimes {\mathrm{\ell }}_{\alpha }$ the intuitive meaning of “being in the node $i$ and in the layer ${\mathrm{\ell }}_{\alpha }$”.

Figure 6: (Color online). Schematic illustration of a two-layer multiplex network obtained by duplicating the network of Fig. 5, and connecting each node with its counterpart in the other layer.

	$x_1$	$x_2$	$x_3$
$x_1$	0	1	1
$x_2$	0	0	1
$x_3$	1	0	0

Table 1: The adjacency matrix of the monoplex in Fig. 5

Now, if we consider a monolayer network $G=(X,E)$ of $N$ nodes, with $V=⟨\{x_1,\mathrm{\cdots },x_N\}⟩$, we can identify $G$ with the linear transformation $\sigma :V⟶V$ such that the matrix associated to $\sigma$ with respect to the basis $X=\{x_1,\mathrm{\cdots },x_N\}$ is the adjacency matrix of $G$.

Thus, if the adjacency matrix of $G$ is $A$, we can find the set of nodes accessible from any node $i$ in one step by multiplying $A$ on the left by the $i^{\mathrm{th}}$ canonical basis row-vector. For example, the adjacency matrix of the graph in Fig. 5 is

(56)

From node 1, we can access in one step nodes 2 and 3, since

(57)

In the same way, a multilayer network $ℳ$ of $N$ nodes and with layers $\{{\mathrm{\ell }}_1,\mathrm{\cdots },{\mathrm{\ell }}_M\}$ can be identified with a linear transformation $\sigma :𝒱\otimes ℒ⟶𝒱\otimes ℒ$ where $X_{ℳ}=\{x_1,\mathrm{\cdots },x_N\}$,

$$𝒱=⟨\{x_1,\mathrm{\cdots },x_N\}⟩,$$ (58)

$$ℒ=⟨\{{\mathrm{\ell }}_1,\mathrm{\cdots },{\mathrm{\ell }}_M\}⟩.$$ (59)

Figure 7: (Color online). Schematic illustration of a generic two-layer network with interlayer connections.

It is easy to check that $ℳ$ is completely determined by the matrix associated to $\sigma$ with respect to the basis

$$\{x_i\otimes {\mathrm{\ell }}_{\alpha };1\le i\le N,1\le \alpha \le M\},$$ (60)

As an example, consider the monolayer network $G=(X,E)$, with $X=\{x_1,x_2,x_3\}$, whose adjacency matrix $A$ is given in Table 1.

		$x_1$		$x_2$		$x_3$
		$x_1\otimes {\mathrm{\ell }}_1$	$x_1\otimes {\mathrm{\ell }}_2$	$x_2\otimes {\mathrm{\ell }}_1$	$x_2\otimes {\mathrm{\ell }}_2$	$x_3\otimes {\mathrm{\ell }}_1$	$x_3\otimes {\mathrm{\ell }}_2$
$x_1$	$x_1\otimes {\mathrm{\ell }}_1$	0	1	1	0	1	0
	$x_1\otimes {\mathrm{\ell }}_2$	1	0	0	1	0	1
$x_2$	$x_2\otimes {\mathrm{\ell }}_1$	0	0	0	1	1	0
	$x_2\otimes {\mathrm{\ell }}_2$	0	0	1	0	0	1
$x_3$	$x_3\otimes {\mathrm{\ell }}_1$	1	0	0	0	0	1
	$x_3\otimes {\mathrm{\ell }}_2$	0	1	0	0	1	0

Table 2: Adjacency matrix of the duplex obtained by duplicating the network of Fig. 5, and connecting each node with its counterpart in the other layer.

Now consider the multiplex network $ℳ$ with layers $\{{\mathrm{\ell }}_1,{\mathrm{\ell }}_2\}$, and nodes $X_{ℳ}=\{x_1,x_2,x_3\}$, obtained by duplicating the previous monoplex network in both layers, and connecting each node with its counterpart in the other layer (Fig. 6). The adjacency matrix of $ℳ$ is given in Table 2.

Of course, the specific matrix representing a tensor depends on the way we order the elements of the basis chosen.

$$\begin{array}{c}\hfill \{x_i\otimes {\mathrm{\ell }}_{\alpha };i\in \{1,\mathrm{\cdots },N\},\alpha \in \{1,\mathrm{\cdots },M\}\},\end{array}$$ (61)

However, if $A$ and $B$ are two different matrices assigned to the same tensor, there exists a permutation matrix $P$ such that $B=P\cdot A\cdot P^{-1}$, and thus both matrices have the same spectral properties (see Sec. 2.2.4).

If in the previous example we swap the order of layers and nodes, we get a different adjacency matrix, called supra-adjacency matrix of $ℳ$ (Table 3), which can be written in the usual form

(62)

where $A_i$ is the adjacency matrix of layer ${\mathrm{\ell }}_i$. Note that, unlike the case of multiplex networks, the blocks in the supra-adjacency matrix of a general multilayer networks are not necessarily square matrices. It is worth mentioning the dual roles between layers and nodes that may be observed by comparing Table 2 and Table 3.

An example of a generic 2-layer network, can be seen in Fig. 7, where we can pass in one step from node $x_1\otimes {\mathrm{\ell }}_1$ to node $x_2\otimes {\mathrm{\ell }}_2$, and from node $x_3\otimes {\mathrm{\ell }}_1$ to node $x_1\otimes {\mathrm{\ell }}_2$. Its adjacency matrix is listed in Table 4. It is important to stress that while the adjacency matrix of a multilayer network with $M$ layers and $N$ nodes has $N^2{M}^2$ entries, the adjacency matrix of a multiplex network with the same layers and nodes is completely determined by only $N^{2}M+M^2$ elements. In fact, a multiplex network of $M$ layers is completely determined by the $M$ adjacency matrices corresponding to the layers and its influence matrix $W=(w_{\alpha \beta })\in {ℝ}^{M\times M}$, i.e. the non-negative matrix $W\ge 0$ such that $w_{\alpha \beta }$ is the influence of the layer $G_{\alpha }$ on the layer $G_{\beta }$.

		${\mathrm{\ell }}_1$			${\mathrm{\ell }}_2$
		$x_1\otimes {\mathrm{\ell }}_1$	$x_2\otimes {\mathrm{\ell }}_1$	$x_3\otimes {\mathrm{\ell }}_1$	$x_1\otimes {\mathrm{\ell }}_2$	$x_2\otimes {\mathrm{\ell }}_2$	$x_3\otimes {\mathrm{\ell }}_2$
${\mathrm{\ell }}_1$	$x_1\otimes {\mathrm{\ell }}_1$	0	1	1	1	0	0
	$x_2\otimes {\mathrm{\ell }}_1$	0	0	1	0	1	0
	$x_3\otimes {\mathrm{\ell }}_1$	1	0	0	0	0	1
${\mathrm{\ell }}_2$	$x_1\otimes {\mathrm{\ell }}_2$	1	0	0	0	1	1
	$x_2\otimes {\mathrm{\ell }}_2$	0	1	0	0	0	1
	$x_3\otimes {\mathrm{\ell }}_2$	0	0	1	1	0	0

Table 3: The supra-adjacency matrix (see text for definition) corresponding to the duplex network in Fig. 6.

		$x_1$		$x_2$		$x_3$
		$x_1\otimes {\mathrm{\ell }}_1$	$x_1\otimes {\mathrm{\ell }}_2$	$x_2\otimes {\mathrm{\ell }}_1$	$x_2\otimes {\mathrm{\ell }}_2$	$x_3\otimes {\mathrm{\ell }}_1$	$x_3\otimes {\mathrm{\ell }}_2$
$x_1$	$x_1\otimes {\mathrm{\ell }}_1$	0	1	1	1	1	0
	$x_1\otimes {\mathrm{\ell }}_2$	1	0	0	1	0	1
$x_2$	$x_2\otimes {\mathrm{\ell }}_1$	0	0	0	1	1	0
	$x_2\otimes {\mathrm{\ell }}_2$	0	0	1	0	0	1
$x_3$	$x_3\otimes {\mathrm{\ell }}_1$	1	1	0	0	0	1
	$x_3\otimes {\mathrm{\ell }}_2$	0	1	0	0	1	0

Table 4: The adjacency matrix of the two-layer network with interlayer connections sketched in Fig. 7.

Multilayer networks, multidimensional networks, hypergraphs, and some other objects can be represented with tensors, which represent a convenient formalism to implement different models [103]. Specifically, tensor-decomposition methods [103, 104] and multiway data analysis [105] have been used to study various types of networks. These kind of methods are based on representing multilayer networks as adjacency higher-order tensors and then applying generalizations of methods such as Singular Value Decomposition (SVD) [106], and the combination of CANDECOMP (canonical decomposition) by Carroll and Chang [107] and PARAFAC (parallel factors) by Harshman [108] leading to CANDECOMP/PARAFAC (CP). These methods have been used to extract communities [104], to rank nodes [109, 110] and to perform data mining [103, 111, 112].

2.4 Correlations in multiplex networks

Multiplex networks encode significantly more information than their single layers taken in isolation, since they include correlations between the role of the nodes in different layers and between statistical properties of the single layers. Discovering the statistically significant correlations in multilayer networks is likely to be one of the major goals of network science for the next years. Here we outline the major types of correlations explored so far. We distinguish between:

• Interlayer degree correlations
  Generally speaking these correlations are able to indicate if the hubs in one layer are also the hubs, or they are typically low degree nodes, in the other layer.

• Overlap and multidegree
  The node connectivity patterns can be correlated in two or more layers and these correlations can be captured by the overlap of the links. For example, we usually have a large fraction of friends with which we communicate through multiple means of communications, such as phone, email and instant messaging. This implies that the mobile phone social network has a significant overlap with the one of email communication or the one of instant messaging. The overlap of the links can be quantified by the global or local overlap between two layers, or by the multidegrees of the nodes that determine the specific overlapping pattern.

• Multistrengths and inverse multiparticipation ratio of weighted multiplex
  The weights of the links in the different layers can be correlated with other structural properties of the multiplex. For example, we tend to cite collaborators differently from other scientists. These types of correlations between structural properties of the multiplex and the weights distribution are captured by the multistrengths and inverse multiparticipation ratio.

• Node pairwise multiplexity
  When the nodes are not all active in all layers two nodes can have correlated activity patterns. For example they can be active on the same, or on different layers. These correlations are captured by the Node Pairwise Multiplexity.

• Layer pairwise multiplexity
  When the nodes are not all active in all layers, two layers can have correlated activity patterns. For example they can contain the same active nodes, or different active nodes. These correlations are captured by the Layer Pairwise Multiplexity.

2.4.1 Degree correlations in multiplex networks

Every node $i=1,2,\mathrm{\dots },N$ of a multiplex has a degree $k_i^{[\alpha ]}$ in each layer $\alpha =1,2,\mathrm{\dots },M$. The degrees of the same node in different layers can be correlated. For example, a node that is a hub in the scientific collaboration network is likely to be a hub also in the citation network between scientists. Therefore, the degree in the collaboration network is positively correlated with that of the citation network. Negative correlations also exist, when the hubs of one layer are not the hubs of another layer. The methods to evaluate the degree correlations between a layer $\alpha$ and a layer $\beta$ are the following:

• Full characterization of the matrix $P(k^{\alpha },k^{\beta })$.
  One can construct the matrix

  $$P(k^{\alpha },k^{\beta })=\frac{N(k^{\alpha },k^{\beta })}{N},$$ (63)

  where $N(k^{\alpha },k^{\beta })$ is the number of nodes that have degree $k^{\alpha }$ in layer $\alpha$ and degree $k^{\beta }$ in layer $\beta$. From this matrix, the full pattern of correlations can be determined.

• Average degree in layer $\alpha$ conditioned on the degree of the node in layer $\beta$
  A more coarse-grained measure of correlation is $\overline{k^{\alpha }}(k^{\beta })$, i.e. the average degree of a node in layer $\alpha$ conditioned to the degree of the same node in layer $\beta$:

  $${\overline{k}}^{\alpha }(k^{\beta })=\sum _{k^{\alpha }}{k}^{\alpha }P(k^{\alpha }|k^{\beta })=\frac{{\sum }_{k^{\alpha }}{k}^{\alpha }P(k^{\alpha },k^{\beta })}{{\sum }_{k^{\alpha }}P(k^{\alpha },k^{\beta })}.$$ (64)

  If this function does not depend on $k^{\beta }$, the degrees in the two layers are uncorrelated. If this function is increasing (decreasing) in $k^{\beta }$, the degrees of the nodes in the two layers are positively (negatively) correlated.

• Pearson, Spearman and Kendall correlations coefficients
  Even more coarse-grained correlation measures are the Pearson, the Spearman and the Kendall’s correlations coefficients.

  The Pearson correlation coefficient $r_{\alpha \beta }$ is given by

  $$r_{\alpha \beta }=\frac{⟨k_i^{[\alpha ]}{k}_i^{[\beta ]}⟩-⟨k_i^{[\alpha ]}⟩⟨k_i^{[\beta ]}⟩,}{{\sigma }_{\alpha }{\sigma }_{\beta }}$$ (65)

  where ${\sigma }_{\alpha }=\sqrt{⟨k_i^{[\alpha ]}{k}_i^{[\alpha ]}⟩-{⟨k_i^{[\alpha ]}⟩}^2}$. The Pearson correlation coefficient can be dominated by the correlations of the high degree nodes if the degree distributions are broad.

  The Spearman correlation coefficient ${\rho }_{\alpha \beta }$ between the degree sequences $\{k_i^{[\alpha ]}\}$ and $\{k_i^{[\beta ]}\}$ in the two layers $\alpha$ and $\beta$ is given by

  $${\rho }_{\alpha \beta }=\frac{⟨x_i^{\alpha }{x}_i^{\beta }⟩-⟨x_i^{\alpha }⟩⟨x_i^{\beta }⟩}{\sigma (x^{\alpha })\sigma (x_i^{\beta })},$$ (66)

  where $x_i^{\alpha }$ is the rank of the degree $k_i^{[\alpha ]}$ in the sequence $\{k_i^{[\alpha ]}\}$ and $x_i^{\beta }$ is the rank of the degree $k_i^{[\beta ]}$ in the sequence $\{k_i^{[\beta ]}\}$. Moreover, $\sigma (x_i^{\alpha })=\sqrt{⟨{(x_i^{\alpha })}^2⟩-{⟨x_i^{\alpha }⟩}^2}$ and $\sigma (x_i^{\beta })=\sqrt{⟨{(x_i^{\beta })}^2⟩-{⟨x_i^{\beta }⟩}^2}$. The Spearman coefficient has the problem that the ranks of the degrees in each degree sequence are not uniquely defined because degree sequences must always have some degeneracy. Therefore, the Spearman correlation coefficient is not a uniquely defined number.

  The Kendall’s $\tau$ correlation coefficient between the degree sequences $\{k_i^{[\alpha ]}\}$ and $\{k_i^{[\beta ]}\}$ is a measure that takes into account the sequence of ranks $\{x_i^{\alpha }\}$ and $\{x_i^{\beta }\}$. A pair of nodes $i$ and $j$ is concordant if their ranks have the same order in the two sequences, i.e. $(x_i^{\alpha }-x_j^{\alpha })(x_i^{\beta }-x_j^{\beta })>0$, and discordant otherwise. The Kendall’s $\tau$ is defined in terms of the number $n_c$ of concordant pairs and the number $n_d$ of discordant pairs and is given by

  $$\tau =\frac{n_c-n_d}{\sqrt{(n_0-n_1)(n_0-n_2)}}.$$ (67)

  In the equation above, $n_0=1/2N(N-1)$ and the terms $n_1$ and $n_2$ account for the degeneracy of the ranks and are given by

  $n_1={\displaystyle \frac{1}{2}}{\displaystyle \sum _n}{u}_n(u_n-1),$

  $n_2={\displaystyle \frac{1}{2}}{\displaystyle \sum _n}{v}_n(v_n-1),$ (68)

  where $u_n$ is the number of nodes in the $n^{\mathrm{th}}$ tied group of the degree sequence $\{k_i^{[\alpha ]}\}$, and $v_n$ is the number of nodes in the $n^{\mathrm{th}}$ tied group of the degree sequence $\{k_i^{[\beta ]}\}$.

The level of degree correlations in the multiplex networks can be tuned by reassigning new labels to the nodes of the multiplexes [48]. Let us for simplicity consider a duplex where we have two degree sequences $\{k_i^{[1]}\}$ and $\{k_i^{[2]}\}$ as proposed in Ref. [48]. The label of the nodes in layer 1 and layer 2 can be reassigned in order to generate the desired correlations between the two degree sequences. Assume we have ranked the degree sequences in the two layers. If the labels of the nodes in both sequences are given according to the increasing rank of the degree in each layer, then the sequences are maximally-positive correlated (MP), i.e. the nodes of equal rank in the two sequences are replica nodes of the multiplex. Conversely, if the label of a node in one layer is given according to the increasing rank of the degree in the same layer, and the label of a node in the other layer is given according to the decreasing rank of the degree in the same layer, the two degree sequences are maximally-negative correlated (MN). In Fig. 8, an example is given for the construction of maximally-positive (MP) correlations and maximally-negative (MN) correlations from two given degree sequence in two layers of a multiplex network.

Figure 8: (Color online). Schematic illustration of three kinds of correlated multiplex networks, maximally-positive (MP), uncorrelated (UC), and maximally-negative (MN). Each layer of the networks has different types of links, indicated by solid and dashed links, respectively. Reprinted figure with permission from Ref. [48]. ©  2014 by the American Physical Society.

2.4.2 Overlap and multidegree

A large variety of data sets, including the multiplex airport network, on-line social games, collaboration and citation networks [63, 78, 113], display a significant overlap of the links. This means that the number of links present at the same time in two different layers is not negligible with respect to the total number of links in the two layers.

The total overlap $O^{\alpha \beta }$ between two layers $\alpha$ and $\beta$ [49, 63] is defined as the total number of links that are in common between layer $\alpha$ and layer $\beta$: