In network theory, multidimensional networks, a special type of multilayer network, are networks with multiple kinds of relations. Increasingly sophisticated attempts to model real-world systems as multidimensional networks have yielded valuable insight in the fields of social network analysis, economics, urban and international transport, ecology, psychology, medicine, biology, commerce, climatology, physics, computational neuroscience, operations management, and finance.
Terminology The rapid exploration of complex networks in recent years has been dogged by a lack of standardized naming conventions, as various groups use overlapping and contradictory terminology to describe specific network configurations (e.g., multiplex, multilayer, multilevel, multidimensional, multirelational, interconnected). To fully leverage the dataset information on the directional nature of the communications, some authors consider only direct networks without any labels on vertices, and introduce the definition of edge-labeled multigraphs which can cover many multidimensional situations. Ch. 4: "Here we introduce the definition of edge-labeled multigraph which can cover many multidimensional situations. To fully leverage the dataset information on the directional nature of the communications, we consider only direct networks without any labels on vertices". The term "fully multidimensional" has also been used to refer to a multipartite edge-labeled multigraph. Multidimensional networks have also recently been reframed as specific instances of multilayer networks. In this case, there are as many layers as there are dimensions, and the links between nodes within each layer are simply all the links for a given dimension.
Definition
Unweighted multilayer networks In elementary network theory, a network is represented by a graph in which is the set of nodes and the links between nodes, typically represented as a tuple of nodes . While this basic formalization is useful for analyzing many systems, real world networks often have added complexity in the form of multiple types of relations between system elements. An early formalization of this idea came through its application in the field of social network analysis (see, e.g., and papers on relational algebras in social networks) in which multiple forms of social connection between people were represented by multiple types of links.
To accommodate the presence of more than one type of link, a multidimensional network is represented by a triple , where is a set of dimensions (or layers), each member of which is a different type of link, and consists of triples with and .
Note that as in all directed graphs, the links and are distinct.
By convention, the number of links between two nodes in a given dimension is either 0 or 1 in a multidimensional network. However, the total number of links between two nodes across all dimensions is less than or equal to .
Weighted multilayer networks In the case of a weighted network, this triplet is expanded to a quadruplet , where is the weight on the link between and in the dimension . Further, as is often useful in social network analysis, link weights may take on positive or negative values. Such signed networks can better reflect relations like amity and enmity in social networks. Alternatively, link signs may be figured as dimensions themselves, e.g. where and This approach has particular value when considering unweighted networks. This conception of dimensionality can be expanded should attributes in multiple dimensions need specification. In this instance, links are n-tuples . Such an expanded formulation, in which links may exist within multiple dimensions, is uncommon but has been used in the study of multidimensional time-varying networks.
General formulation in terms of tensors
Whereas unidimensional networks have two-dimensional adjacency matrices of size , in a multidimensional network with dimensions, the adjacency matrix becomes a multilayer adjacency tensor, a four-dimensional matrix of size . By using index notation, adjacency matrices can be indicated by , to encode connections between nodes and , whereas multilayer adjacency tensors are indicated by , to encode connections between node in layer and node in layer . As in unidimensional matrices, directed links, signed links, and weights are all easily accommodated by this framework.
In the case of multiplex networks, which are special types of multilayer networks where nodes can not be interconnected with other nodes in other layers, a three-dimensional matrix of size with entries is enough to represent the structure of the system by encoding connections between nodes and in layer .
Multidimensional network-specific definitions
Multi-layer neighbors In a multidimensional network, the neighbors of some node are all nodes connected to across dimensions.
Multi-layer path length A path between two nodes in a multidimensional network can be represented by a vector r in which the th entry in r is the number of links traversed in the th dimension of .M. Magnani, A. Monreale, G. Rossetti, F. Giannotti: "On multidimensional network measures", SEBD 2013, Rocella Jonica, Italy As with overlapping degree, the sum of these elements can be taken as a rough measure of a path length between two nodes.
Network of layers The existence of multiple layers (or dimensions) allows to introduce the new concept of network of layers, peculiar of multilayer networks. In fact, layers might be interconnected in such a way that their structure can be described by a network, as shown in the figure.
The network of layers is usually weighted (and might be directed), although, in general, the weights depends on the application of interest. A simple approach is, for each pair of layers, to sum all of the weights in the connections between their nodes to obtain edge weights that can be encoded into a matrix . The rank-2 adjacency tensor, representing the underlying network of layers in the space is given by
where is the canonical matrix with all components equal to zero except for the entry corresponding to row and column , that is equal to one. Using the tensorial notation, it is possible to obtain the (weighted) network of layers from the multilayer adjacency tensor as .
Centrality measures
Degree In a non-interconnected multidimensional network, where interlayer links are absent, the degree of a node is represented by a vector of length . Here is an alternative way to denote the number of layers in multilayer networks. However, for some computations it may be more useful to simply sum the number of links adjacent to a node across all dimensions. This is the overlapping degree: . As with unidimensional networks, distinction may similarly be drawn between incoming links and outgoing links. If interlayer links are present, the above definition must be adapted to account for them, and the multilayer degree is given by
where the tensors and have all components equal to 1. The heterogeneity in the number of connections of a node across the different layers can be taken into account through the participation coefficient.
Versatility as multilayer centrality
When extended to interconnected multilayer networks, i.e. those systems where nodes are connected across layers, the concept of centrality is better understood in terms of versatility. Nodes that are not central in each layer might be the most important for the multilayer systems in certain scenarios. For instance, this is the case where two layers encode different networks with only one node in common: it is very likely that such a node will have the highest centrality score because it is responsible for the information flow across layers.
Eigenvector versatility
As for unidimensional networks, eigenvector versatility can be defined as the solution of the eigenvalue problem given by , where Einstein summation convention is used for sake of simplicity. Here, gives the multilayer generalization of Bonacich's eigenvector centrality per node per layer. The overall eigenvector versatility is simply obtained by summing up the scores across layers as .
Katz versatility
As for its unidimensional counterpart, the Katz versatility is obtained as the solution of the tensorial equation , where , is a constant smaller than the largest eigenvalue and is another constant generally equal to 1. The overall Katz versatility is simply obtained by summing up the scores across layers as .
HITS versatility
For unidimensional networks, the HITS algorithm has been originally introduced by Jon Kleinberg to rate Web Pages. The basic assumption of the algorithm is that relevant pages, named authorities, are pointed by special Web pages, named hubs. This mechanism can be mathematically described by two coupled equations which reduce to two eigenvalue problems. When the network is undirected, Authority and Hub centrality are equivalent to eigenvector centrality. These properties are preserved by the natural extension of the equations proposed by Kleinberg to the case of interconnected multilayer networks, given by and , where indicates the transpose operator, and indicate hub and authority centrality, respectively. By contracting the hub and authority tensors, one obtains the overall versatilities as and , respectively.
PageRank versatility
PageRank, originally introduced to rank web pages, can also be considered as a measure of centrality for interconnected multilayer networks.
It is worth remarking that PageRank can be seen as the steady-state solution of a special Markov process on the top of the network. Random walkers explore the network according to a special transition matrix and their dynamics is governed by a random walk master equation. It is easy to show that the solution of this equation is equivalent to the leading eigenvector of the transition matrix.
Random walks have been defined also in the case of interconnected multilayer networks and edge-colored multigraphs (also known as multiplex networks). For interconnected multilayer networks, the transition tensor governing the dynamics of the random walkers within and across layers is given by , where is a constant, generally set to 0.85, is the number of nodes and is the number of layers or dimensions. Here, might be named Google tensor and is the rank-4 tensor with all components equal to 1.
As its unidimensional counterpart, PageRank versatility consists of two contributions: one encoding a classical random walk with rate and one encoding teleportation across nodes and layers with rate .
If we indicate by the eigentensor of the Google tensor , denoting the steady-state probability to find the walker in node and layer , the multilayer PageRank is obtained by summing up over layers the eigentensor:
Triadic closure and clustering coefficients
Like many other network statistics, the meaning of a clustering coefficient becomes ambiguous in multidimensional networks, due to the fact that triples may be closed in different dimensions than they originated. Several attempts have been made to define local clustering coefficients, but these attempts have highlighted the fact that the concept must be fundamentally different in higher dimensions: some groups have based their work off of non-standard definitions, while others have experimented with different definitions of random walks and 3-cycles in multidimensional networks.
Community discovery While cross-dimensional structures have been studied previously, they fail to detect more subtle associations found in some networks. Taking a slightly different take on the definition of "community" in the case of multidimensional networks allows for reliable identification of communities without the requirement that nodes be in direct contact with each other. For instance, two people who never communicate directly yet still browse many of the same websites would be viable candidates for this sort of algorithm.