Vital nodes identification in complex networks

• Vital-node identification supports epidemic control, advertising, infrastructure protection, resource allocation, drug discovery, connectivity management, sports evaluation, and scientific prediction.These applications arise because scale-free networks can assign substantially different structural and functional roles to different nodes.Source: §1 · p. 4
• No universal importance index exists: objectives differ, and method performance can change across networks or objective-function parameters.Local and parameter-free indices are simpler and cheaper but generally less accurate than global or multi-parameter approaches, creating a central tradeoff.Source: §1 · p. 4
• Identifying a vital set is especially difficult because combining individually influential nodes can produce overlapping influence, making direct heuristics unreliable.Set identification is more relevant to applications such as immunizing or advertising to groups, while spatial, temporal, and multilayer networks pose additional challenges.Source: §1 · pp. 4–5
• The review systematically clarifies concepts and metrics, classifies problems and methods, surveys progress and the state of the art, and identifies open challenges.It emphasizes physics-rooted approaches while using language intended to support communication between computer scientists and physicists.Source: §1 · p. 5
• The review covers individual-node methods, set identification, weighted and bipartite networks, empirical comparisons, applications, and future outlook.Its empirical analyses compare representative methods across disparate real networks and different objective functions to assess similarities, differences, advantages, disadvantages, and applicability.Source: §1 · p. 5

Overview

• Structural centralities assign each node a real-valued score from topology to rank importance, enabling applications independent of the dynamical process under study.The review distinguishes these measures from iterative-refinement methods that use dynamical processes or iterative algorithms to explore structural properties.Source: §2 · pp. 5–6

Neighborhood-based centralities

• Neighborhood-based methods progress from degree and LocalRank to ClusterRank, coreness, and H-index by incorporating wider neighborhoods, clustering, location, or recursive structure.LocalRank uses fourth-order neighbors; ClusterRank penalizes local interconnectedness; coreness uses k-core decomposition, while degree, H-index, and coreness form initial, intermediate, and steady states of a discrete-operator sequence [33, 36, 37, 40, 41, 42].Source: §2 · p. 6

Path-based centralities

• Path-based centralities assess information dissemination through distances and shortest-path structure: eccentricity uses maximum distance, closeness aggregates distances, and betweenness measures shortest-path control.Eccentricity is sensitive to unusual paths, whereas closeness reduces that disturbance by summing distances; the passage states that smallest closeness indicates the best information-flow vision and largest betweenness the strongest control.Source: §2 · p. 6
• Beyond shortest paths, Katz, subgraph, and information indices weight longer or repeated paths less because information transmission is assumed to weaken with path length [46, 47, 48].Katz includes all paths with decreasing length weights, subgraph centrality counts weighted closed paths, and the information index measures information across all possible paths.Source: §2 · p. 7

2.1.1. Degree centrality

• Degree centrality ranks nodes by directly connected neighbors and can outperform more complex centralities for network vulnerability and low-rate spreading tasks.In directed networks, in-degree reflects popularity and out-degree reflects social activity, while weighted networks use strength instead of degree.Source: §2.1.1 · p. 7

2.1.2. LocalRank

• LocalRank extends degree centrality by incorporating fourth-order neighborhood information while retaining near-linear computational complexity, O(n⟨k⟩2), and weighted-network extensibility.It addresses degree centrality’s limited information by using the number of nearest and next-nearest neighbors.Source: §2.1.2 · p. 8

2.1.3. ClusterRank

• ClusterRank combines nearest-neighbor counts with interactions among neighbors, weighting nodes inversely with local clustering through functions such as f(ci) = 10−ci.Related approaches assess influence through the number of connected communities or structural holes.Source: §2.1.3 · pp. 8–9

2.1.4. Coreness

• Coreness uses k-core decomposition to identify centrally located nodes, but it is coarse-grained, requires global topology, and can fail to distinguish nodes in BA or tree-like networks.Mixed-degree, distance-to-core, community-aware, tie-aware, behavioral, and redundant-link-removal extensions refine coreness [63].Source: §2.1.4 · pp. 9–10, §2.1.5 · p. 10

2.1.5. H-index

• H-index is a local centrality based on neighbors’ degrees, and iterative application of its operator converges to coreness, making degree, H-index, and coreness successive states [40, 41, 42].The measure extends to directed and weighted networks through Hin-index, Hout-index, and weighted H-index variants.Source: §2.1.5 · p. 11

2.2.1. Eccentricity

• Eccentricity ranks nodes by their maximum shortest-path distance to others, with smaller values indicating greater influence.A few unusually long paths can distort this measure, causing eccentricity to misidentify the most influential node.Source: §2.2.1 · pp. 11–12, Figure 3 · p. 12

2.2.2. Closeness centrality

• Closeness centrality uses the inverse mean geodesic distance, representing information-flow efficiency; harmonic distances extend it to disconnected networks.The node with the highest closeness has the best overall vision of information flow, while 1/∞ = 0 handles unreachable pairs.Source: §2.2.2 · pp. 12–13

2.2.3. Katz centrality

• Katz centrality sums contributions from all paths while suppressing longer paths by s^p, requiring s below the reciprocal of the adjacency matrix’s largest eigenvalue.Despite its mathematical structure, its high computational complexity limits use in large-scale networks.Source: §2.2.3 · p. 13

2.2.4. Information index

• The information index aggregates information over all possible paths, where longer paths transmit less, and is equivalent to electrical conductance between node pairs.It is a variation of closeness centrality and can be extended to weighted networks.Source: §2.2.4 · p. 14

2.2.5. Betweenness centrality

• Betweenness centrality measures a node’s control over information flow by counting shortest paths through it; in scale-free networks, its distribution follows a power law.It equals the load at a node when every node sends one packet to every other along shortest paths, with equal splitting across equivalent routes.Source: §2.2.5 · pp. 14–15

2.2.6. Subgraph centrality

• Subgraph centrality weights closed walks by length, supports motif detection, and has strong node-identification performance.For simple connected networks with n > 1, its stated inequality becomes equality if and only if the network is complete.Source: §2.2.6 · pp. 16–17

3. Iterative refinement centralities

• These centralities implement mutual enhancement across different network settings: eigenvector centrality and cumulative nomination target undirected networks, whereas PageRank, LeaderRank, and HITs are mainly used for directed networks.PageRank originated in web-page ranking and LeaderRank addresses its dangling-node problem by adding a ground node.Source: §3 · pp. 17–18

3.1. Eigenvector centrality

• Eigenvector centrality assigns higher importance to nodes connected to influential neighbors, computing scores through power iteration until reaching a steady state.Its score can concentrate on a few nodes, motivating nonbacktracking centrality for undirected networks and alpha centrality for directed networks with many zero-status nodes [97, 98, 99].Source: §3.1 · p. 18

3.2. Cumulative nomination

• Cumulative nomination repeatedly adds each node’s neighbors’ nomination values to its own, stopping at a steady state and improving convergence because its update vector uses the previous iteration’s values [71].The method has a formula similar to alpha centrality, but alpha centrality uses a fixed exogenous vector whereas cumulative nomination updates that vector across iterations.Source: §3.2 · p. 19

3.3. PageRank

• PageRank extends eigenvector centrality through directed-network random walks, redistributing page importance along outgoing links while using random jumping to address dangling nodes and nonconvergence.The jumping probability s is often set around 0.85 but should be tested for different scenarios.Source: §3.3 · pp. 19–20

3.4. LeaderRank

• LeaderRank adds a ground node to make the network strongly connected, producing a parameter-free method that converges faster and outperforms PageRank in ranking effectiveness and robustness.The augmented network has n + 1 nodes, m + 2n directed links, and diameter 2; the ground node’s final value is evenly distributed among other nodes.Source: §3.4 · pp. 20–21

3.5. HITs

• HITs separates directed-network importance into mutually reinforcing authority and hub scores, where authorities receive links from strong hubs and hubs point to strong authorities.The converged scores are normalized greatest eigenvectors of A^TA for authorities and AA^T for hubs [127, 128].Source: §3.5 · p. 21

3.6. SALSA

• SALSA maps a directed network to a bipartite undirected network and computes independent random walks for hubs and authorities, making it equivalent to weighted in-degree analysis and more computationally efficient than HITs.The mapping removes isolated nodes and represents each directed link through a hub-to-authority connection.Source: §3.6 · p. 22, Figure 4 · p. 23

4. Node operation

• Node removal identifies important nodes by the damage they cause to giant-component size, connected components, or connectivity, while node contraction evaluates increased network agglomeration.Counting components cannot distinguish differently sized or functional components, motivating path-based measures such as shortest-distance damage, closeness, and betweenness centrality.Source: §4 · pp. 23–24

4.1. Connectivity-sensitive method

• Connectivity-sensitive methods distinguish direct and indirect losses after removal, emphasizing disconnections involving removed nodes and short-distance connections over indirect or long-distance losses.For single-node removal in large networks, indirect loss may vanish, reducing shortest-distance damage to the sum of inverse distances from the removed node, equivalent to closeness centrality.Source: §4.1 · p. 24

4.2. Stability-sensitive method

• Node importance can be assessed by how removal changes vulnerability, including residual closeness, shortest-path measures, disjoint-path measures benchmarked against fully connected networks, or spanning-tree counts [136][139].Source: §4.2 · pp. 25–26

4.3. Eigenvalue-based method

• Eigenvalue-based methods measure dynamical importance by the relative decrease in the adjacency matrix’s largest eigenvalue after node removal, with larger decreases indicating greater importance.The perturbative approximation can also handle directed and weighted networks and measure link importance with a different formula.Source: §4.3 · pp. 26–27

4.4. Node contraction method

• Node contraction measures importance through the increase in agglomeration after merging a node with its neighbors, combining degree and betweenness effects but remaining too costly for large networks.Agglomeration depends on node count and average shortest distance; the metric reflects both neighbor count and shortest-path location, while repeated average-distance calculations limit scalability.Source: §4.4 · pp. 27–28

5. Dynamics-sensitive methods

• Structural centralities can rank nodes differently across dynamical parameters, motivating methods that incorporate the target process rather than assuming one universal centrality.In SIR, degree centrality performs better at small β, whereas eigenvector centrality performs better near βc; influence rankings depend strongly on spreading and recovery rates.Source: §5 · p. 28

5.1. Path counting methods

• Path-counting methods weight walks or paths according to dynamics-specific transmission effects, including dynamical influence, SIS alpha-centrality formulations, and routing betweenness for traffic.Dynamical influence generalizes across SIR, voter, Ising, and Kuramoto models; routing betweenness instead counts paths passing through a node under specified routing rules, while path independence and computational cost remain challenges for infection-walk methods.Source: §5.1 · pp. 29–32

5.2. Time-aware methods

• Time-aware methods quantify influence within finite horizons, with dynamics-sensitive centrality outperforming methods without temporal factors and with rankings changing between small and very large t.The Boolean-network analysis found dynamics-matrix eigenvector centrality superior to adjacency-based eigenvector centrality, while degree centrality was better for small t and eigenvector centrality for very large t.Source: §5.2 · pp. 32, 34

5.3. Others

• Other methods include epidemic centrality, game centrality, and percolation centrality, but they face predictive, theoretical, or state-definition limitations.Game centrality uses simulated defecting-node dynamics and is ad hoc; percolation centrality is weighted betweenness that reduces to ordinary betweenness when all nodes share the same percolation level.Source: §5.3 · pp. 34–36

Motivation

• Small vital-node sets are needed for network marketing, epidemic immunization, and military counterwork under limited budgets, time, or resources.The selected nodes should trigger purchases, protect populations, or reduce an adversary’s communication capacity.Source: §6 · p. 36

Centrality-based selection

• Selecting the top-k nodes by a centrality measure is a common benchmark, but rich-club clustering can make targeting all highly ranked nodes unnecessary and inefficient.Top-k largest-degree nodes are specifically identified as a benchmark in many applications.Source: §6 · p. 36

Problem formulation

• Influence maximization seeks node sets satisfying specific structural or functional objectives and is introduced through problem descriptions, pioneer techniques, and state-of-the-art progress.The section emphasizes contributions developed by statistical physicists alongside representative computer-science techniques.Source: §6 · p. 36

6.1. Influence maximization problem (IMP)

• IMP seeks a size-k node subset S maximizing an influence function f(S), classified as structural when topology-determined and functional when process-dependent.The influence function may range from simple structural measures to parameterized dynamical mechanisms.Source: §6.1 · p. 36

6.1.1. Structural IMP

• Structural IMP includes selecting nodes whose removal most decreases specified-pair maximum flow, increases shortest distance, or fragments the network into disconnected components.Optimal percolation formulates superspreader identification and epidemic immunization through minimizing the removed set that breaks network connectivity.Source: §6.1.1 · pp. 36–37
• The feedback vertex set problem removes at least one vertex from every cycle, is NP-complete for minimum size, and relates closely to IMP; minimum dominating sets can approximate IMP [191, 196, 197].Weighted FVS minimizes total node weight, while MDS selects the smallest set covering every node or its neighbors.Source: §6.1.1 · p. 37

6.1.2. Functional IMP

• Functional IMP maximizes outcomes such as product sales by choosing customers for marketing actions, with purchase probability combining intrinsic propensity, neighbor influence, and self-reliance.The general model is NP-hard, although a simple linear model can be solved by a system of linear equations [199].Source: §6.1.2 · pp. 37–38
• Kempe, Kleinberg and Tardos defined influence as expected final activations in monotone spreading processes and showed IMP is NP-hard under linear-threshold and independent-cascade models.Their framework enabled simulation-based algorithm comparisons; SIR closely matches independent cascade, while non-progressive threshold dynamics resemble SIS.Source: §6.1.2 · pp. 38–39

6.2.1. Heuristic algorithms

• Heuristic methods commonly select top-k nodes by centrality, but adaptive recalculation, VoteRank, graph coloring, and equal graph partitioning reduce clustering or improve fragmentation.VoteRank updates neighboring voting abilities after each selection and outperforms ClusterRank and coreness in SIR simulations; EGP performs significantly better than selecting highest-degree or highest-betweenness nodes but is more time-consuming and does not directly solve k-IMP.Source: §6.2 · p. 39, §6.2.1 · pp. 40, 42

6.2. Heuristic and greedy algorithms

• Heuristic algorithms have diffuse boundaries, so the review separates methods with more specific shared methodologies and omits purely optimization or machine-learning algorithms [20].The section presents representative heuristic and greedy designs rather than an exhaustive account of all extensions.Source: §6.2 · p. 40, §6.2.2 · p. 45

6.2.1. Heuristic algorithms

• Degree discount nearly matches greedy accuracy while running more than one-millionth faster than the fastest greedy algorithm, especially when p ≪1.For a candidate vi with si selected neighbors, its degree is discounted by 2si+(ki−si)sip under the independent cascading model.Source: §6.2.1 · p. 40

6.2.2. Greedy algorithms

• The original greedy algorithm repeatedly scans all unselected nodes for maximum marginal influence, but its simulation cost makes it impractical for large-scale networks.For k-IMP with n nodes, m links, and R simulations, the stated complexity is O(kRNM), and even networks with tens of thousands of nodes can require days.Source: §6.2.2 · pp. 43–44
• Greedy hill-climbing achieves a (1 − 1/e)-approximation for independent cascade, linear threshold, and decreasing cascade models, and outperforms simple degree- or closeness-based selection.The guarantee follows from submodularity; the decreasing cascade model additionally requires order-independent and non-increasing activation probabilities.Source: §6.2.2 · pp. 43–44
• CELF exploits submodularity to avoid unnecessary reevaluations and is 700 times faster than original greedy on some network instances, while percolation-based greedy has complexity O(kRM).The percolation approach is in principle N times faster than the original greedy algorithm and runs remarkably faster than CELF in the reported comparison.Source: §6.2.2 · pp. 44–45

Structural influence maximization

• Zhou transforms the FVS problem by representing global cycle constraints as local edge constraints over discrete vertex states, where valid configurations induce trees or single-cycle components.Removing one vertex from each single-cycle component yields a feedback vertex set, so more occupied nodes generally correspond to smaller FVS weight.Source: §6.3 · pp. 45–46
• The resulting self-consistent belief-propagation equations use the Bethe-Peierls approximation, which factorizes neighboring cavity probabilities and works best when networks are locally tree-like, especially sparse real networks.Iterative solution with large reweighting parameter x targets maximum occupied weight and hence minimum FVS weight, but excessively large x can cause divergence and node-removal updates select only a small fraction each round.Source: §6.3 · pp. 46–47
• Mugisha and Zhou [254] reported markedly better optimal-percolation performance than Ref., whereas Morone et al. [262] disputed this advantage with a faster variant; the comparison remains debated.The message-passing FVS framework can therefore be extended to optimal percolation, but reported performance depends on the algorithmic variant.Source: §6.3 · p. 48

Functional influence maximization

• For the linear-threshold model, Altarelli et al. represent the dynamical process by node activation times and consider pairs of times because single-variable constraints create many short loops.Source: §6.3 · p. 48

Scope and applicability

• Because message-passing theory does not require submodular objectives, it may apply more broadly than greedy algorithms to dynamical processes where phase transitions cause sharp changes in final activity.The review notes that greedy methods remain usable when approximation guarantees are not required.Source: §6.3 · p. 49

Percolation foundations

• Bond percolation preserves edges with probability p and produces a giant component only above a critical threshold pc, whereas site percolation assigns preservation probability to nodes.The SIR model with transmissibility p is equivalent to bond percolation with bond occupation probability p.Source: §6.4 · p. 49

Bond percolation

• Ji et al. [266] identify W spreaders by repeatedly removing edges, scoring high-degree nodes across resulting clusters, and ranking nodes by accumulated scores.The method is parallelizable with complexity O(t|V |). On Facebook and Email-Enron, it produces more evenly distributed spreaders than degree, betweenness, closeness, and k-shell methods, increasing coverage and reducing redundancy.Source: §6.4 · pp. 49–50

Optimal percolation

• Collective Influence (CI) approximates optimal site percolation by iteratively removing the highest-CI node until the giant component vanishes, scaling as O(NlogN).Larger neighborhood radius l yields better approximations, while extremal optimization provides the underlying exact-system formulation but is not scalable to large networks.Source: §6.4 · p. 50
• Optimal percolation maps minimizing activated spreaders or maximizing epidemic immunization onto finding a minimal node set that disrupts global connectivity, an NP-hard problem.The formulation minimizes the largest eigenvalue of a nonbacktracking operator for a specified preserved-node fraction q.Source: §6.4 · p. 50

Local-information spreading

• Hu et al. [271] found that SIR spreading separates into local and global phases, enabling nearly optimized selection of W spreaders using purely local network information.A node’s influence equals giant-component size times its probability of belonging to that component; the greedy algorithm’s runtime is independent of network size.Source: §6.4 · p. 51

7. On weighted networks

• Weighted networks represent interaction strength through positive edge weights, motivating weighted clustering, assortativity, modularity, and extensions of unweighted vital-node methods.Examples include air transportation, scientific collaboration, and neural networks, where weights quantify seats, coauthored papers, or interaction strength.Source: §7 · p. 51

7.1.1. Node strength

• Node strength sums incident edge weights, combining connectivity with link importance; in real networks it often scales nonlinearly with degree as s ∝ k^θ, θ ≠ 1.Directed networks additionally use in-strength and out-strength, and normalized strength yields weighted degree centrality.Source: §7.1.1 · p. 52

7.1.2. Weighted coreness

• Weighted coreness replaces degree with a tunable combination of degree and strength, recovering k-shell when α = 1, β = 0 and s-shell when α = 0, β = 1.Iterative pruning assigns weighted shell layers after removing nodes below the current minimum weighted degree; the resulting s-core depends on topology and degree–weight correlations.Source: §7.1.2 · pp. 52–53

7.1.3. Weighted H-index

• The weighted H-index applies an H function to neighbors’ weighted degrees together with link weights, ranking neighbors by strength and returning the intersection of y = f(x) and y = x.For weighted undirected simple networks, every node’s iterated weighted H-index sequence converges to its weighted coreness.Source: §7.1.3 · pp. 53–54

7.1.4. Weighted closeness centrality

• Weighted closeness and betweenness redefine shortest paths using reciprocal edge weights, while a tunable α additionally controls the importance of intermediary-node count.At α = 0, distances match unweighted paths; α = 1 gives inverse-weight distances, 0 < α < 1 favors fewer intermediaries, and α > 1 favors longer paths when weights dominate.Source: §7.1.4 · pp. 54, 56, §7.1.5 · p. 56

7.1.5. Weighted betweenness centrality

• Weighted betweenness counts shortest paths defined by the weighted-distance rule and assigns credit according to how often those paths pass through each node.Its formulation uses the same intermediary-sensitive path definition and positive tunable parameter α as weighted closeness.Source: §7.1.5 · p. 56

7.1.6. Weighted PageRank and LeaderRank

• Weighted PageRank distributes each node’s score to outgoing neighbors proportionally to link weights, replacing ordinary random walks with weighted random walks; weighted LeaderRank applies an analogous extension.Weighted LeaderRank adds a ground node, redistributes its converged score equally, and has been used to rank software developers from communication weights.Source: §7.1.6 · pp. 56–57

7.2. D-S evidence theory

• D-S evidence theory combines degree and strength to estimate whether each node is important, unimportant, or unknown, under weaker assumptions than Bayesian probability.The framework explicitly permits an unknown state when available evidence cannot determine node importance.Source: §7.2 · p. 57
• Basic probability assignments separately map normalized degree and strength to high and low importance states within the discernment frame θ = (high, low).For each node vi, mdi(h), mdi(l), msi(h), and msi(l) represent evidence from degree and strength for importance or unimportance.Source: §7.2 · p. 57
• Dempster’s rule combines the degree and strength BPAs, accounting for conflict K and residual uncertainty mi(θ), whose average allocation yields final importance and unimportance probabilities.The resulting evidential centrality increases with higher Mi(h) and/or lower Mi(l).Source: §7.2 · p. 58
• The method assumes a uniform degree distribution, limiting effectiveness, and EVC centrality omits global network structure.These limitations motivate Evidential Semi-local centrality, which incorporates degree-distribution effects through an extended semi-local formulation.Source: §7.2 · p. 58
• Neighborhood connection patterns add local structure information to evidential centrality, further enhancing its effectiveness.This extension explicitly considers topological connections among a node’s neighbors.Source: §7.2 · p. 58

8. On bipartite networks

• Bipartite networks B(X, Y, E) partition nodes into two disjoint groups, permit edges only between groups, and include many real-world systems.Examples include heterosexual relations, metabolic networks, collaborations, telephone networks, and user-object commerce networks.Source: §8 · pp. 58–59
• Bipartite structure has no odd cycles, admits binary coloring, and has symmetric spectrum; breadth-first or depth-first search tests bipartivity in linear time.For monopartite networks, bipartivity measures distance from bipartiteness; Internet-community data typically has higher bipartivity than collaboration networks.Source: §8 · p. 59

8.1. Reputation systems

• Reputation systems address unreliable or manipulated user ratings by jointly identifying high-reputation users and high-quality items in user-item bipartite networks.Weighted links encode interaction intensity, while thresholds can convert weighted networks into unweighted networks; seller spamming motivates reputation correction.Source: §8.1 · pp. 59–60

8.2. Statistical methods

• Statistical methods improve average ratings by weighting item quality according to user reputation, while group-based ranking estimates reputation from users’ rating-pattern group sizes.The group-based ranking procedure constructs score-item and rewarding matrices before computing reputation from the mean-to-standard-deviation ratio; iterative refinement extends it [300].Source: §8.2 · pp. 60, 62

8.3. Iterative methods

• Iterative methods alternate item-quality and user-reputation updates until convergence, including error-based IR, correlation-based CR, and redistribution-based IARR and IARR2.IARR increases prestigious users’ influence, while IARR2 penalizes low-reputation raters and users rating few items.Source: §8.3 · pp. 62–63

8.4. BiHITS and variants

• biHITS jointly propagates user reputation and item fitness through weighted bipartite links, with a unique initialization-independent solution when the network is connected.Scores are normalized during iteration, which stops when total absolute changes fall below ε; unweighted networks use the adjacency matrix.Source: §8.4 · pp. 63–64

8.4.1. Algorithms with content information

• Generalized Co-HITS incorporates user- and item-side content through personalized parameters and text relevance initialization, reducing to ordinary biHITS when λU = λI = 1.The method supports iterative and regularization frameworks, with relevance functions including vector-space and statistical-language models.Source: §8.4.1 · p. 64

8.4.2. Algorithms with user trustiness

• BiHITS variants incorporate social trust and provider credit: QTR improves rankings using user relationships, while Eigen-Rumor and QRC model user-item-provider interactions [311].QTR reduces to biHITS when all parameters are zero; Eigen-Rumor balances provider credit and user ratings through ω, and QRC models negative effects from low-scoring entities.Source: §8.4.2 · p. 65, §8.4.3 · p. 66

9.1. On undirected networks

• Across four undirected networks, LocalRank and eigenvector centrality perform best overall for spreading influence, while betweenness performs poorly and H-index and coreness outperform degree.LocalRank is best among five local centralities, eigenvector centrality among four global centralities, and LocalRank sometimes exceeds global methods.Source: §9.1 · p. 68, Table 3 · p. 68
• For connectivity in four undirected networks, degree performs best overall, with H-index and LocalRank relatively strong and betweenness usually second best among global centralities.Lower robustness R and critical portion pc indicate better performance; degree’s result suggests high-degree nodes are important for connectivity.Source: §9.1 · p. 69, Table 4 · p. 69, Table 5 · p. 70

9.2. On directed networks

• On four directed networks, local methods generally outperform global methods for spreading influence, while LeaderRank exceeds PageRank in all four networks.The study uses SIR spreading along directed links, and performance varies substantially across networks, preventing a single overall best algorithm.Source: §9.2 · p. 71, Table 7 · p. 72
• For directed-network connectivity, in-degree is generally a strong indicator and produces the lowest robustness in some cases, although robustness and critical-portion results can differ.For Delicious, in-degree has the lowest R but a larger pc than PageRank and LeaderRank.Source: §9.2 · p. 71, Table 8 · p. 72, Table 9 · p. 72

9.3. On weighted networks

• In weighted networks, H-index and coreness identify influential spreaders well and can outperform some global methods, while LeaderRank exceeds PageRank on two directed networks.Weighted SIR transmission depends on edge weights through probability 1−(1−β)^wij.Source: §9.3 · pp. 73–74, Table 11 · p. 74
• For weighted-network connectivity, node strength performs best overall, leading in three networks and ranking second in USA airports, where PageRank is best.Strength also has the smallest critical portion pc in most cases; PageRank exceeds LeaderRank on two directed networks, while betweenness exceeds closeness on two undirected networks.Source: §9.3 · p. 74, Table 12 · p. 74, Table 13 · p. 75

9.4. On bipartite networks

• On real bipartite datasets, IARR2 with θ = 1 achieves the best AUC for Netflix and MovieLens, while IR is relatively good on Netflix and CR and IARR on MovieLens.The parameter θ in IARR and IARR2 is highly sensitive and must be selected carefully.Source: §9.4 · p. 77, Table 15 · p. 77

9.5. Finding a set of vital nodes

• The set-based evaluation uses Amazon, Cond-mat, Email-Enron, and Facebook networks to compare seven ranking methods under specified Ji and CI parameter settings.The methods are degree, betweenness, closeness, Ji’s percolation method [266], Hu’s percolation method [271], CI, and VoteRank [206].Source: §9.5 · p. 80
• Ji’s method and VoteRank identify relatively influential node sets for maximizing SIR information coverage, followed by Hu’s method, while closeness performs worst.The comparison uses the average final recovered-node ratio after initializing 5% infected nodes selected by each method, as reported in Table 18.Source: §9.5 · p. 80
• CI performs best for preserving network connectivity, while degree, VoteRank, and betweenness also perform relatively well; Ji’s and Hu’s selections rarely disintegrate networks.This evaluation reports robustness R and critical removal portion p_c in Tables 19 and 20.Source: §9.5 · p. 80, Table 19 · p. 81, Table 20 · p. 81

10.1. Identifying influential spreaders in social networks

• LeaderRank selected 1000 users whose total direct forwardings exceeded out-degree centrality by more than 6 times with spammers and 2 times without spammers, while remaining resilient to spammers.In the corresponding experiment, LeaderRank produced 3892 versus 620 forwardings with spammers and 4063 versus 924 without spammers; Fig. 14 compares the forwarding distributions.Source: §10.1 · p. 83, Figure 14 · p. 83

10.2. Predicting essential proteins

• PeC substantially outperformed topology-only centralities for essential-protein prediction, whereas methods integrating topology and biological information showed similar performance.The reviewed methods combine network centrality with gene expression, protein complexes, orthology, co-expression, or related biological information.Source: §10.2 · p. 84, Figure 15 · p. 85, Figure 16 · p. 85

10.3. Quantifying scientific influences

• Scientific influence measures extend beyond publication or citation counts by modeling citation, authorship, temporal, and user-paper relations, while co-author credit, time dependence, and collaboration structure remain important limitations.CiteRank discounts older citations using ρ_i = e−age_i/τdir, AP rank distinguishes prestige from popularity, and the Econophysics Forum deployment highlights valuable papers.Source: §10.3 · pp. 84, 86, 87, 88

10.4. Detecting financial risks

• DebtRank measures distress propagation beyond outright defaults, and in the Japanese credit network DebtRank followed D(banks) + D(firms) = 6.55 × 10−19S^1.50, making larger banks disproportionately important.The exponent ≃1.50 implies that doubling a bank’s size increases its DebtRank by 1.82 times; other methods include impact, vulnerability, and SinkRank centralities.Source: §10.4 · pp. 89–90

10.5. Predicting career movements

• Career movements correlate with network position: central employees are less likely to resign, while higher work-related in-degree predicts promotion and selected centralities predict both outcomes above chance.PageRank and LeaderRank in social networks are most positively related to promotion; resignation is negatively related to specified in-degree, strength, k-core, and work-network degree features.Source: §10.5 · pp. 90–91, Figure 20 · p. 91

10.6. Predicting failures with developer networks

• In developer networks, central software modules are more failure-prone, closeness centrality predicts post-release failures, and combining dependence with contribution networks largely increases predictive power.Developer closeness and betweenness predict failures, while a LeaderRank variant effectively predicts reopened bugs.Source: §10.6 · pp. 91–92

Benchmark experiments

• The field needs solid benchmarks based on real dynamical processes, or an open platform providing reproducible simulations, datasets, and code across objectives and real networks.Comparisons are complicated by objective functions, dynamical parameters, network structures, participant interactions, and message-content effects.Source: §11 · p. 92

Method development

• Methods should be systematically classified and tested on real and tunable artificial networks to quantify sensitivity to structural and dynamical changes and define application ranges.Open problems include identifying influential nodes or sets at finite time t, especially in continuous dynamics, and in incomplete networks.Source: §11 · p. 93

Expanded scope

• Research should extend beyond giant-component size and spreading dynamics to objectives such as efficiency and coverage, processes such as synchronization and routing, and spatial, temporal, and multilayer networks.The proposed expansion targets network features, dynamical processes, and network types with stronger relevance to real-world systems.Source: §11 · p. 93

Real applications

• Large-scale real applications in patient treatment, commercial advertising, and similar settings are needed to encourage further study, while not replacing controlled experiments.The review distinguishes these applications from prior uses that mainly addressed other research problems rather than operational real-world deployment.Source: §11 · p. 93