Source-linked AI summary
Centrality in Interconnected Multilayer Networks
Manlio De Domenico, Albert Solé-Ribalta, Elisa Omodei, Sergio Gómez, Alex Arenas
TL;DR
The paper addresses how to define node centrality when real-world systems contain multiple interconnected relationship levels. It extends monoplex centrality measures through tensorial formalism and shows that aggregation into a weighted monoplex can substantially alter node rankings, while multilayer measures account for the full interconnected structure.
Problem
Defining influential nodes is nontrivial in interconnected multilayer networks, and heuristic aggregation across layers may not capture their real importance.
Method
The paper extends topology- and dynamics-based monoplex centrality measures using tensorial operations on the full interconnected multilayer network.
Results
The framework shows analytically and numerically that centrality definitions generally differ from naive layer-wise addition, while aggregated monoplexes can produce relevant ranking differences.
Takeaways & Limitations
Centrality analysis of interconnected multilayer networks should preserve inter-layer connections rather than rely generally on aggregated monoplexes.
Abstract
from arXiv · showhide
Real-world complex systems exhibit multiple levels of relationships. In many cases, they require to be modeled by interconnected multilayer networks, characterizing interactions on several levels simultaneously. It is of crucial importance in many fields, from economics to biology, from urban planning to social sciences, to identify the most (or the less) influent nodes in a network. However, defining the centrality of actors in an interconnected structure is not trivial. In this paper, we capitalize on the tensorial formalism, recently proposed to characterize and investigate this kind of complex topologies, to show how several centrality measures -- well-known in the case of standard ("monoplex") networks -- can be extended naturally to the realm of interconnected multiplexes. We consider diagnostics widely used in different fields, e.g., computer science, biology, communication and social sciences, to cite only some of them. We show, both theoretically and numerically, that using the weighted monoplex obtained by aggregating the multilayer network leads, in general, to relevant differences in ranking the nodes by their importance.
I. INTRODUCTION
Interconnected multilayer networks represent multiple relationship levels while preserving the costs or links between layers. The paper extends centrality measures to these structures and shows that aggregation can substantially change node rankings.
- I. INTRODUCTION: Single-edge network models can oversimplify multiple relationships and produce misleading structural interpretations.Temporal networks illustrate the broader risk of losing relationship structure when distinct dimensions are collapsed.
- I. INTRODUCTION: Interconnected multilayer networks are distinct from interdependent networks because many or all nodes may have counterparts across layers.The paper emphasizes this distinction before developing its centrality framework.
- I. INTRODUCTION: Multiplexes label different relationship types between the same actors, whereas interconnected multilayer networks also represent movement between layers.For transportation systems, switching between subway and bus layers may incur economic or commuting-time costs.
- I. INTRODUCTION: The paper extends widely adopted centrality measures to interconnected multilayer networks using tensorial formalism and considers topology- and dynamics-based diagnostics.Dynamic measures are validated against detailed simulations.
- I. INTRODUCTION: Aggregating the multilayer network into a weighted monoplex can lead to relevant differences in node-importance rankings.The paper develops its framework across the introduction, tensorial notation, centrality definitions, and conclusions.
II. TENSORIAL NOTATION
The paper uses compact tensorial notation to encode intra-layer and inter-layer relationships in a single interconnected multilayer structure. This representation supports path calculations and clarifies why aggregation generally fails to preserve the original topology.
- II. TENSORIAL NOTATION: Standard adjacency matrices capture edge-colored graphs but are limited for interconnected multiplexes with more complex or time-varying relationships.Higher-order tensors and algebras provide the proposed framework for this complexity.
- II. TENSORIAL NOTATION: Tensorial notation uses canonical vectors and tensors to represent interconnected multilayer networks compactly and to generalize network calculations.The formalism distinguishes covariant row vectors, contravariant column vectors, and canonical vectors assigned to nodes.
- II. TENSORIAL NOTATION: A multilayer system assigns relationship types to layers, distinguishing node indices from layer indices in tensorial equations.Latin letters denote nodes, while Greek letters denote layers.
- II. TENSORIAL NOTATION: The rank-4 multilayer adjacency tensor M_iα_jβ generalizes a monoplex adjacency matrix by encoding relationship intensity between nodes across layers.It also accommodates actors present in only some layers through empty nodes and zero-valued associated edges.
- II. TENSORIAL NOTATION: Tensorial calculations require care because repeated indices encode contractions and products can represent Kronecker products rather than ordinary scalar multiplication.The paper also restricts an abbreviated matrix notation when canonical tensors explicitly enter calculations.
- II. TENSORIAL NOTATION: Aggregation contracts layer indices into a monoplex, but this loses inter-layer connection information.When that information matters, the multilayer tensor must instead retain inter-layer structure through contraction with an all-ones tensor.
- II. TENSORIAL NOTATION: Tensor products and contractions represent paths across layers, whereas aggregate calculations may include inter-layer connections as self-loops before further operations.The same framework extends from length-2 paths to longer paths.
- II. TENSORIAL NOTATION: The aggregated graph cannot generally serve as a good proxy for the interconnected topology.The distinction follows from the different path calculations produced by preserving versus collapsing layer structure.
III. CENTRALITY IN INTERCONNECTED NETWORKS
The section defines node centrality in interconnected multilayer networks through tensorial operations, while emphasizing that global importance must account for inter-layer relationships rather than rely on heuristic aggregation. It also illustrates how multilayer random walks can traverse otherwise disconnected layer components.
- Tensorial operations on the multilayer adjacency tensor, canonical vectors, and canonical tensors provide a natural extension of single-layer centrality.This establishes the algebraic basis for defining node centrality in multilayer networks.
- Global node importance aggregates information across layers, but heuristic combinations can depend on arbitrary choices and misrepresent importance.The tensorial approach incorporates multilayer complexity without external assumptions.
- A multilayer random walker can move within a layer or switch layers, reaching nodes in components disconnected on an individual layer.The figure uses dotted trajectories to depict these within-layer and inter-layer moves.
A. Centrality based on dynamical properties
The paper extends random-walk-based centrality measures to interconnected multilayer networks using transition tensors and steady-state eigentensors. These measures account for inter-layer navigation, while aggregating layer information can substantially affect node importance rankings.
- Random-walk framework: The multilayer steady state is obtained from the leading eigentensor of the transition tensor, yielding the probability of finding a walker at each node-layer pair.This extends the monoplex leading-eigenvector formulation to higher-order tensors.
- Random-walk framework: Random walks on multilayer networks allow centrality measures to account for within-layer movement and switching between interconnected layers.The walker may jump to a same-layer neighbor or switch to its counterpart in another layer.
- Occupation centrality: Random-walk occupation centrality is proportional to node strength in the classical weighted case, with strength including inter-layer connections.The strength tensor normalizes transition probabilities, and the resulting occupation probability satisfies Πiα ∝ siα.
- Occupation centrality: Summing occupation centrality across layers is the unique correct aggregation in this framework, and aggregation agrees with the interconnected calculation when inter-layer edges are represented as self-loops.If inter-layer edges have equal strength for all nodes, the result is proportional to aggregated-network degree without requiring self-loops.
- Validation: Simulation and theory agree excellently for the random-walk centrality, including the ξi measure, regardless of network size, layer count, or topology.The paper uses Monte Carlo simulations as a ground truth for the dynamical diagnostics.
- Ranking consequences: Accounting for inter-layer structure alters node centrality rankings, including rankings of highly ranked nodes in synthetic and empirical networks.The paper extends this dynamical framework to PageRank and random-walk betweenness and closeness centralities.
B. Centrality based on topological properties
The paper extends topology-based centrality measures, including eigenvector, Katz, HITS, betweenness, and closeness, to interconnected multilayer networks. These extensions account for the full interconnected structure rather than relying on aggregation before calculation or heuristic combination across layers.
- Eigenvector centrality: Eigenvector centrality is extended by solving a tensorial eigenvalue problem whose eigentensor encodes node centrality in each layer.The overall node score is obtained by contracting the eigentensor over layers.
- Eigenvector centrality: The multilayer eigenvector measure differs from both aggregated-monoplex centrality and heuristic aggregation of layerwise centralities.It is a mathematical extension of the original definition and accounts for the interconnected topology during calculation.
- Katz centrality: Katz centrality is generalized by defining a centrality tensor for each node and layer, then contracting it over layers to obtain node scores.The construction accounts for the whole interconnected topology and extends Katz’s equation to interconnected multilayer networks.
- HITS centrality: HITS centrality is extended with separate hub and authority tensors, whose layer contractions produce node-level hub and authority scores.For undirected interconnected multiplexes, hub and authority scores coincide with the corresponding eigenvector centrality.
- Centrality measures based on shortest path: Betweenness counts shortest paths through a node, while closeness averages inverse shortest-path costs across origins in the interconnected topology.Paths may traverse nodes and layers, with costs determined by edge weights and the application.
IV. CONCLUSIONS AND DISCUSSION
The paper formulates multiple centrality measures for interconnected multilayer networks, covering random navigation and topology-based definitions. In general, these measures differ from naive layerwise addition and have complex nonlinear forms.
- IV. CONCLUSIONS AND DISCUSSION: The paper presents mathematical formulations of centrality measures for interconnected multilayer networks.The definitions are grouped into measures based on random navigation and measures defined from topology itself.
- IV. CONCLUSIONS AND DISCUSSION: The multilayer definitions generally differ from naive addition across layers and adopt complex nonlinear forms.The results are presented as ready for complex-network analysis in applications including social sciences and transportation networks.
Appendix A: Eigenvalue problem with tensors
The appendix explains how tensor eigenvalue problems can be solved by unfolding multilayer tensors into lower-rank representations. A rank-4 adjacency tensor can be flattened into supra-matrices without changing the relevant spectral properties.
- Appendix A: Eigenvalue problem with tensors: Tensor eigenvalue problems can be addressed by unfolding tensors to lower-rank tensors.A rank-2 tensor can be flattened into a vector, and a rank-4 multilayer adjacency tensor can be unfolded into a squared rank-2 tensor.
- Appendix A: Eigenvalue problem with tensors: Flattening a rank-4 multilayer adjacency tensor produces an NL × NL supra-matrix representation.Here, L is the number of layers, and the resulting supra-matrix has NL components in its associated supra-vector.
- Appendix A: Eigenvalue problem with tensors: Different allowed unfoldings preserve the spectral properties of the resulting supra-matrix and can therefore solve the rank-4 tensor eigenvalue problem.The construction yields block adjacency matrices, commonly called supra-adjacency matrices.
Appendix B: Mean number of crossing times
The appendix defines the expected number of visits to a node-layer during random walks from an origin layer to a destination node. It derives this quantity from indicator variables and the absorbing transition tensor.
- Appendix B: Mean number of crossing times: The expected number of visits to node j in layer β is defined over M random walks from node o in layer σ to node d.The walks end when they reach the destination node, regardless of its layer.
- Appendix B: Mean number of crossing times: Indicator variables record whether walk m visits node j in layer β at time t.The indicator equals 1 for a visit and 0 otherwise.
- Appendix B: Mean number of crossing times: The visit probability conditional on origin node and layer is obtained through a frequentist interpretation of the walk indicators.Substitution into the preceding expression uses the absorbing transition tensor defined in Eq. (4).
Appendix C: Synthetic multiplex with given inter-layer assortativity
The appendix describes an algorithm for generating two-layer multiplex networks with a desired inter-layer assortativity, starting from an initial assortativity value and modifying the network through randomly selected vertices.
- The algorithm generates interconnected multiplex networks targeting a specified inter-layer assortativity A⋆.The procedure is presented in the appendix using standard notation.
- It begins with a 2-layer multiplex having initial inter-layer assortativity A0.
- The procedure randomly selects two different vertices, i and j, and considers their layer-specific degrees.The supplied description explicitly introduces the degrees on the first layer for vertex i.