PaperlayerView exact revision on arXiv

Source-linked AI summary

Vital nodes identification in complex networks

Linyuan Lü, Duanbing Chen, Xiao-Long Ren, Qian-Ming Zhang, Yi-Cheng Zhang, Tao Zhou

arXiv:1607.01134v1physics.soc-phcs.SI

TL;DR

Vital-node identification is important in heterogeneous networks but lacks a universally reliable index because objectives, network structures, and process parameters differ. This review clarifies concepts, classifies methods, and compares established approaches empirically across real networks, concluding that systematic benchmarking and interdisciplinary perspectives remain important.

  • Problem

    Different structural and functional objectives require different vital-node rankings, while method performance varies with network structure and process parameters.

  • Method

    The review synthesizes concepts, metrics, problems, methods, and progress, then empirically compares well-known approaches across disparate real networks and objective functions.

  • Results

    The review reports extensive empirical comparisons of well-known vital-node methods on disparate real networks under different objective functions.

  • Takeaways & Limitations

    A comprehensive understanding of method applicability requires comparisons across objectives, dynamical-process parameters, and network structures.

  • Takeaways & Limitations

    Method performance depends on objective functions, dynamical-process parameters, and network structures, so benchmark conclusions are context-dependent.

Abstract

from arXiv · show

Real networks exhibit heterogeneous nature with nodes playing far different roles in structure and function. To identify vital nodes is thus very significant, allowing us to control the outbreak of epidemics, to conduct advertisements for e-commercial products, to predict popular scientific publications, and so on. The vital nodes identification attracts increasing attentions from both computer science and physical societies, with algorithms ranging from simply counting the immediate neighbors to complicated machine learning and message passing approaches. In this review, we clarify the concepts and metrics, classify the problems and methods, as well as review the important progresses and describe the state of the art. Furthermore, we provide extensive empirical analyses to compare well-known methods on disparate real networks, and highlight the future directions. In despite of the emphasis on physics-rooted approaches, the unification of the language and comparison with cross-domain methods would trigger interdisciplinary solutions in the near future.

1. Introduction

Vital-node identification matters because heterogeneous networks assign nodes different structural and functional roles, but the task has diverse objectives and difficult trade-offs. This review organizes the field, compares methods across real networks, and identifies open challenges.

  • Heterogeneous node roles make vital-node identification relevant to epidemic control, advertising, outage prevention, resource allocation, and network connectivity.
  • No universal importance index can optimize every objective, and method performance varies across networks and objective-function parameters.
  • Local, parameter-free indices are simpler and cheaper, but often less accurate than methods using global information or multiple parameters.
  • Identifying vital node sets is difficult because heuristics designed for individual nodes often perform poorly when selecting groups.
  • The review clarifies concepts, metrics, problems, and methods; compares established approaches on disparate real networks; and highlights future challenges.
  • The review is organized around individual-node methods, including structural centralities, iterative refinement, and removal-based influence analyses.

2. Structural centralities

Structural centralities assign numerical scores from network structure to rank node importance. The review distinguishes neighborhood-based measures from path-based measures and discusses alternatives that account for longer paths.

  • A centrality measure assigns each node a real value intended to rank its structural importance.
  • Structural centralities use network topology without directly depending on the specific dynamical process under study.
  • Neighborhood-based centralities: Degree centrality estimates influence by counting immediate neighbors, providing a straightforward and efficient local algorithm.
  • Path-based centralities: Closeness and betweenness centralities use shortest-path structure to characterize dissemination speed and control over information flow.
  • Path-based centralities: Katz, subgraph, and information indices include longer paths while assigning them reduced weight to model non-shortest-path propagation.
  • The chapter broadly classifies structural centralities as neighborhood-based or path-based and introduces representative measures.

2.1. Neighborhood-based centralities

Neighborhood-based centralities infer node influence from local connections, neighbors’ properties, clustering, or network-core location. They favor computational simplicity but can lose accuracy or require structural information beyond strictly local neighborhoods.

  • Degree centrality: Degree centrality defines a node’s score as its number of directly connected neighbors, with greater degree interpreted as greater influence.
  • Degree centrality: Normalized degree centrality facilitates within-formula comparison, but nodes in different networks remain generally incomparable because network organization, function, and density differ.
  • Degree centrality: Degree centrality has low computational complexity and can outperform more complicated centralities in degree-targeted attacks on scale-free and exponential networks.
  • LocalRank: LocalRank extends degree centrality by incorporating fourth-order-neighbor information while retaining lower complexity than typical path-based centralities.
  • ClusterRank: ClusterRank combines neighborhood size with interactions among nearest neighbors, using a decreasing function of local clustering because clustering can hinder spreading.
  • Community-aware indices: Community- and structural-hole-based indices rank nodes partly by their connections across groups, which may accelerate global information spreading.
  • Coreness: Coreness uses iterative k-core decomposition to rank nodes by network-core location, but it is coarse-grained and unsuitable for some BA and tree-like networks.
  • Coreness extensions: Mixed-degree and related extensions distinguish nodes using residual links, exhausted links, distances to the core, community properties, or tie strength.

2.2. Path-based centralities

Path-based centralities rank nodes using distances, paths, or information transmission across the network. Their assumptions differ: some emphasize shortest paths, while others include all paths or account for flow alternatives.

  • Eccentricity: Eccentricity ranks a node by its maximum shortest-path distance to all other nodes, with smaller eccentricity indicating greater influence.Normalized eccentricity compares values using the network's largest and smallest eccentricities.
  • Eccentricity: Eccentricity can misidentify influential nodes because a few unusually long paths determine its maximum-distance criterion.In the example network, v7 is ranked ahead of v6 despite v6 being the intended most influential node.
  • Closeness and information-based measures: Closeness centrality uses the inverse of mean geodesic distance, representing how efficiently a node exchanges information with others.Its original definition requires connected networks because disconnected node pairs have infinite distance.
  • All-path centralities: Katz centrality weights all paths by length, assigning shorter paths greater contributions through a tunable parameter s.The parameter must be below the reciprocal of the adjacency matrix's largest eigenvalue, and high computational complexity limits large-scale use.
  • Closeness and information-based measures: Information centrality measures transmission through all possible paths, with longer paths losing more information, and can extend to weighted networks.It differs from closeness centrality in how each path contributes to the aggregate measure.
  • Betweenness centrality: Betweenness centrality measures shortest-path control, ranging from zero for star-network leaves to the maximum for the central node.In scale-free networks, betweenness equals shortest-path packet load under the stated routing assumptions and follows a power-law distribution.
  • Group and related centralities: Group betweenness extends shortest-path centrality from individual nodes to groups, while co-betweenness counts paths passing through every group member.Subgraph centrality is also reported as useful for identifying important nodes and detecting network motifs.
  • Betweenness centrality: Shortest-path betweenness may mismatch real transport because load balancing and fault tolerance can route packets along non-shortest paths, motivating flow betweenness.Selecting shortest paths between all node pairs can also produce traffic congestion.

3. Iterative refinement centralities

Iterative refinement centralities rank nodes by repeatedly updating scores from neighboring nodes or network dynamics. The section covers eigenvector-based methods, PageRank and LeaderRank, HITS, SALSA, and cumulative nomination.

  • Eigenvector centrality: Eigenvector centrality assigns importance according to the summed centralities of a node’s neighbors and can be computed by power iteration.Scores are repeatedly shared with connected neighbors until reaching a steady state.
  • Eigenvector centrality: Eigenvector centrality can concentrate scores in a few nodes, making distinctions among nodes difficult; nonbacktracking centrality modifies neighbor contributions to address this issue.In directed networks, alpha centrality introduces exogenous sources of status.
  • PageRank: PageRank ranks nodes through random walks, but dangling nodes can prevent convergence, motivating a random-jumping factor.The jumping probability s is commonly set around 0.85 but should be tested for different scenarios.
  • LeaderRank: LeaderRank adds a ground node connected bidirectionally to all other nodes, producing a strongly connected network without PageRank’s random-jumping parameter.After convergence, the ground node’s value is evenly distributed among the other nodes.
  • LeaderRank: LeaderRank converges faster and outperforms PageRank in ranking effectiveness, robustness against manipulations, and robustness against noisy data.The review attributes faster convergence to a strongly connected network with diameter 2.
  • HITS and SALSA: HITS distinguishes authority and hub roles through mutually reinforcing scores, while SALSA maps directed links onto a bipartite undirected network for stochastic random walks.SALSA separates nodes with non-zero out-degree as hubs and nodes with non-zero in-degree as authorities.

4. Node operation

Node-operation methods identify vital nodes by examining how removal or contraction changes connectivity, vulnerability, stability, dynamical impact, or network agglomeration. Their usefulness depends on the objective and network fragility.

  • Node removal: Node-removal methods define importance through damage to giant-component size, connectedness, shortest paths, stability, robustness, or vulnerability.Scale-free networks are stable against random failures but vulnerable to intentional attacks.
  • Node contraction: Node contraction merges a node and its neighbors, treating nodes that make the network more agglomerate after contraction as more important.Agglomeration depends on both node count and average shortest distance.
  • Connectivity-based measures: Connectivity damage can be measured using giant-component size, connected-component count, shortest-distance changes, or reciprocal-distance losses.The DSP measure separates direct losses involving the removed node from indirect losses among other nodes.
  • Vulnerability-based measures: Vulnerability-based methods treat a node as important when its removal makes the remaining network more vulnerable, including through residual closeness or path diversity.Disjoint-path methods emphasize the diversity of passageways between node pairs.
  • Stability-based measures: Spanning-tree methods link network stability to the number of spanning trees, but fail when node removal creates disconnected components.Stability-sensitive methods are less advantageous when the network is already fragile and one random removal can fragment it.
  • Dynamical impact: Dynamical importance can be estimated from the relative change in the adjacency matrix’s largest eigenvalue after removing a node or node set.A larger eigenvalue change indicates greater impact under this measure.

5. Dynamics-sensitive methods

Dynamics-sensitive methods identify vital nodes by incorporating the features and parameters of a target dynamical process rather than relying only on structural centrality. The review covers path counting, dynamical influence, time-aware centralities, routing-based methods, and game centrality, while noting important assumptions and computational limits.

  • Motivation: Structural centralities can rank nodes differently across dynamical parameters, so no single structural index is universally optimal.In SIR, degree centrality performs better at small spreading rates, whereas eigenvector centrality performs better near the epidemic threshold.
  • Core concept: Dynamics-sensitive methods use estimated target-dynamics features and parameters to improve vital-node identification beyond structural centralities.Random-walk ranking methods are excluded when the random walk is not the target dynamics itself.
  • Path counting methods: Path-counting methods estimate influence by weighting paths according to length and the target dynamics, but self-avoiding-path assumptions can be too strong and computational costs high.The approach counts pathways through which influence reaches other nodes, with decay depending on path length and dynamics.
  • Dynamical influence: Dynamical influence quantifies how an initial condition at a node affects the final state through the left eigenvector associated with the largest eigenvalue of a dynamics matrix.When the matrix is the adjacency matrix, the calculation counts walks of length l and exposes the path-counting basis of dynamical influence.
  • Dynamical influence: At the SIR epidemic threshold, dynamical influence equals eigenvector centrality, while related analyses warn that a spectral gap may be necessary and some networks invalidate the method.The threshold is β = 1/αmax, where αmax is the largest eigenvalue of the adjacency matrix.
  • Traffic dynamics: Routing betweenness identifies vital traffic nodes from a specified routing table by counting paths passing through each target node.The routing table supplies forwarding probabilities and immediate predecessors for source-target traffic.
  • Time-aware methods: Time-aware DS centrality outperforms methods without a temporal factor at a given time step, while dynamics-sensitive simulations also support temporal dependence in node importance.The review relates DS centrality to a temporal cutoff of alpha centrality and reports that eigenvector centrality can outperform degree centrality at very large times.
  • Other dynamics: Game centrality measures how an initially defecting node converts other nodes to its strategy, but requires simulating the evolutionary-game dynamics and is ad hoc.It averages the proportion of defectors over the last 50 simulation steps.

6. Identifying a set of vital nodes

Identifying a set of vital nodes extends individual-node ranking to applications requiring a small group that propagates information or maintains connectivity. Directly selecting the top-k nodes by centrality is a common benchmark but may be inefficient when high-centrality nodes are clustered.

  • Motivation: Real-world applications often require a small set of vital nodes for information propagation, network connectivity, or marketing under limited budgets.Marketing seeks customers likely to buy and able to trigger purchases by others.
  • Baseline and limitation: Ranking all nodes by centrality and choosing the top-k is a common benchmark, but clustered high-centrality nodes can make this strategy inefficient.The limitation applies to degree and other centrality-based selections.
  • Problem framing: Influence maximization selects a target set rather than a single vital node to satisfy a specified structural or functional objective.The review introduces problem descriptions, pioneering works, state-of-the-art progress, and approaches from computer science and statistical physics.

6.1. Influence maximization problem (IMP)

Influence maximization asks for a size-k node subset that maximizes an influence function, whose meaning depends on the structural or dynamical objective. The review connects this framework to flow reduction, percolation, feedback vertex sets, viral marketing, and operational spreading models.

  • General formulation: Influence maximization finds a subset S of fixed size k that maximizes an influence function f(S) over a network.The function may depend only on topology or incorporate more complicated mechanisms.
  • Structural IMP: Structural influence maximization can seek nodes whose removal produces the greatest decrease in maximum flow between a specified node pair.This formulation defines vital nodes through network structure and directed-link removal.
  • Structural IMP: Optimal percolation maps superspreader identification and epidemic immunization to removing a minimal node set that fragments the network.The influence of a removed set is measured by the size of the largest remaining connected component.
  • Structural IMP: A feedback vertex set contains at least one vertex from every cycle, so its removal leaves an undirected network composed of one or more trees.The minimum size of such sets is called the decycling number.
  • Functional IMP: Viral-market influence maximization selects customers for discounts or advertisements to maximize direct and word-of-mouth sales under a limited budget.Purchase probability combines product desirability, marketing action, and influence from neighboring customers.
  • Functional IMP: The general viral-market optimization problem is NP-hard, whereas a simple linear model can be solved using a system of linear equations.The linear model assigns nonnegative neighbor-influence weights that sum to one.
  • Functional IMP: Kempe, Kleinberg, and Tardos define influence as the expected number of active nodes at process termination and seek the k-node seed set maximizing it.Their framework uses monotone activation processes and estimates influence through simulations.
  • Functional IMP: Their framework studies linear-threshold and independent-cascade models, with activation governed respectively by weighted thresholds or one-chance probabilistic transmissions.The SIR model becomes equivalent to independent cascade when δ = 1 and pij = β.

6.2. Heuristic and greedy algorithms

Heuristic and greedy methods approximate vital-node selection through centrality updates, graph partitioning, local search, or incremental influence maximization. Their guarantees and performance depend on the objective and network structure.

  • Heuristic algorithms: Approximate methods are common because typical information maximization problems are NP-hard.
  • Heuristic algorithms: Adaptive recalculation updates centralities after each removal, while degree discount adjusts degree using already shared neighbors and infection probability.The degree-discount approximation is especially effective when p ≪1.
  • Heuristic algorithms: VoteRank repeatedly selects the node with the largest voting score, then sets its voting ability to zero and decreases neighboring abilities.The process runs for k steps; simulations in the SIR model found it outperformed ClusterRank and coreness.
  • Heuristic algorithms: Equal graph partitioning fragments networks more effectively than simply selecting highest-degree or highest-betweenness nodes.
  • Greedy algorithms: Greedy influence maximization adds the node with the largest incremental influence and provides a (1 −1/e)-approximation for submodular objectives.For independent-cascade and linear-threshold models, greedy hill-climbing performs much better than selecting nodes by degree or closeness.
  • Greedy algorithms: The decreasing cascade model extends independent cascade by making activation probabilities depend on activation history while retaining order-independent and decreasing constraints.

6.3. Message passing theory

Message-passing methods encode network problems as local constraints and solve self-consistent probability equations. They can address objectives lacking submodularity, potentially extending beyond greedy algorithms.

  • Message-passing formulation: Message-passing theory converts global cycle constraints into local constraints using discrete state variables assigned to network vertices.Occupied components are trees or single-cycle graphs, linking solutions with feedback vertex sets.
  • Belief propagation: The Bethe-Peierls approximation neglects correlations among neighboring vertices in a cavity network, except where the network is locally tree-like.
  • Belief propagation: The resulting self-consistent equations are belief-propagation equations that can be solved iteratively.For the feedback vertex set problem, suitable large-x limits can yield solutions corresponding to minimal total weight.
  • Influence maximization: For linear-threshold influence maximization, message passing represents the dynamics through activation times, local constraints, and an energy function combining seed costs with activation revenues.
  • Scope: Unlike greedy algorithms, message-passing theory does not require objective functions to be submodular.This may broaden its application to dynamical processes with phase transitions, where adding one node can sharply change the final state.

6.4. Percolation methods

Percolation methods identify influential nodes by studying connectivity changes after probabilistic edge or node removal. They support scalable spreader selection and influence maximization through cluster structure and optimal-percolation formulations.

  • Percolation foundations: Bond percolation preserves each edge with probability p, and a giant component emerges only when p exceeds a critical threshold pc.
  • Influential spreaders: Percolation-based spreader selection repeatedly removes links, ranks nodes associated with large resulting clusters, and recommends the highest-scoring W nodes.The method has complexity O(t|V|) and produced more evenly distributed spreaders than conventional centralities on Facebook and Email-Enron networks.
  • Optimal percolation: Optimal influence can be formulated as minimizing the largest eigenvalue of a nonbacktracking operator for a specified preserved-node fraction q.
  • Optimal percolation: Collective Influence removes nodes iteratively according to a radius-l index and scales as O(NlogN).Larger l gives better approximations to the optimal solution, while removal continues until the giant component vanishes.
  • Spreading dynamics: SIR spreading separates into local and global phases, and a characteristic local length scale can predict early whether spreading becomes widespread.The review reports that global influence can be exactly measured using purely local network information.

7. On weighted networks

Weighted-network methods incorporate link strengths into centrality and core-based analyses. They modify degree, shell decomposition, H-index, and shortest-path definitions to represent both connectivity and interaction intensity.

  • Weighted structural measures: Node strength sums incident link weights and combines connectivity with the importance of associated links.In real weighted networks, strength commonly scales nonlinearly with degree as s ∝k^θ, θ≠1.
  • Weighted coreness: Weighted core decomposition replaces degree with a tunable weighted degree, recovering classic k-shells when α=1, β=0 and s-shells when α=0, β=1.When α=β=1, degree and strength receive equal treatment.
  • Weighted coreness: The weighted decomposition iteratively removes nodes below the current minimum weighted degree and assigns each node a weighted coreness shell.
  • Weighted H-index: The weighted H-index applies an H function to neighbors’ weighted degrees together with their corresponding link weights.Its value is the x-coordinate where y=f(x) intersects y=x, including intersections on vertical or horizontal staircase segments.
  • Weighted H-index: The weighted H-index sequence converges to each node’s weighted coreness in weighted undirected simple networks.
  • Weighted closeness centrality: Weighted closeness redefines shortest paths using link weights and can tune the trade-off between path length and the number of intermediary nodes.For 0<α<1, paths with fewer intermediary nodes are favored; for α>1, tie weights matter more and longer paths are favored.

7.2. D-S evidence theory

D-S evidence theory combines degree and strength to estimate node importance under uncertainty. The resulting evidential centrality treats higher importance probability and lower unimportance probability as signs of greater vitality.

  • Motivation: D-S evidence theory synthesizes node degree and strength to quantify importance under uncertainty.It provides a reasoning framework requiring weaker conditions than Bayesian probability theory.
  • Evidence representation: Degree and strength are represented as evidence over the high and low importance states.Basic probability assignments are constructed separately for each factor.
  • Evidence representation: The uncertainty masses mdi(θ) and msi(θ) record how much the theory cannot determine about a node’s importance.These masses are defined as the residual probability after assigning support to high and low importance.
  • Evidence combination: Dempster’s rule combines degree- and strength-based evidence while accounting for conflicting assignments through K.The combined probabilities mi(h), mi(l), and mi(θ) are normalized by 1 − K.
  • Centrality measure: Evidential centrality ranks a node as more vital when its importance probability is higher and its unimportance probability is lower.The measure distributes residual uncertainty before comparing the resulting importance and unimportance probabilities.
  • Limitations and extension: Evidential centrality assumes a uniform degree distribution and has been criticized for ignoring global network structure.Evidential Semi-local centrality was proposed to address these limitations by incorporating degree-distribution effects and extended semi-local information.

8. On bipartite networks

Bipartite networks separate nodes into two disjoint groups with links only across groups, supporting applications such as reputation systems. In online rating networks, methods estimate item quality and user reputation using statistical, iterative, and mutual-reinforcement approaches.

  • Network structure: A bipartite network divides nodes into disjoint subsets X and Y, with no edges between nodes in the same subset.It is denoted B(X, Y, E), where E contains only cross-group edges.
  • Network structure: Bipartite networks model relationships such as heterosexual relations, metabolic substance–reaction links, and participant–event collaborations.These examples demonstrate that many real-world systems naturally contain two node groups.
  • Network structure: Bipartiteness can be tested in linear time by breadth-first search using alternating binary labels across neighboring nodes.A node receiving inconsistent labels certifies that the network is not bipartite.
  • Reputation systems: Online rating systems require reputation methods because unreliable or manipulated users can bias item evaluations.The goal is to produce credible assessments of both user reputation and item quality.
  • Reputation systems: Users and items form a weighted bipartite network, where link weights encode the type and intensity of user–item interactions.The network is represented as G(U, I, W), with users U, items I, and interactions W.
  • Statistical methods: Average ratings provide the simplest item-quality estimate, while reputation-weighted calculations give more reliable users greater influence.User reputation may be externally supplied or inferred from previous ratings.
  • Statistical methods: Group-based ranking estimates reputation by grouping users with similar rating patterns and using group sizes.Its basic assumption is that users consistently belonging to larger groups are more likely to be reliable.
  • Iterative methods: Iterative refinement alternates between updating item qualities from user reputations and reputations from item qualities until convergence.IR uses rating-quality mean squared error, whereas CR uses Pearson correlation between ratings and item qualities.

9. Performance evaluation

The review evaluates representative vital-node algorithms across real networks, considering both functional spreading influence and structural connectivity. Results vary by network type and objective, with no single method consistently best.

  • Eight representative algorithms are compared on four undirected unweighted real networks, evaluating both functional and structural importance.
  • LocalRank and eigenvector centrality perform overall best for identifying individual nodes with high spreading influence.LocalRank is the strongest among five local centralities, while eigenvector centrality leads four global centralities.
  • Degree performs best for network robustness, indicating that high-degree nodes are especially important for maintaining connectivity in the tested undirected networks.H-index and LocalRank also perform relatively well, while betweenness is the strongest of the four global centralities.
  • In directed networks, in-degree attacks make the network more vulnerable, while robustness and critical-portion measures can differ across networks.
  • For weighted networks, node strength generally outperforms weighted H-index and weighted coreness for connectivity, whereas PageRank and LeaderRank differ by network and task.LeaderRank is better than PageRank on two directed networks, while PageRank is better than LeaderRank on two directed networks for connectivity.
  • For bipartite rating data, IARR2 with θ = 1 performs best by AUC on Netflix and MovieLens, while IARR performs best for Pearson correlation across users and items.The parameter θ in IARR and IARR2 is reported to be highly sensitive.
  • For selecting sets of influential nodes, Ji’s method and VoteRank achieve relatively high information coverage, while CI performs best for network connectivity.Closeness is overall worst for spreading influence, whereas removing nodes selected by Ji’s and Hu’s methods can hardly disintegrate the network in most cases.

10. Applications

Applications of vital-node identification span social influence, essential-protein detection, scientific impact, financial risk, career movement, and software reliability. Across these settings, results show that performance depends on the objective, network, and information incorporated.

  • Identifying influential spreaders in social networks: Large-scale mobile-message experiments compared LeaderRank and out-degree centrality for selecting influential users in a directed communication network.The network contained 9,330,493 nodes and 23,208,675 links, with users selected from 31 days of forwarding data.
  • Identifying influential spreaders in social networks: LeaderRank was more resilient to spammers than out-degree centrality, with 207 versus 22 forwarding users when spammers were present.After removing spammers, out-degree improved from 22 to 62 forwarding users, whereas LeaderRank changed from 207 to 221.
  • Quantifying scientific influences: Essential-protein detection improved when centrality was combined with gene-expression information: PeC outperformed topology-only measures, while integrated methods showed similar performance.The comparison included sixteen centrality measures on a yeast protein-protein interaction network.
  • Quantifying scientific influences: Scientific-influence applications address weaknesses of publication counts and citation counts, including papers that initially receive few downloads but later attract many citations.An algorithm deployed at the Econophysics Forum helped highlight such valuable papers.
  • Quantifying scientific influences: A limitation in measuring scientific influence is that treating all co-authors as equally important overlooks differences in contribution, time dependence, and collaboration structure.The review describes alternative credit-assignment approaches, including order-based and community-perceived contribution measures.
  • Detecting financial risks: Financial-risk applications use DebtRank and related centralities to assess systemic importance, with Japanese results linking bank importance to size through a power-law relation.The reported relation was D(banks) + D(firms) = 6.55 × 10^-19 S^1.50, and doubling size increased DebtRank by 1.82 times.
  • Predicting career movements: Career-movement analyses found PageRank and LeaderRank most positively related to promotion, while several degree, strength, and k-core measures were negatively related to resignation.Software-network studies additionally reported that central modules were more failure-prone and that closeness centrality predicted post-release failures.

11. Outlook

The review identifies benchmark experiments, method development, broader research scopes, and large-scale real applications as critical priorities for vital-node research. These priorities address dependence on objectives, dynamics, network structures, and limited real-world validation.

  • Future research priorities: Benchmark experiments are needed because algorithm performance depends on objectives, dynamical-process parameters, and network structures.The review notes that selective reporting can favor algorithms, while real-dynamics experiments could provide stronger comparisons.
  • Future research priorities: Vital-node methods require further development, including better organization and classification of the many existing centralities.The review highlights closely related measures such as PageRank and LeaderRank, and betweenness and closeness.
  • Future research priorities: Research scopes should expand beyond giant-component size and spreading dynamics to additional objectives, processes, and network types.Suggested directions include efficiency, coverage, synchronization, transportation, routing, cascading, evolutionary games, and spatial, temporal, and multilayer networks.
  • Future research priorities: Large-scale real-world applications are needed in settings such as patient treatment and commercial advertising.Such applications would complement experiments and encourage further study, although they cannot replace systematic algorithm comparisons.
Loading 1607.01134v1…