Multidimensional network

[1] [2][3][4][5][6][7] Increasingly sophisticated attempts to model real-world systems as multidimensional networks have yielded valuable insight in the fields of social network analysis,[3][4][8][9][10][11][12] economics, urban and international transport,[13][14][15] ecology,[16][17][18][19] psychology,[20][21] medicine, biology,[22] commerce, climatology, physics,[23] computational neuroscience,[24][25][26][27] operations management, and finance.

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[28][29] terminology to describe specific network configurations (e.g., multiplex, multilayer, multilevel, multidimensional, multirelational, interconnected).

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.

[3] In a non-interconnected multidimensional network, where interlayer links are absent, the degree of a node is represented by a vector of length

[4] When extended to interconnected multilayer networks, i.e. those systems where nodes are connected across layers, the concept of centrality is better understood in terms of versatility.

[10] For unidimensional networks, the HITS algorithm has been originally introduced by Jon Kleinberg to rate Web Pages.

These properties are preserved by the natural extension of the equations proposed by Kleinberg to the case of interconnected multilayer networks, given by

[10] 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.

It is easy to show that the solution of this equation is equivalent to the leading eigenvector of the transition matrix.

[40] For interconnected multilayer networks, the transition tensor governing the dynamics of the random walkers within and across layers is given by

As its unidimensional counterpart, PageRank versatility consists of two contributions: one encoding a classical random walk with rate

[4][41][42] 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,[42] while others have experimented with different definitions of random walks and 3-cycles in multidimensional networks.

[4][41] While cross-dimensional structures have been studied previously,[43][44] they fail to detect more subtle associations found in some networks.

[3][8][9][45] 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.

A generalization of the well-known modularity maximization method for community discovery has been originally proposed by Mucha et al.[8] This multiresolution method assumes a three-dimensional tensor representation of the network connectivity within layers, as for edge-colored multigraphs, and a three-dimensional tensor representation of the network connectivity across layers.

Methods based on statistical inference, generalizing existing approaches introduced for unidimensional networks, have been proposed.

Nevertheless, for multilayer systems with a small number of layers, it has been shown that the method performs optimally in the majority of cases.

Extending these analyses to a multidimensional network requires incorporating additional connections between nodes into the algorithms currently used (e.g., Dijkstra's).

Current approaches include collapsing multi-link connections between nodes in a preprocessing step before performing variations on a breadth-first search of the network.

[39] In a multidimensional network in which different dimensions of connection have different real-world values, statistics characterizing the distribution of links to the various classes are of interest.

Additional dimensions of communication provide a more faithful representation of reality and may highlight these patterns or diminish them.

[23][52] One result common to many studies is that diffusion in multiplex networks, a special type of multilayer system, exhibits two regimes: 1) the weight of inter-layer links, connecting layers each other, is not high enough and the multiplex system behaves like two (or more) uncoupled networks; 2) the weight of inter-layer links is high enough that layers are coupled each other, raising unexpected physical phenomena.

[53] In fact, all network descriptors depending on some diffusive process, from centrality measures to community detection, are affected by the layer-layer coupling.

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

[15][54] The problem of classical diffusion in complex networks is to understand how a quantity will flow through the system and how much time it will take to reach the stationary state.

Classical diffusion in multiplex networks has been recently studied by introducing the concept of supra-adjacency matrix,[55] later recognized as a special flattening of the multilayer adjacency tensor.

[3] In tensorial notation, the diffusion equation on the top of a general multilayer system can be written, concisely, as

Many of the properties of this diffusion process are completely understood in terms of the second smallest eigenvalue of the Laplacian tensor.

[55] Recently, how information (or diseases) spread through a multilayer system has been the subject of intense research.