Mathematical Formulation of Multilayer Networks

A network representation is useful for describing the structure of a large variety of complex systems. However, most real and engineered systems have multiple subsystems and layers of connectivity, and the data produced by such systems are very rich. Achieving a deep understanding of such systems necessitates generalizing “traditional” network theory, and the newfound deluge of data now makes it possible to test increasingly general frameworks for the study of networks. In particular, although adjacency matrices are useful to describe traditional single-layer networks, such a representation is insufficient for the analysis and description of multiplex and time-dependent networks. One must therefore develop a more general mathematical framework to cope with the challenges posed by multilayer complex systems. In this paper, we introduce a tensorial framework to study multilayer networks, and we discuss the generalization of several important network descriptors and dynamical processes—including degree centrality, clustering coefficients, eigenvector centrality, modularity, von Neumann entropy, and diffusion—for this framework. We examine the impact of different choices in constructing these generalizations, and we illustrate how to obtain known results for the special cases of single-layer and multiplex networks. Our tensorial approach will be helpful for tackling pressing problems in multilayer complex systems, such as inferring who is influencing whom (and by which media) in multichannel social networks and developing routing techniques for multimodal transportation systems.

Popular Summary

Describing a social network based on a particular type of human social interaction, say, Facebook, is conceptually simple: a set of nodes representing the people involved in such a network, linked by their Facebook connections. But, what kind of network structure would one have if all modes of social interactions between the same people are taken into account and if one mode of interaction can influence another? Here, the notion of a “multiplex” network becomes necessary. Indeed, the scientific interest in multiplex networks has recently seen a surge. However, a fundamental scientific language that can be used consistently and broadly across the many disciplines that are involved in complex systems research was still missing. This absence is a major obstacle to further progress in this topical area of current interest. In this paper, we develop such a language, employing the concept of tensors that is widely used to describe a multitude of degrees of freedom associated with a single entity.

Our tensorial formalism provides a unified framework that makes it possible to describe both traditional “monoplex” (i.e., single-type links) and multiplex networks. Each type of interaction between the nodes is described by a single-layer network. The different modes of interaction are then described by different layers of networks. But, a node from one layer can be linked to another node in any other layer, leading to “cross talks” between the layers. High-dimensional tensors naturally capture such multidimensional patterns of connectivity. Having first developed a rigorous tensorial definition of such multilayer structures, we have also used it to generalize the many important diagnostic concepts previously known only to traditional monoplex networks, including degree centrality, clustering coefficients, and modularity.

We think that the conceptual simplicity and the fundamental rigor of our formalism will power the further development of our understanding of multiplex networks.

Figure 1

Schematic of a multilayer network. When studying ordinary networks, one represents the interaction of entities (i.e., nodes) using an adjacency matrix, which encodes the intensity of each pairwise interrelationship. However, as shown in the left panel, entities can interact in different ways (e.g., depending on the environment in which they are embedded). In this panel, each layer of a multilayer network corresponds to a different type of interaction (e.g., social relationships, business collaborations, etc.) and is represented by a different adjacency matrix. As shown in the right panel, the layers can also be interconnected. One thereby obtains a new type of relationship, which complicates the description of networked systems.

Figure 2

Schematic of multilayer networks for three different topologies. We show three four-layer multiplex networks (and the corresponding network of layers as an inset in the top-left corners) and recall that each interlayer edge connects a node with one of its counterparts in another layer.

Figure 3

Schematics of (left) projected and (right) overlay monoplex networks obtained from a multilayer network. Both types of single-layer networks are weighted, but their edges have different weights. One obtains an overlay network using the contraction operator and thus neglects the influence of interlayer connections.

Figure 4

Schematic of closing triangles in multiplex networks. Triangles can be closed using intralayer connections from different layers. In the figure, we show two different situations that can arise. For example, the left panel might represent a multilayer social network in which nodes $A$ and $B$ are friends of node $C$ but are not friends with each other (first layer), but nodes $A$ and $B$ still have a social tie because they work in the same company even though node $C$ does not work there (third layer). In the right panel, one might imagine that each layer corresponds to a different online social network: Perhaps node $B$ tweets about an item; node $C$ sees node $B$’s post on Twitter (first layer) and then posts the same item on Facebook (second layer); node $A$ then sees this post and blogs about it (third layer), and node $B$ reads this blog entry.

Figure 5

Schematic of a random walk (dotted trajectories) in a multiplex network. A walker can jump between nodes within the same layer, or it might switch to another layer. This illustration evinces how multiplexity allows a random walker to move between nodes that belong to different (disconnected) components on a given layer.