Source-linked AI summary
Centrality Measures in Temporal Networks: A Critical and Comparative Survey
Aksa Urooj, Iqra Altaf Gillani
TL;DR
Temporal centrality research lacks consolidated evidence for comparing measures and selecting them across dynamic network settings. This survey builds a functional taxonomy, reviews classical adaptations and specialized metrics, and evaluates them through diffusion, ranking, and runtime analyses; it concludes that method choice depends on application, network characteristics, and computational constraints.
Problem
Temporal centrality research is fragmented, with limited consolidated understanding of measures’ comparative performance, strengths, weaknesses, and application suitability.
Method
The survey organizes temporal centrality measures by influence mechanism, reviews classical adaptations and specialized metrics, and evaluates them on real-world temporal networks.
Results
TWC and TSDC consistently achieve the highest diffusion performance under both SI and SIS models, while Supracentrality, Incremental PageRank, and CENDY perform comparatively weaker.
Takeaways & Limitations
Temporal centrality measures should be selected according to the application domain, network characteristics, and computational constraints because no category is universally superior.
Takeaways & Limitations
Coreness Centrality often assigns the same core number to many nodes, limiting granularity and distinguishing power within temporal networks.
Abstract
from arXiv · showhide
Temporal networks offer a suitable representation for complex systems in which interactions vary over time, such as communication, transportation, and social networks. Identifying influential nodes in such networks is more challenging than in static graphs because node importance depends not only on network structure but also on the timing and ordering of interactions. Although many temporal centrality measures have been proposed, the literature remains fragmented, with limited consensus on their comparative performance and applicability. This paper presents a critical and comparative survey of centrality measures in temporal networks. We review both temporal extensions of classical centrality metrics and measures specifically designed for temporal graphs, and propose a functional taxonomy that categorizes existing approaches according to the primary mechanism through which influence is quantified in temporal networks. The proposed taxonomy organizes temporal centrality measures into interaction-based, path-based, walk-based, spectral-based and robustness-based categories, providing a unified perspective on their underlying principles. In addition, we provide comparative insights to help select appropriate temporal centrality measures under different network characteristics and application settings. To complement the survey, we conduct experiments on multiple real-world temporal network datasets. The measures are evaluated through influence spreading experiments using epidemic diffusion models, ranking consistency analysis based on Kendall's rank correlation, and runtime complexity analysis to assess computational efficiency and scalability. Finally, we highlight key open challenges and future research directions, including scalability for million-sized networks and the need for standardized evaluation frameworks.
1. Introduction
Temporal networks model interactions that evolve over time, making node importance dependent on temporal dynamics rather than static structure alone. This survey addresses fragmented understanding by organizing and comparing temporal centrality measures across applications and evaluation dimensions.
- Temporal networks: Temporal networks represent interactions as time-varying relationships, capturing changes in both graph structure and node interactions.An interaction is represented by its endpoints, occurrence time, and duration.
- Motivation: Static centrality measures identify influential or structurally critical nodes, but temporal graphs require specialized approaches balancing temporal accuracy and computational feasibility.Applications include viral marketing, traffic bottleneck detection, infrastructure robustness, and communication systems.
- Research gap: Existing research remains fragmented, limiting consolidated understanding of comparative performance, strengths, weaknesses, and application suitability.Prior surveys provide only partial coverage of node centrality measures in temporal networks.
- Contributions: The survey proposes a functional taxonomy and reviews both temporal adaptations of classical metrics and measures designed specifically for evolving or streaming networks.The taxonomy is organized by the primary mechanism through which influence is quantified.
- Evaluation and outlook: The study combines application analysis, real-world experimental comparison, influence spreading, ranking correlation, runtime assessment, and identification of open challenges.Future directions include scalability in streaming settings and integration of higher-order and multilayer temporal structures.
2. Preliminaries
The preliminaries define temporal graphs, structural graph concepts, and network efficiency before introducing SI and SIS diffusion models for evaluating temporal influence. These foundations describe how interactions evolve and how spreading is modeled over time.
- Temporal graph foundations: A temporal graph is a chronological sequence of graphs whose fixed vertex set is connected by edges that evolve over time.Temporal edges may connect vertices during specified intervals within a time horizon.
- Graph definitions: A cycle basis generates all graph cycles through linear combinations, while a minimum cycle basis minimizes the total weight of its constituent cycles.The minimum union cycle instead includes every edge in one minimum-weight cycle, with each vertex assigned to one such cycle.
- Stability concepts: An unstable vertex pair is one whose shortest-path distance changes after an edge is added or removed.The r-unstable vertex set contains vertices whose levels change in the modified BFS+ graph; an empty set indicates stability.
- Network efficiency: Network efficiency is defined as the average inverse shortest-path distance between node pairs.This definition provides a communication-efficiency quantity for graph analysis.
- Diffusion models: The SI and SIS models evaluate spreading capability using infection probability β, with SIS additionally allowing recovery probability γ and reinfection.SI keeps infected nodes infected permanently, whereas SIS returns recovered nodes to the susceptible state.
3. Taxonomy of Temporal Centrality Measures
The taxonomy classifies temporal centralities by how they quantify influence, distinguishing local interactions, temporal paths, diffusion walks, spectral propagation, and structural robustness. These categories expose trade-offs among temporal awareness, structural information, computational efficiency, and application fit.
- The functional taxonomy groups temporal centralities into local interaction-based, path-based, walk-based diffusion, spectral, and structural robustness categories.It classifies measures by their primary source of influence rather than solely by mathematical formulation.
- Local Interaction-Based Centralities: Local interaction-based measures use immediate temporal neighborhoods, offering simplicity and scalability but often missing broader structural position.They are suitable for large-scale and streaming networks because they avoid expensive global computations.
- Path-Based Centralities: Path-based measures quantify influence through chronologically valid temporal paths that capture reachability and communication efficiency.Their principal limitation is computational complexity from repeated traversals across time layers.
- Walk-Based Diffusion Centralities: Walk-based diffusion measures consider multiple temporally valid walks, often modeling spreading more realistically than shortest-path approaches at higher computational cost.They are used in influence maximization, information dissemination, and epidemic spreading studies.
- Spectral Centralities: Spectral measures derive global influence from recursive propagation through time-dependent adjacency structures and dominant eigenvectors, requiring substantial matrix computation.Temporal implementations may use coupled layers or large supra-adjacency structures.
- Structural Robustness Centralities: Structural robustness measures rank nodes by their contribution to cohesion, connectivity, or efficiency, supporting resilience analysis but potentially missing temporal spreading dynamics.They assess how node removal degrades evolving network functionality.
4. Classical Centrality Measures
Classical centrality measures quantify node importance using structural properties, but temporal adaptations incorporate evolving connections, durations, and network changes. Degree and coreness measures remain computationally useful while exhibiting important limitations in capturing influence and temporal detail.
- Classical measures identify important nodes using structural properties and support applications including service placement, product promotion, ecological protection, and cortical-network analysis.
- Degree Centrality: Degree centrality counts a node’s connections, making it simple and cost-effective but insensitive to connection duration and neighbor influence.A patient connected to five doctors illustrates how degree alone can miss relationship duration.
- Degree Centrality: Temporal degree variants incorporate connection duration, temporal ordering, neighbor activity, or hybrid degree-like information.Examples include Time Scale Degree Centrality, time-ordered graph extensions, and temporal degree-degree.
- Coreness Centrality: Coreness centrality assigns nodes to densely connected k-core layers, reflecting network position rather than degree alone.A node belongs to a k-core when it has at least k neighbors within the induced subgraph.
- Coreness Centrality: Incremental and temporal core methods update affected nodes or characterize cores by coreness and temporal span as networks evolve.Incremental k-core decomposition achieved up to a million-fold speed-up over the traditional k-shell method on a 16-million-node network.
- Coreness Centrality: Coreness centrality has complexity O(T(n + m)) per snapshot sequence but often assigns identical core numbers to many nodes, limiting granularity.Nodes in the same k-shell may receive similar spreading-capability assessments.
4.3. Closeness centrality
Closeness centrality measures global accessibility through shortest-path distances, while temporal variants account for time-respecting paths and dynamic changes. These methods improve temporal realism but can be computationally expensive and problematic for disconnected networks.
- Closeness centrality evaluates node importance through average shortest-path distance to all other nodes, capturing global accessibility.
- Static aggregation can overestimate paths and underestimate geodesic distances because it ignores continuously changing connections and interaction timing.
- Dynamic closeness methods update centrality after edge changes by recomputing distances for unstable or affected vertices.CENDY detects vertices whose distances changed after insertion, while other methods reuse breadth-first-search level differences.
- Temporal closeness requires time-respecting shortest paths from each node to all others, with complexity O(Tnm).
- Closeness becomes undefined across disconnected components and is therefore inefficient for large-scale networks.
4.4. Betweenness Centrality
Betweenness centrality emphasizes intermediary nodes on shortest routes, but temporal computation is costly and shortest-path assumptions can produce sparse or unrealistic influence rankings. Dynamic updates and random-walk formulations address parts of these limitations.
- Betweenness centrality highlights nodes that mediate communication between different network regions by counting shortest routes through them.
- Temporal betweenness has complexity O(Tn3) because it counts shortest paths through every node for every node pair.Traditional formulations also omit the time a node stores a message before forwarding it.
- Dynamic betweenness algorithms reduce recomputation by reusing prior shortest-path results, restricting updates to affected structures, or pruning incremental updates.The QUBE framework limits updates to Minimum Union Cycles, while stream-based methods maintain approximate scores for insertions and deletions.
- Shortest-path betweenness can assign zero scores to many nodes and assumes information or infections consistently follow shortest routes.Newman’s alternative considers all random walks, allowing diffusion over longer paths with some probability.
4.5. Eigenvector Centrality
Eigenvector centrality extends degree by weighting connections to influential neighbors, while temporal formulations model evolving networks across interconnected layers. Its iterative computation and structural assumptions limit applicability in several network settings.
- Eigenvector centrality weights a node by the eigenvector values of its adjacent neighbors, addressing degree centrality’s equal-neighbor assumption.
- Temporal eigenvector frameworks represent dynamic networks as interconnected layers and use a supracentrality matrix’s dominant eigenvector to score nodes at each time layer.The matrix combines within-layer connections with between-layer links.
- Eigenvector centrality is computed iteratively for each snapshot with per-snapshot complexity O(k(n+m)).Here, k is the number of iterations.
- Eigenvector centrality may assign zero scores outside the main strongly connected component and underestimate nodes influential only within smaller clusters.Power iteration may also converge slowly or fail in some bipartite graphs.
- The iterative algorithm can create substantial computational overhead in large-scale networks.
4.6. PageRank Centrality
PageRank has been adapted to temporal networks to account for evolving links, time-stamped interactions, and changing personalization. These approaches improve temporal responsiveness but face computational and recency-related limitations.
- Incremental and temporal extensions: Incremental PageRank updates only changed or affected graph regions instead of recomputing the full ranking after every change.The updated graph is partitioned into unchanged nodes P and changed or affected nodes Q.
- Incremental and temporal extensions: Temporal PageRank ranks nodes using time-stamped edges, capturing evolving influence that static PageRank ignores.The method extends classic PageRank to temporal networks by incorporating the timing of interactions.
- Temporal extensions: f-PageRank jointly ranks nodes and time layers, while time-dependent personalized PageRank adapts its personalization vector across time.f-PageRank is computationally intensive for large networks, and time-dependent personalization may face scalability issues with many time layers.
- Complexity and limitations: O(Tk(n+ m)) complexity characterizes temporal PageRank across T snapshots and k iterations.The method propagates iteratively across time-ordered graphs, requiring computation over temporal snapshots and iterations.
- Complexity and limitations: Temporal PageRank tends to favor older pages because newer pages have had less time to accumulate links.Several approaches address this recency bias, while certain links may also carry different levels of significance.
5. Centrality Measures in Temporal Networks
Temporal centrality measures address the sequencing, causality, and timing that static or independently analyzed snapshots often miss. The section covers efficiency, temporal walks and paths, epidemic influence, coverage, and temporal random-walk approaches.
- Motivation: Static centrality and snapshot-based extensions can miss causality, sequencing, and timing in influence propagation.These limitations motivate centrality measures designed specifically for temporal networks.
- Robustness-based measures: Efficiency centrality evaluates a node by removing it and measuring the resulting decrease in overall network efficiency.Unlike closeness centrality, it can be applied to directed networks.
- Walk-based measures: Temporal Walk Centrality measures a node’s ability to receive and transmit information while incorporating interaction duration and sequence.Its weights can depend on walk length and waiting time, with longer paths or delays receiving lower weights.
- Path-based measures: Dynamic centrality extends α-centrality to time-respecting paths through memoryless and memory-based models.The memoryless model propagates only to the next time step, whereas the memory-based model uses exponentially decaying historical interactions.
- Diffusion-based measures: Dynamic-Sensitive Centrality uses an SIR-derived discrete-time Markov chain and multilayer adjacency matrices to quantify cumulative spreading influence.The formulation combines nodal temporal dynamics with network topology across time layers.
- Coverage-based measures: Temporal Coverage Centrality counts the proportion of vertex pairs whose fastest temporal path includes a temporal vertex.Coverage requires matching earliest arrival and latest departure conditions; high values indicate redundancy in information flow.
- Coverage-based measures: Temporal Boundary Coverage Centrality adds a boundary condition to TCC to highlight temporal vertices essential to fastest temporal paths.The stricter criterion filters out non-essential intermediate vertices.
- Spectral and walk-based measures: TempoRank combines temporal ordering and connectivity by multiplying snapshot transition matrices and extracting the leading eigenvector of the resulting matrix.An approximate solution can aggregate temporal pathways across snapshots for computational efficiency.
6. Real-World Applications and Use-Cases of Temporal Centrality Measures
Temporal centrality is applied across healthcare, communication, financial, and online settings where interactions evolve over time. Measure selection depends on dataset properties, temporal resolution, application goals, and computational constraints.
- Measure selection: Meaningful measure selection depends on dataset characteristics, temporal resolution, application goals, and computational constraints.Different temporal centralities capture different aspects of influence, flow, and persistence.
- Application overview: The survey summarizes major application domains together with temporal centrality measures considered suitable for each setting.The application overview spans communicators, healthcare super-spreaders, and financial trust hubs.
- Healthcare: Healthcare contact networks use temporal centrality to identify potential super-spreaders among patients and healthcare workers.These results can support targeted interventions such as vaccination prioritization and contact isolation.
- Communication: Communication networks use temporal centrality to identify influential users who disseminate information or facilitate communication.TWC, TSDC, and eigenvector-based centrality are described as effective for capturing dynamic information flow.
- Finance and economics: Financial and economic transaction networks use temporal analysis to identify participants influencing transaction flows and trust propagation.TWC, TSDC, and betweenness are suited to sustained influence and temporal paths.
7. Experimental Evaluation
The survey evaluates representative temporal centrality measures on three real-world temporal networks using diffusion effectiveness, ranking consistency, and runtime analyses. Results show that temporal walk- and time-aware measures often identify influential nodes effectively, while computational costs vary substantially across methods and datasets.
- Experimental Setup: Experiments compare representative temporal centrality measures on three real-world temporal network datasets using diffusion, ranking, and runtime evaluations.The datasets and evaluation setup are introduced as a systematic comparison framework.
- Experimental Setup: Top 5% ranked nodes seed SI and SIS simulations with β = 0.01, γ = 0.02, and 1000 Monte Carlo repetitions.Mean Fraction of Infected is reported over time for each centrality method.
- Influence Spreading Results: TWC and TSDC consistently achieve the highest diffusion performance under both SI and SIS models across the evaluated temporal datasets.Their performance is attributed to capturing temporal reachability and dynamic interaction patterns.
- Ranking Correlation Analysis: TSDC and TWC show consistently strong ranking correlation in dense networks, whereas CENDY often has weak or negative correlations with other measures.Temporal Coreness and QUBE also frequently exhibit moderate to strong correlations.
- Runtime Analysis Results: TSDC has the lowest execution time, while Efficiency Centrality and Supracentrality are among the most computationally demanding methods.Runtime generally increases with network size and temporal complexity, and the relative ordering remains largely consistent across datasets.
- Overall Findings: The results indicate a trade-off between computational efficiency and methodological complexity when selecting temporal centrality measures.Local interaction-based methods such as TSDC are suited to large-scale settings, whereas spectral and global-path-based methods require more computational resources.
8. Open Challenges and Future Directions
The survey identifies scalability, streaming applicability, and contextual modeling as major unresolved challenges for temporal centrality research. Future work should address large and continuously evolving networks while incorporating richer semantic and heterogeneous information.
- Scalability: Scalability remains a major challenge because several temporal centrality methods repeatedly process time layers or large supra-adjacency matrices.The resulting memory and time complexity can grow exponentially, motivating scalable approximation and incremental updates.
- Streaming Analysis: Most existing temporal centrality measures support retrospective analysis rather than real-time updates in streaming environments.Adaptive algorithms are needed for networks whose edges arrive continuously.
- Context-Aware Modeling: Many measures rely only on topological and temporal features, omitting node attributes, interaction semantics, and external influences.The survey points toward semantic embeddings and heterogeneous attributes for context-aware temporal centrality.
9. Conclusion
The survey organizes temporal centrality measures by their primary source of influence and compares classical adaptations with specialized temporal metrics. It concludes that temporal order, interaction duration, and causality matter for node importance, while scalability and real-time applicability remain unresolved.
- Conclusion: The functional taxonomy groups temporal centrality measures by their primary source of influence, providing a unified framework for comparing diverse approaches.The survey covers temporal adaptations of classical measures and specialized temporal metrics.
- Conclusion: Temporal order, interaction duration, and causality are critical for assessing node importance in time-evolving networks.Temporal extensions also face computational complexity, temporal-granularity sensitivity, and limited scalability.
- Future Directions: Future directions include scalable real-time maintenance, machine-learning and temporal-embedding approaches, and context-aware hybrid centrality measures.These directions combine structural, temporal, and functional perspectives on evolving influence.