PaperlayerView exact revision on arXiv

Source-linked AI summary

Eigenvector-Based Centrality Measures for Temporal Networks

Dane Taylor, Sean A. Myers, Aaron Clauset, Mason A. Porter, Peter J. Mucha

arXiv:1507.01266v3physics.soc-phcs.SInlin.AOphysics.data-an

TL;DR

Temporal networks require centrality measures that preserve changing edges and their order rather than aggregating layers or analyzing them independently. The paper couples layer-specific centrality matrices into a supra-centrality matrix, then derives node and trajectory measures through marginal, conditional, and perturbative analyses. The framework reveals coupling-dependent localization and temporal change across three empirical networks, while joint centralities can be biased toward middle layers and time-averaged measures depend on limiting choices.

  • Problem

    Existing temporal centrality approaches can lose centrality trajectories through aggregation, ignore temporal ordering through layer isolation, and use application-dependent assumptions whose tradeoffs are not always clear.

  • Method

    The paper couples layer-specific centrality matrices in an NT × NT supra-centrality matrix and derives joint, marginal, conditional, time-averaged, and first-order-mover centralities.

  • Results

    The method identifies coupling-dependent localization and different time scales of centrality change, and is applied to mathematics Ph.D. exchange, Hollywood costarring, and Supreme Court citation networks.

  • Takeaways & Limitations

    Separating inter-layer from intra-layer connections provides a temporal eigenvector-centrality formalism for studying node importance and centrality trajectories across time.

  • Takeaways & Limitations

    Joint centralities have a bias toward middle layers, and time-averaged centralities based on summed joint or conditional values are sensitive to the perturbation parameter.

Abstract

from arXiv · show

Numerous centrality measures have been developed to quantify the importances of nodes in time-independent networks, and many of them can be expressed as the leading eigenvector of some matrix. With the increasing availability of network data that changes in time, it is important to extend such eigenvector-based centrality measures to time-dependent networks. In this paper, we introduce a principled generalization of network centrality measures that is valid for any eigenvector-based centrality. We consider a temporal network with N nodes as a sequence of T layers that describe the network during different time windows, and we couple centrality matrices for the layers into a supra-centrality matrix of size NTxNT whose dominant eigenvector gives the centrality of each node i at each time t. We refer to this eigenvector and its components as a joint centrality, as it reflects the importances of both the node i and the time layer t. We also introduce the concepts of marginal and conditional centralities, which facilitate the study of centrality trajectories over time. We find that the strength of coupling between layers is important for determining multiscale properties of centrality, such as localization phenomena and the time scale of centrality changes. In the strong-coupling regime, we derive expressions for time-averaged centralities, which are given by the zeroth-order terms of a singular perturbation expansion. We also study first-order terms to obtain first-order-mover scores, which concisely describe the magnitude of nodes' centrality changes over time. As examples, we apply our method to three empirical temporal networks: the United States Ph.D. exchange in mathematics, costarring relationships among top-billed actors during the Golden Age of Hollywood, and citations of decisions from the United States Supreme Court.

1. Introduction.

The paper generalizes eigenvector-based centralities to temporal networks by coupling layer-specific centrality matrices. Its joint, marginal, and conditional centralities describe node-layer importance and centrality trajectories, while perturbation expansions yield time-averaged and first-order-mover scores.

  • Approach: The authors couple centrality matrices across temporal layers into an NT × NT supra-centrality matrix.The framework distinguishes inter-layer from intra-layer connections and applies to any eigenvector-based centrality.
  • Centrality Measures: The dominant eigenvector gives joint centrality for each node-layer pair, while marginal and conditional centralities support node, layer, and trajectory analyses.Joint centrality reflects both node and layer importance; conditional centrality evaluates nodes relative to one another at a specified time.
  • Temporal Coupling: ω controls temporal coupling, ranging from decoupled layers as ω → 0+ to dominating coupling as ω → ∞.The coupling strength tunes how much a node’s centrality changes through time.
  • Perturbation Analysis: Zeroth-order perturbation terms produce time-averaged centralities, whereas first-order terms produce first-order-mover scores for centrality changes.Time-averaged centrality ranks nodes with constant centrality across time; first-order-mover scores rank the magnitude of temporal change.
  • Computation: Both time-averaged centralities and first-order-mover scores require solving linear-algebraic problems of size N × N rather than the full NT × NT eigenproblem.The perturbative approach also avoids requiring a particular intra-layer coupling weight ω.
  • Applications: The method is illustrated on doctoral exchange, Hollywood costarring, and Supreme Court citation temporal networks.The introduction identifies these as three empirical examples.

2. Background Information and a Naive Approach.

Temporal centrality must account for changing edges and their order, because aggregation or layer isolation can distort centrality trajectories and rankings. The paper therefore separates inter-layer from intra-layer connections, avoiding failures of naive supra-adjacency eigenvector calculations.

  • Background: Eigenvector-based centralities use dominant eigenvectors of centrality matrices and capture global network structure.Examples include adjacency-, hub-, authority-, and PageRank-based matrices.
  • Background: Temporal networks are commonly represented as sequences of layers, whose rankings may fluctuate when edges appear or disappear over time.Uncoupled layer analyses can produce substantial step-to-step variation due to edge stochasticity.
  • Background: Aggregating layers prevents analysis of centrality trajectories, while analyzing layers independently ignores temporal edge ordering.Temporal ordering and time scale can fundamentally affect dynamics underlying eigenvector-based rankings.
  • Background: Existing temporal centrality generalizations may suit different applications, and their modeling assumptions and tradeoffs are not always clear.The paper frames this as a need for careful comparison of application-dependent generalizations.
  • Naive Generalization: A naive supra-adjacency approach treats inter-layer identity edges like ordinary edges, despite their distinct role in multilayer networks.This can make standard spectral interpretations inappropriate for temporal networks.
  • Naive Generalization: For hub and authority centralities, products such as A A^T and A^T A mix intra-layer and inter-layer effects instead of separating them.Their blocks no longer correspond neatly to a single edge type.
  • Naive Generalization: The naive construction can decouple even- and odd-indexed nodes, producing nonunique dominant eigenvectors, zero entries, oscillations, and numerical instability.These problems become visible for large coupling weights ω.
  • Proposed Formalism: The proposed formalism directly couples layer-specific centrality matrices while treating inter-layer and intra-layer edges as distinct.It is designed to behave appropriately for all ω > 0 without heuristic averaging or layer aggregation.

3. Temporal Coupling of Eigenvector-Based Centralities.

The paper generalizes eigenvector-based centralities to temporal networks by coupling layer-specific centrality matrices and analyzing node-layer centralities. Joint, marginal, and conditional measures expose how centrality depends on nodes, layers, coupling strength, and time.

  • 3.1. Inter-Layer Coupling of Centrality Matrices: A supra-centrality matrix couples the centrality matrices of temporal layers, extending eigenvector-based centrality to ordered multilayer networks.The construction treats inter-layer and intra-layer connections as fundamentally different.
  • 3.1. Inter-Layer Coupling of Centrality Matrices: The coupling parameter controls how strongly each node’s centrality is linked across neighboring time layers, producing a family of temporal centrality measures.The formulation uses ϵ = 1/ω, with ϵ → 0+ corresponding to strong coupling.
  • 3.1. Inter-Layer Coupling of Centrality Matrices: The temporal extension is non-causal because each layer is coupled to neighboring layers both forward and backward in time.The assumed coupling connects layer t to layers t + 1 and t − 1 when present.
  • 3.2. Joint, Marginal and Conditional Centrality for Multilayer Networks: The dominant eigenvector assigns joint centrality to each node-layer pair, while marginal and conditional centralities summarize nodes, layers, and within-layer comparisons.The vector is mapped to an N × T matrix whose entries give node-layer centralities; row and column sums yield marginal node and layer centralities.
  • 3.3. Synthetic Temporal Network Example: For small ϵ, layer 2’ is dominant, whereas for large ϵ, layer 1’ is dominant; centralities can change discontinuously because of eigenvalue crossings.Layer 1’ has the largest isolated centrality-matrix eigenvalue in the example.
  • 3.3. Synthetic Temporal Network Example: At ϵ = 0.5, conditional centrality increases over time for physical node 4 but decreases for physical node 1, matching their reversed degree ordering across the first and third layers.Node 1 has the largest degree at t = 1’ and the smallest at t = 3’, while node 4 shows the opposite pattern.

4. Singular Perturbation in the Strong-Coupling Limit.

In the strong-coupling limit, the supra-centrality problem becomes singular because the uncoupled limit has an N-dimensional dominant eigenspace. Singular perturbation resolves this degeneracy, yielding time-averaged centralities from zeroth-order terms and first-order-mover scores from first-order terms.

  • 4.1. Singularity at Infinite Inter-Layer Coupling.: At ϵ = 0, the supra-centrality matrix becomes reducible and has an N-dimensional dominant eigenspace, whereas ϵ > 0 has a unique dominant eigenvector.The singularity arises because intra-layer connectivity is eliminated at ϵ = 0.
  • 4.1. Singularity at Infinite Inter-Layer Coupling.: The stride permutation exposes the limiting matrix as P(I ⊗ A)P^T, which decouples into N identical eigenvalue problems for the inter-layer coupling matrix.The dominant eigenvalues therefore have multiplicity N, with eigenspaces constructed from the eigenvectors of A.
  • 4.2. Zeroth-Order Expansion and Time-Averaged Centrality.: Zeroth-order terms make each node’s conditional centrality constant across time and identify time-averaged centralities from an N × N eigenvector problem.For chain coupling, the limiting joint centrality has the form α_i sin(πt/(T + 1)), while the conditional node centrality is α_i up to normalization.
  • 4.3. First-Order Expansion and First-Order-Mover Scores.: First-order expansion yields a linear system whose solution captures the dominant centrality-trajectory changes for small ϵ.The resulting first-order term provides a concise representation of temporal variation.
  • 4.3. First-Order Expansion and First-Order-Mover Scores.: First-order-mover scores rank nodes by the magnitudes of their entries in v1, while the corresponding centralities may increase or decrease over time.The direction of change can be examined from the corresponding entries of v(ϵ).

5. Case Studies with Empirical Network Data.

The empirical case studies apply temporal eigenvector centralities to university, actor, and Supreme Court citation networks, revealing how rankings and trajectories depend on time and inter-layer coupling.

  • 5.1. Doctoral Degree Exchange in the Mathematics Genealogy Project: Time-averaged authority centralities identify MIT, UC Berkeley, Stanford, and Princeton as the four most central mathematics universities.These rankings are based on the dominant eigenvector of the time-averaged authority matrix.
  • 5.1.1. MGP: Centrality in the Strong-Coupling Regime.: Strong linear correlation links university first-order-mover and time-averaged rankings, but Georgia Tech and CUNY have unusually high mover ranks relative to their average ranks.Georgia Tech’s mathematics department shifted from primarily teaching-oriented to more research-oriented in the late 1970s.
  • 5.1.1. MGP: Centrality in the Strong-Coupling Regime.: At ϵ = 10^-4, Georgia Tech and CUNY show drastic temporal changes in conditional authority centrality, whereas the other highly ranked universities remain relatively constant.The comparison includes the four universities with the highest time-averaged centralities and the two universities with high first-order-mover scores.
  • 5.1.2. MGP: Some Properties of Authority Centrality.: Increasing ϵ produces more volatile trajectories: neighboring-layer centralities become dissimilar for Georgia Tech when ϵ ≥ 10^-1, while small ϵ preserves slow variation.The authors focus on the strong-coupling regime because they judge highly volatile rankings at large ϵ to be an inappropriate description of department prestige.
  • 5.1.2. MGP: Some Properties of Authority Centrality.: For large ϵ, joint centrality localizes near t = 1982 because that layer’s centrality matrix has the largest spectral radius.In the decoupled limit, Perron–Frobenius theory describes concentration onto the dominant layer.
  • 5.2. Top Billing in the Golden Age of Hollywood (GAH).: In the Hollywood network, the ten actors with the highest time-averaged centralities also have the highest first-order-mover scores, while Clark Gable and Groucho Marx have nearly equal leading average centralities.Clark Gable’s αi is 0.3683 and Groucho Marx’s is 0.3627, compared with 0.2844 for Harpo Marx.

6. Conclusions.

The paper generalizes eigenvector-based centralities to temporal networks through joint, marginal, and conditional centralities, while deriving strong-coupling approximations for time-averaged centralities and first-order-mover scores. Higher-order expansions are developed and validated empirically, but causal inter-layer coupling remains an important direction for future work.

  • Joint centralities rank node-layer pairs, while marginal and conditional centralities summarize node or layer importances and centrality trajectories over time.
  • Strong-coupling perturbation expansions yield time-averaged centralities and first-order-mover scores, identifying central entities and those whose centrality changes most.
  • The methodology applies to any eigenvector-based centrality, including PageRank, hub and authority centralities, and eigenvector centrality, with supporting Matlab software.
  • Directed inter-layer edges could represent causal scenarios, but may produce non-irreducible supra-centrality matrices requiring strong connectivity mechanisms such as teleportation.
  • Higher-order terms extend the perturbation expansion for approximating the dominant eigenvector at fixed ϵ > 0, and Fig. 6.1 validates these approximations on the MGP and GAH networks.
  • For sufficiently small ϵ, increasing approximation order reduces error, with linear, quadratic, and successive decay rates for zeroth-, first-, and higher-order approximations.The small-coupling thresholds are ϵ ⪅3 × 10^-4 for MGP and ϵ ⪅10^-3 for GAH.
Loading 1507.01266v3…