Critical nodes identification in complex networks: a survey

2.1. Degree centrality

In the study of social network structures, Bavelas et al. ^[13] introduced the concept of centrality, and Nieminen et al. ^[14] addressed the complex and cumbersome calculation of point centrality metrics by proposing a direct measure of node importance through the adjacency matrix. Specifically, the degree of node v_i is defined as follows:

The advantage of this metric is that it is intuitive and easy to understand, with simple computation. However, the node degree metric cannot have comparability across networks of different scales. Building on this, the concept of degree centrality for the entire network is introduced, defined as:

The improved metric enables comparisons across networks of varying sizes. Intuitively, a node with more neighbors is likely to be more influential. However, this metric only considers the local state of node v_i and cannot take into account the local environment of the node. To address the limitations of high computational cost and low local relevance in centrality measures, Chen et al. ^[15] introduced semi-local centrality (SLC), which incorporates the degrees of both first and second-order neighbors with flexible parameters. While degree centrality performs effectively in scenarios with low diffusion probabilities, SLC is better suited for larger diffusion probabilities, capturing broader network influence. To mitigate the sensitivity of centrality measures to diffusion probabilities, Ma et al. ^[16] proposed Laplacian centrality, which measured node influence by the energy change of a network after node removal. It can be easily computed using node degree, significantly reducing computational complexity and offering good scalability, though it only considered nodes and their first-order information. Zhu et al. ^[17] introduced an Improved Laplacian Centrality (ILC) based on the self-consistency concept, incorporating global topological structure information.

2.2. K-shell decomposition

Kitsak et al. ^[18] proposed the $$ k_s $$ index based on node local neighbors, which characterizes the topological structure of each node in the network. The method starts by removing all nodes with $$ k(v)=1 $$ from the network, and these nodes are defined as $$ k_s(v)=1 $$. This process repeats until only nodes with $$ k(v)\geq 2 $$ remain. Next, all nodes with $$ k(v)=2 $$ in the subgraph are removed, and these nodes are assigned an index of $$ k_s=2 $$. This process continues until only nodes with $$ k(v)\geq 3 $$ are left. The procedure stops when no nodes remain in the subgraph. In this way, each node is assigned to a corresponding $$ k $$-shell layer, and the overall $$ k $$-shell decomposition is obtained. This method has low time complexity, but it cannot distinguish the importance of nodes within the same layer.

To distinguish the importance of nodes within the same $$ k $$-shell layer, the $$ k $$-shell index overlooks the edges connected to the deleted nodes and the removal order of nodes during the node ranking process. Zeng et al. ^[19] proposed the Mixed Degree Decomposition (MDD), which combines the degree of remaining and removed nodes to better distinguish nodes in the same $$ k $$-shell layer. This method is effective in networks with special structures, such as trees, stars, and regular graphs. Li et al. ^[20] further classified neighbors by removal order and assigned weights to more accurately capture a node's spreading capability. Liu et al. ^[21] estimated node influence using the shortest distance to core nodes, while Zareie et al. ^[22] used the distance to the network boundary as a proxy for core proximity. However, the $$ O(n^2) $$ computational complexity of shortest path calculations poses challenges for large-scale networks.

Extensive numerical simulations have shown that in some networks, nodes with high $$ k $$-shell indices, even those classified as core nodes, are not always the most influential in information propagation ^[21,22]. This indicates a discrepancy between the actual network core and the $$ k $$-shell decomposition index. Ibnoulouafi et al. ^[23] introduced M-Centrality, which integrates the $$ k $$-shell index with the degree variation features of both nodes and their neighbors. This metric demonstrates robust performance in dynamic transmission and network connectivity, while maintaining a time complexity of $$ O(n) $$. Liu et al. ^[24] proposed a link entropy metric that quantifies link diversity within shells by averaging the link diversity of nodes within the same shell. By normalizing for varying node counts, this method effectively distinguishes true core nodes from quasi-core groups. Additionally, Liu et al. ^[25] argued that dense interconnections among core nodes could hinder effective information diffusion. They introduced edge diffusion importance by removing edges with low diffusion intensity between nodes, and applying $$ k $$-shell decomposition to the pruned network, yielding a more accurate characterization of node importance.

2.3. H-index

H-index is originally designed to gauge the impact of academic journals and researchers. Lü et al. ^[26] extended the H-index to measure node importance in networks. The H-index of node $$ v_i $$ is defined as:

where $$ H(\cdot) $$ is the operator that finds the largest integer $$ h $$ such that the node has at least $$ h $$ neighbors with degree no less than $$ h $$. If the H-index of node $$ v_i $$ is $$ h $$, it means that node $$ v_i $$ has at least $$ h $$ neighbors with degree no less than $$ h $$. In large-scale social citation networks, nodes with the same H-index are often hard to distinguish. To address this, Liu et al. ^[27] proposed the LH-index, incorporating both node and neighbor information. Gao et al. ^[28] introduced the Weighted H-index for weighted networks by integrating edge weights. Furthermore, Zareie et al. ^[29] proposed the Extended H-index centrality (EHC), which considers the cumulative contributions of all neighbors.

2.4. K-truss

Cohen et al. ^[30] introduced the concept of K-truss decomposition for a given unweighted undirected network. Let $$ e_{ij} $$ represent the edge between nodes $$ v_i $$ and $$ v_j $$. In the K-truss decomposition, the support of edge $$ e_{ij} $$ is the number of distinct triangles it forms, denoted as:

where $$ \Delta_{ijk} $$ represents a triangle with vertices $$ i $$, $$ j $$, and $$ k $$, $$ k $$ is a common neighbor of the two nodes, and $$ \Delta_{G} $$ is the set of all triangles in network $$ G $$. The higher the support of an edge, the higher its clustering characteristic. The decomposition proceeds based on edge support. Initially, set the parameter to $$ k=3 $$. Then, remove edges in the network with support less than $$ k-2 $$, and reduce the support of the two other edges forming a triangle with each edge by 1, updating the network topology. Continue removing edges with support less than $$ k-2 $$ until all edges in the network have support greater than or equal to $$ k-2 $$. Nodes removed in this stage are assigned to the k-truss layer. For the next step, increase $$ k+1 $$, and repeat the process of removing edges with support less than $$ k-2 $$ until all nodes in the network are completely assigned to the corresponding layers. Malliaros et al. ^[31] introduced a triangle-graph-based k-core decomposition that refines the analysis of densely connected networks. Their method calculates the "Trustworthness" of an edge, defined by its participation in a k-truss (the number of triangles it is part of). This approach offers a more detailed analysis compared to $$ k $$-shell decomposition, making it particularly effective for identifying influential communities within networks.

2.5. Structural hole

Yu et al. ^[32] introduced the concept of "structural hole" to identify key nodes in a network by defining a node influence matrix $$ P $$. If there is no direct connection or indirect redundancy relationship between two entities or communities, the obstruction between them is called a structural hole:

where $$ p_{ij} $$ represents the proportion of total effort that node $$ v_i $$ contributes to maintaining node $$ v_j $$ as a neighbor, and $$ \Gamma(v_i) $$ is the set of neighbors of node $$ v_i $$. The network constraint coefficient of node $$ v_i $$ is calculated as:

where $$ q $$ is an intermediate node connecting $$ v_i $$ and $$ v_j $$, and $$ p_{iq} $$ and $$ p_{qj} $$ represent the total effort proportions of nodes $$ v_i $$ and $$ v_j $$ in maintaining their neighborhoods with a common neighbor $$ q $$. A smaller constraint coefficient signifies a larger structural hole, making the node more influential in information propagation. Yu et al. ^[33] proposed an improved structural hole method (ISH) that integrates degree and nearest-neighbor information, effectively identifying critical nodes for information propagation by considering edge weights based on neighbor degrees.

In contrast, while the $$ k $$-shell index prioritizes central nodes, it overlooks neighbor interactions and broader topological features. To address this, Xu et al. ^[34] introduced a local centrality measure (VKC) that combines neighborhood information with structural hole concepts, using outward-link diversity and network constraint coefficients. Building on these ideas, Liu et al. ^[35] developed an information control capability index (ICC), integrating $$ k $$-shell values and enhanced structural hole theory. Zhao et al. ^[36] further refined this approach with the SHKS node ranking index, combining $$ k $$-shell and structural hole metrics, identifying vital bridging nodes with lower $$ k $$-shell indices. While "structural holes" focus on nodes controlling parts of the network, they typically overlook the broader network topology. The combination of structural hole theory and $$ k $$-shell methods enhances the overall network capacity ^[37].

2.6. Neighborhood similarity

In a network, two similar nodes are more likely to be interested in transmitting the same information, and the likelihood of information propagating through the edges between the nodes is higher. Wang et al. ^[38] defined the similarity between nodes $$ v_i $$ and $$ v_j $$ based on the number of their common neighbors. Specifically, the more common neighbors two nodes have, the more similar they are. The similarity is mathematically defined as:

where $$ v_{i} $$ and $$ v_{j} $$ represent the starting node and the randomly selected neighboring node, respectively. Lu et al. ^[39] proposed an Extended Similarity Coefficient Ranking Method (ESCRM), which connected the importance of nodes to the local structural similarity between nodes and their neighbors. Ai et al. ^[40] introduced Resource Allocation Similarity (RAS), simulating resource transfers based on the inverse sum of common neighbors to capture both structural and functional similarities. Rao et al. ^[41] discovered small communities from the multilayer network by dice neighborhood similarity (DNS), merging smaller communities and generating larger communities to maximize community influence and find k seed nodes in the multilayer network. Tong et al. ^[42] proposed an Extended Tanimoto Correlation (TC) for topological clustering of neighborhood sets to measure node importance.

3.1. Eigenvector centrality

Eigenvector Centrality (EC) takes into account the importance of a node's neighbors ^[43,44]. It uses the eigenvectors and eigenvalues of the network's adjacency matrix to measure the importance of nodes. The main idea is to assume that the importance of node $$ v_i $$ is denoted as $$ x_i $$. Thus, the eigenvector centrality of node $$ v_i $$ is defined as:

where $$ c $$ is the proportionality constant, and initializing $$ x = [x_{1}, x_{2}, \dots, x_{n}] $$, after several iterations, it converges to $$ x = cAx $$, rewritten as $$ Ax = c^{-1}x $$, meaning $$ x $$ is the eigenvector corresponding to the eigenvalue $$ c^{-1} $$ of the adjacency matrix $$ A $$. Building on this, Ilyas et al. ^[45] introduced Principal Component Centrality (PCC) to identify social hubs in large-scale networks, measuring node influence based on its position using eigenvectors of the adjacency matrix. To identify influential members in social networks, Estrada et al. ^[46] defined subgraph centrality, which sums closed paths within a node's subgraph, with shorter paths contributing more. Ahajjam et al. ^[47] proposed the LeadersRank algorithm, ranking nodes based on eigenvector centrality and identifying communities through second-order neighbors. However, this algorithm primarily bases node importance on immediate neighbors, leading to slow convergence and neglect of external influences.

To address eigenvector centrality's localization issue, which concentrates weight on a few nodes, Martin et al. ^[48] introduced a method based on a non-backtracking matrix. This method avoids localization while yielding similar results to eigenvector centrality in dense networks. Zhong et al. ^[49] combined Jaccard similarity with the dissimilarity between nodes and proposed the eigen-centrality from the differences and similarities of structure (ECDS) centrality method, which takes the weighted sum of the centralities of its neighboring nodes to form an iterative formula similar to the eigenvector centrality.

3.2. Katz centrality

Katz centrality ^[50] extended eigenvector centrality by adding a constant term to describe the importance of the central node itself. It is defined as:

where $$ \beta $$ is a constant, and in matrix form, it can be given as $$ x = cAx + \beta $$, which is equivalent to $$ x = (I - cA)^{-1}\; \beta $$. Here, $$ x $$ represents the Katz centrality vector for all nodes in the network. It assigns different weights to all paths in the network, assuming that longer paths are less important than shorter ones. However, it has a high time complexity and is only applicable to smaller networks with few loops. To address the limitation of betweenness centrality, which only considers the shortest paths and ignores non-shortest paths, Zhang et al. ^[51] proposed the BKC algorithm, which combines path-information and Katz centrality. This approach considers both local and global features, overcoming the limitation of evaluating node importance based solely on neighboring nodes.

3.3. Pagerank algorithm

Traditional ranking methods for webpages rely on "keyword density", but this can be undermined by "malicious keywords." Page et al. ^[52] proposed the core algorithm of Google's search engine, Pagerank. The value of node $$ v_i $$ at time $$ t $$ is defined as:

where $$ k_{j}^{out} $$ represents the out-degree of node $$ v_j $$. However, in practice, there are cases where webpages are unreachable. To address this issue, a random jump probability $$ c $$ is introduced:

where $$ c $$ is a constant derived from experiments. In the PageRank algorithm, each node has the same random jump probability, and the parameter $$ c $$ can be flexibly adjusted based on the network characteristics. The algorithm measures the importance of a webpage based on the quality and quantity of its inbound links. If a webpage is linked by many pages or high-quality pages, it is considered to have greater importance.

To address the limitations of PageRank, such as its failure to incorporate node attributes or external information, Yang et al. ^[53] described the frequency and duration of contact between nodes in a directed weighted network to capture the importance of nodes based on their in-degrees and out-degrees. They proposed the Two-Way-PageRank method to identify important nodes in directed weighted networks. Hsu et al. ^[54] introduced the AttriRank model, which integrates node attribute similarity into the ranking process. This model utilizes random walks, capturing associations between nodes based on both network structure and attribute similarity. The random walk is framed as a Markov chain, with a transition matrix that balances information propagation across the network and node attributes. Building on this, Sheng et al. ^[55] proposed the Trust-PageRank (TPR) algorithm, which combines attribute similarity and trust values, defined through structural degree ratios. TPR effectively merges node attributes and network structure to refine node rankings. Su et al. ^[56] introduced a cascade failure and directionally weighted PageRank method tailored for power grid networks. This approach incorporates grid connectivity, electrical topology, and power flow direction, thus enhancing the grid's resilience by mitigating the impact of cascading failures.

3.4. Voting mechanism

To address the parameter adjustment issue in the PageRank algorithm, Lü et al. ^[57] introduced a background node $$ g $$ in the network, which establishes bidirectional connections with all other nodes, making the network strongly connected. They proposed the LeaderRank (LR) algorithm. Initially, all pages are assumed to have a LR value of 1, while the background node has a LR value of 0. After convergence, the LR value for node $$ i $$ is defined as:

After traversing all the nodes in the network, the LR value is obtained. Compared to PageRank, LR has stronger robustness in resisting spammer attacks and random interference. Building on this, Li et al. ^[58] introduced the weight-LeaderRank algorithm for weighted networks, which modifies the standard random walk by incorporating a biased random walk. This adjustment ensures that neighboring nodes receive higher scores, thereby improving the identification of influential propagators. To address the issue of overlapping influence in methods such as PageRank, ClusterRank, and $$ k $$-shell, Zhang et al. ^[59] proposed the iterative VoteRank method. In this approach, nodes receive votes from their neighbors, and their importance is determined by the number of votes they accumulate. This method reduces to degree-based ranking when all nodes have the same voting ability.

Building on the information of node neighborhood within the network topology, Kumar et al. ^[60] proposed the NCVoteRank method, which adjusts the voting weights according to the core degree of neighboring nodes, adding flexibility to the voting framework. Sun et al. ^[61] enhanced this concept by introducing the weight-VoteRank method, which incorporates both the number of neighbors and edge weights, allowing for a more nuanced measure of node importance in weighted networks. Li et al. ^[62] further refined the VoteRank algorithm with the introduction of Linearity and Importance (DIL) ^[63]. This method initializes node scores and voting abilities based on local importance, and updates the voting capabilities of neighbors in each round. Through iterative voting, the Top-$$ k $$ nodes with the highest scores are selected, improving the efficiency and accuracy of the ranking process. These methods collectively advance the VoteRank algorithm by integrating node neighborhood information, edge weights, and local importance, thereby enhancing the precision and efficiency of node ranking in complex networks.

4.1. Betweenness centrality

Freeman et al. ^[64] reviewed traditional centrality measures to determine the importance of nodes in social networks. Based on the connectivity between nodes, they introduced Betweenness Centrality (BC), which measures the importance of a node by counting the number of shortest paths that pass through the node. It is defined as:

where $$ \left | d_{ij} \right | $$ is the number of shortest paths between nodes $$ v_i $$ and $$ v_j $$, and $$ \left | d_{ij}(v)\right | $$ is the number of shortest paths between nodes $$ v_i $$ and $$ v_j $$ that pass through node $$ v $$. BC takes into account the global features of the network, but its path computation has a high time complexity. Hage et al. ^[65] proposed using the maximum distance between a node and all other nodes in the network as a measure of the node's eccentricity centrality, $$ \text{ECC} $$. The eccentricity centrality of node $$ v_i $$ is defined as:

where the network diameter is the maximum eccentricity value among all nodes in the network $$ G $$, and the network radius is defined as the minimum eccentricity value among all nodes. Clearly, the node whose eccentricity centrality value equals the network radius is the central node. Boccaletti et al. ^[66] proposed the Average Shortest Path (ASP) index, which measures a node's importance based on its effective information transfer to all other nodes. The ASP index is defined as the sum of the shortest path distances from a node to all other nodes, standardized by the total number of node pairs in the network. However, the ASP index becomes ineffective when a node is removed, as it can disconnect the network. To address this, Lü et al. ^[67] introduced the Relative Change of Average Shortest Path (RASP) centrality, which focuses on the change in the average shortest path in the network after a node is removed. RASP measures the node's importance in maintaining network connectivity by calculating the relative change in the average shortest path.

To address the high time complexity of betweenness centrality, Song et al. ^[68] introduced load centrality (LC), which measures the change in network paths after node removal to assess the node's impact on connectivity. Ventresca et al. ^[69] developed the CNDP algorithm, which determines node connectivity and capacity based on path length, the number of paths, and network scale. Many real-world networks display hierarchical and modular structures. Zhang et al. ^[70] proposed a multi-scale node importance metric using a kernel function, where bandwidth determines the range of interactions. Small bandwidth captures short-range interactions, while large bandwidth highlights long-range interactions, offering insights into node influence across different scales during dynamic processes. In power systems, Yang et al. ^[71] introduced the Electric Observability Capability Index (EOCI) and the Electrical Dynamic Characteristics Index (EkI) to identify critical nodes influencing power system observability and controllability. Kianian et al. ^[72] used degrees and independent influence paths to approximate influence propagation, reducing computational cost by pruning insignificant nodes. Xiao et al. ^[73] applied Local Average Shortest Path with extended Neighborhood concept (LASPN) theory to identify critical nodes, combining local average shortest paths and extended neighborhoods for efficient processing in large-scale networks.

4.2. Closeness centrality

To address the interference of special values in paths, Freeman et al. ^[74] introduced Closeness Centrality by calculating the average distance of a node to all other nodes in the network. The smaller the average shortest distance $$ d_i $$ from node $$ v_i $$ to other nodes in the network, the closer node $$ v_i $$ is to the other nodes in the network. The reciprocal of $$ d_i $$ is defined as the closeness centrality of node $$ v_i $$:

In a connected network, the smaller the average distance between a node and all other nodes in the network, the larger the closeness centrality of that node. This can be understood as determining the importance of a node by the average transmission time of information in the network. To improve closeness centrality for network efficiency, Latora et al. ^[75] extended betweenness centrality to disconnected networks and proposed the EFF index. However, this approach requires calculating the distances between all node pairs, which is computationally expensive for large networks. To reduce this complexity, Salavati et al. ^[76] applied the Louvain community detection algorithm to identify network communities. By maximizing modularity, they extracted community structures and selected key nodes using betweenness centrality. They also introduced a method to identify gateway nodes linking communities and reduced computation by focusing on a subset of special nodes. Okamoto et al. ^[77] proposed the RAND algorithm to estimate average node distances efficiently. It selects top candidate nodes based on these estimates and ranks them precisely, balancing computational efficiency with accuracy. Sheng et al. ^[78] introduced the global and local structure(GLS) method, which calculates the influence of nodes by considering common neighbors and structural characteristics. This method combines local and global structural influence based on their information exchange capabilities.

4.3. Random walk

Currently, methods for identifying key nodes based on heuristic centrality measures are used only for specific network topologies or unique dynamic models for analysis and demonstration. Iannelli et al. ^[79] proposed a method based on the random walk effective distance $$ D^{RW}_{ij}(\lambda) $$ between pairs of nodes, using the adjacency matrix $$ A_{ij} $$ and the diffusion dynamic parameter $$ \lambda $$ to quantify the influence of nodes during the network diffusion process. The ViralRank score for node $$ v_i $$ is defined as the average random walk effective distance between all source nodes and target nodes in the network:

where $$ i \neq j $$, $$ D_{ii}^{RW} = 0 $$, $$ P^{(j)}, I^{(j)} \in R^{(N-1)\times (N-1)} $$ are partition matrices of the Markov matrix, $$ (P)_{ij} = A_{ij} / \sum_{k} A_{ik} $$, and the identity matrix $$ (I)_{ij} = \theta_{ij} $$ are obtained by removing the $$ i $$-th row and $$ j $$-th column, respectively. $$ p^{(j)} $$ is the $$ j $$-th row of $$ P $$ after removing the $$ v_j $$-th element. A node's smaller average effective distance means a higher ViralRank score, indicating central nodes cause larger outbreaks than peripheral ones as "seed" nodes. Dong et al. ^[80] proposed the Semi-Local Centrality (SLC) method, integrating topological features with dynamic processes. SLC starts a random walk from node $$ v_i $$, adding influential neighboring nodes to the path. The SLC of a node is defined by the length of the random walk path formed by its influential neighbors, improving the accuracy. To address the limitations of current centrality measures and their incompatibility with distributed environments, Kermarrec et al. ^[81] proposed second-order centrality, which calculates the standard deviation of return times recorded by each node during a random walk. This approach supports distributed computation and provides a local value for each node, reflecting its relative importance. It allows unbiased identification of key nodes through random walk, enabling a global understanding of network topology.

5.1. Network control

Existing research has highlighted the importance of specific nodes in regulating network dynamics and functionality. Li et al. ^[82] employed the Watts-Strogatz propagation model to explore spreading mechanisms in small-world networks. Their analysis of delayed control propagation with linear and nonlinear feedback controllers demonstrated how network parameters influence stability and oscillatory behavior. Ghosh et al. ^[83] emphasized the critical role of dynamic synchronization in maintaining global network coherence. Their findings showed that proper weighting procedures significantly enhance synchronization in static complex networks, with key nodes exerting disproportionate influence on system stability. D'Souza et al. ^[84] proposed a framework for network control that integrates node dynamics and macroscopic network properties, refining control strategies through higher-order interactions. Liu et al. ^[85] developed analytical tools to assess the controllability of arbitrary directed networks, establishing that the number of driver nodes required for full control is primarily dictated by the network's degree distribution. Their work uncovered a fundamental relationship between network structure and control feasibility: sparse, heterogeneous networks are the most difficult to control, whereas dense, homogeneous networks require fewer driver nodes. The controllability of a system governed by linear time-invariant dynamics:

where $$ x(t)\in R^{N} $$ represents the system state of $$ N $$ nodes at time $$ t $$, $$ A\in R^{N\times N} $$ is the adjacency matrix encoding interaction dynamics, and $$ B\in R^{N\times M} $$ identifies the driver nodes influenced by control inputs $$ u(t)\in R^{M} $$. The system is controllable if and only if the controllability matrix, $$ C = (B, AB, \dots, A^{n-1}B) \in \mathbb{R}^{N \times NM} $$. The system is controllable if and only if $$ Rank(C)=N $$, meaning it can transition from any initial state to any final state within a finite time. Furthermore, the minimum number of driver nodes $$ N_D $$ required for full control can be estimated using the structural controllability framework as $$ N_D = \max\{1, N- \operatorname{rank}(A)\}. $$ To address the problem of identifying an optimal driver node set for minimizing control cost, recent studies have proposed formulations such as

which seeks the control input $$ u(t) $$ with the smallest energy expenditure required to guide the system toward the desired state. To address the minimal-cost control problem, Ding et al. ^[86] proposed the Projection Gradient Method Extension (R-PGME) algorithm, which leverages Monte Carlo simulations and identifies a minimal set of key nodes for effective control. Lu et al. ^[87] applied the Warshall algorithm to Boolean control networks (BCNs), determining the smallest set of nodes required for stability in large-scale systems. Expanding on these approaches, Zhu et al. ^[88] integrated structural information and developed a low-complexity structural controller for large-scale Boolean networks, efficiently identifying the minimal feedback node set for robust control.

The eigenvalues of the Laplacian matrix play a critical role in pinning control and network controllability, directly influencing the selection of optimal driver nodes for synchronizing large-scale networks. Yu et al. ^[89] proposed a distributed adaptive strategy that adjusts coupling weights based on local node dynamics to achieve synchronization, later extending their work to establish synchronization criteria for various network topologies, including strongly and weakly connected graphs ^[90]. Ding et al. ^[91] demonstrated that denser and more homogeneous networks exhibit superior controllability, with controlled nodes typically having lower in-degree than the network average. Amani et al. ^[92] introduced the Eigenvalue Sensitivity Index (ESI), which ranks nodes using extremal Laplacian eigenvectors to estimate their importance in pinning control. They further developed a computationally efficient method based on sensitivity analysis of the Laplacian matrix to identify near-optimal driver nodes ^[93]. Liu et al. ^[94] evaluated pinning effectiveness via the smallest eigenvalue of the grounded Laplacian, linking controllability to network structure. Several optimization strategies have been investigated. Wang et al. ^[95] achieved full network control through structural perturbations using a single driver node. Bof et al. ^[96] showed that energy-efficient control depends on the left and right Perron eigenvectors of the network matrix. Zhou et al. ^[97] proposed the ControlRank metric, validating degree-based rankings in scale-free networks. Liu et al. ^[98] refined driver node selection by prioritizing nodes with the largest eigenvector components corresponding to the dominant Laplacian eigenvalue. Bomela et al. ^[99] applied the Moore–Penrose pseudoinverse of the Laplacian to identify Most Influential Nodes (MIN) in oscillatory networks. Recent studies have emphasized minimal intervention strategies. Jiang et al. ^[100] showed that large-scale synchronization can often be achieved with minimal control effort or higher-order interactions. Sun et al. ^[101] analyzed optimal control in reaction-diffusion networks, revealing the influence of topology and diffusion parameters on epidemic dynamics. Collectively, these works highlight the strong interdependence between spectral properties, network structure, and dynamic processes, underscoring the value of targeted interventions for achieving efficient and robust network control.

The contribution of network edges, including loops, to overall network dynamics is fundamentally governed by the eigenvector corresponding to the smallest nonzero eigenvalue of the Laplacian matrix, known as the Fiedler vector. The cumulative effect of all edges is encapsulated in the network's algebraic connectivity, which dictates synchronization and diffusion properties. Zhang et al. ^[102] analyzed the impact of adding feedback edges in directed acyclic graphs (DAGs) on consensus behavior in multi-agent systems. They identified disruptive feedback edges that degrade convergence speed and formulated a necessary and sufficient condition for their identification. Mo et al. ^[103] extended this by introducing a topology-based optimization framework for directed graphs, enabling the systematic selection of edges that enhance convergence. They demonstrated that in strongly connected weighted digraphs, the second smallest Laplacian eigenvalue remains real and established conditions for edge selection that improve consensus dynamics. Jiang et al. ^[104] proposed a method to assess the importance of loops in complex networks, ranking key loops based on their influence on the Fiedler value. Similarly, Cao et al. ^[105] developed a theoretical framework for synchronization acceleration by optimizing directed edge placement and weights. They derived a necessary and sufficient condition for selecting edges that enhance convergence, allowing efficient identification through Laplacian eigenspace computations. Zhang et al. ^[106] reaffirmed the existence of disruptive feedback edges in DAGs and explicitly constructed conditions for their identification. Gao et al. ^[107] further examined how weighted edge additions influence algebraic connectivity in directed graphs, proving that changes in Laplacian eigenvalues are localized within subgraphs containing the added edges. Their findings underscore the dependence of algebraic connectivity on edge weight, range, and distribution along network paths. These studies further reveal how interventions of network edges and cycles control dynamic behavior, highlighting the role of spectral properties in optimizing synchronization and controllability.

5.2. Maximization of connected component

In a network, there exists a set of important nodes that influence the network's robustness and connectivity. By removing these nodes or attacking the network, we can identify a critical set of nodes. Deleting this set of nodes can minimize or maximize the connectivity components (such as the largest connected component or node pair connectivity) in the remaining network, which is known as the Critical Nodes Deletion Problem. Aringhieri et al. ^[108] designed a general framework to address several classic critical node problems (CNPs), specifically: (1) Pairwise connectivity: Minimize the number of connected node pairs in the remaining network by deleting up to $$ K $$ nodes, ensuring the pairwise connectivity is reduced to a threshold $$ P $$. (2) Largest connected component: Minimize the size of the largest connected component in the remaining network by deleting up to $$ K $$ nodes, ensuring its size cannot exceed a threshold $$ L $$. (3) Number of connected components: Maximize the number of connected components in the remaining network by deleting the fewest nodes possible, ensuring it meets or exceeds a threshold $$ N $$. It discusses greedy algorithm design rules for these problems and proposes general algorithms for solving various CNPs, providing solutions for subsequent derivations and improvements of CNP models. Alozie et al. ^[109] focused on optimizing distance-based connectivity metrics by removing a subset of nodes. They aimed to minimize two specific metrics: (1) the number of node pairs connected by the longest path, and (2) the Harary index or efficiency of the graph. To achieve this, they proposed a general mixed-integer programming formulation and a separation algorithm based on breadth-first search (BFS) tree generation, designed to solve the constraint inequalities.

Thulasiraman et al. ^[110] evaluated node value using cut vertices and edges for network diagnostics and security, employing link testing and node connection statistics. In protein interaction networks, Boginski et al. ^[111] aimed to identify key nodes by solving the Cardinally Constrained-CNDP (CC-CNDP), defined as minimizing the set of deleted nodes $$ R $$ such that the largest connected component in the remaining subgraph $$ G(V \setminus A) $$ of the network cannot exceed $$ L $$, as follows:

where $$ e_{ij} $$ represents the edge between nodes $$ v_i $$ and $$ v_j $$, (1) ensures that there is an edge between nodes $$ v_i $$ and $$ v_j $$, meaning that both nodes are in the network, (2-4) constrain the connectivity of the node set $$ (i, j, k) $$ to be minimal, and (5) constrains the size of the largest connected component in the network. This CNDP problem is transformed into an integer programming optimization problem to identify critical network disruptions and target proteins for drug neutralization. In self-organizing networks, Karygiannis et al. ^[112] defined critical nodes as breakpoints under failures or attacks. They used graph theory's vertex and edge cut principles to reveal network vulnerability through subgraph generation and involved solving optimization problems where their removal satisfies specific constraints.

Furthermore, Arulselvan et al. ^[113] proposed a risk management-based method to detect a set of nodes that, when deleted, cause the connectivity index of the resulting subgraph to fall below a threshold. This problem is defined as the cardinality-constrained critical node problem (CC-CNP) and modeled as an integer linear programming (ILP) problem, which is solved using a heuristic genetic algorithm. In social networks, there exists a set of $$ k $$ mediator nodes aimed at maximizing the probability of information activation from a source node to a target node. Li et al. ^[114] defined this problem as the k-Mediators problem. Based on the independent cascade propagation model, they optimized information propagation by considering path probability effects and structural connectivity, using the product of edge weights to more accurately simulate the information spread process. They proposed a three-step greedy method to iteratively construct the best propagation tree (BPT), connecting all source and target nodes and optimizing the propagation paths to maximize activation probabilities. Ventresca et al. ^[115] developed a multi-objective critical node detection algorithm. It removes nodes to maximize the connected components in the remaining network while minimizing the size variance among these components. Veremyev et al. ^[116] introduced two critical node deletion problems: (1) deleting $$ K $$ nodes to minimize the remaining connected node pairs; (2) deleting the fewest nodes to ensure the largest component has no more than $$ L $$ nodes. They reduced the solving time through constraints, making it possible to tackle large-scale network optimization issues. Ren et al. ^[117] proposed a reverse greedy strategy to identify nodes crucial for maintaining connectivity. Starting from an empty network, it adds nodes with the least impact on the largest component, ranking by addition order, with the last added node deemed most critical.

To address the high computational costs of greedy algorithms on large networks. Wang et al. ^[118] developed a community-based greedy algorithm using node edge weights for propagation speed, incorporating information diffusion for community detection and dynamic programming to identify influential nodes. Lam et al. ^[119] used simulations in the NetLogo multi-agent environment to identify critical infrastructure components, assessing node failure impacts via attack scenarios and the giant component metric. Ventresca et al. ^[120] proposed a depth-first search method with $$ O(|V| + |E|) $$ complexity, integrated into greedy algorithms for quick key node identification in large networks, enabling efficient CNDP objective function solving. Tang et al. ^[121] introduced a Discrete Shuffling Frog Leaping Algorithm based on virtual frog population topology, featuring novel encoding, evolution rules, and a local degree-based replacement strategy for efficiency.

5.3. Minimization of pair connectivity

To minimize pairwise connectivity by removing a fixed number of nodes, Di Summa et al. ^[122] proposed an ILP model with non-polynomial constraints, as follows:

where constraint (1) limits the number of deletions to $$ K $$, while (2) ensures that removing an edge implies removing both its endpoints. Constraints (3)–(5) enforce connectivity dependencies, ensuring that if $$ \{i, j\} $$ is disconnected in the remaining graph, then the node pairs $$ (i, k) $$ and $$ (k, j) $$ cannot be connected.

In small-scale networks, heuristic algorithms are commonly used to identify critical nodes that impact connectivity. Arulselvan et al. ^[123] employed a combinatorial heuristic integrating integer programming to efficiently minimize pairwise connectivity by selectively removing nodes. Similarly, Shen et al. ^[124] introduced an adaptive algorithm that identifies critical nodes without requiring full recalculations after topological changes, enhancing efficiency and response speed. Ventresca et al. ^[125] developed an approximation algorithm for undirected, unweighted graphs, combining ILP with randomized rounding. By handling vertex and triangle inequality constraints separately, their method effectively reduces subgraph connectivity while capping the number of deleted nodes at $$ k $$, with solution quality bounded by a constant factor. Dinh et al. ^[126] assessed network vulnerability under dynamic conditions using expected pairwise connectivity (EPC) as a metric, transforming the problem into a stochastic optimization framework based on probabilistic graphs. Sarker et al. ^[127] proposed an enumeration algorithm that accounts for connection costs and node weights, achieving high time efficiency and controlled complexity. Their approach, applied to river drainage networks, confirms power-law fragmentation behavior following the removal of critical nodes.

To address the complexity and accuracy balance in identifying critical nodes in large-scale networks, Pullan et al. ^[128] proposed a Greedy Randomized Adaptive Search Procedure (GRASP) with Path Relinking. The algorithm introduces an evolutionary path relinking mechanism during the path search process. It was shown that the GRASP with Path Relinking is more efficient than algorithms such as neighborhood search and simulated annealing in solving the CNDP. Addis et al. ^[129] proposed a "hybrid" heuristic algorithm based on the basic greedy algorithm. By combining two greedy rules, "node addition and deletion, " the algorithm addresses the CNDP problem of removing K nodes to minimize the residual network connectivity. The algorithm alternates between node addition and deletion operations in the feasible solution space, effectively avoiding local optimal solutions. Chen et al. ^[130] focused on the critical node fragmentation problem in weighted networks. They proposed a non-convex mixed-integer quadratic programming (MIQP) model for undirected weighted networks. A greedy algorithm is employed to approximate the optimal solution, and the algorithm iteratively selects K critical nodes (Critical Node Set, CNS) that cause the most significant decrease in network pairwise connectivity, identifying the critical node combination that maximizes network performance.

To mitigate the high computational complexity of the critical node deletion problem, Ventresca et al. ^[131] employed a population-based incremental learning algorithm combined with combinatorial simulated annealing to detect critical nodes, leveraging depth-first search to minimize pairwise connectivity. For dense networks where pairwise connectivity computations remain $$ O(n^{2}) $$, Shen et al. ^[132] developed a hybrid iterative linear programming rounding (HILPR) algorithm, which transforms the problem into ILP, improving solving efficiency through local search and constraint pruning. Ventresca et al. ^[133] proposed a region-growing dual-criterion method using LP relaxation to iteratively expand a fixed-radius ball, providing a logarithmic approximation for optimal node removal. Addressing weighted social networks, Yin et al. ^[134] introduced the Mixed Strength Decomposition (MSD) method, dynamically setting thresholds for node removal based on connection weights, improving the precision of critical node identification. These advancements enhance computational efficiency in solving CNDP, enabling more effective identification of critical nodes in large-scale networks.

Recent studies have focused on optimizing critical node detection and network robustness under adversarial conditions. Zhang et al. ^[135] formulated the Critical Node Detection problem in interdependent networks as a Bi-objective Optimization Problem (BICND) and designed a method integrating single-layer and multi-layer network transfer. This approach reduced algorithmic complexity while enhancing accuracy in identifying critical nodes. Fortz et al. ^[136] proposed a compact integer programming formulation for the node attack optimization problem using pseudo-components within a two-level model, addressing performance limitations of prior iterative methods. Jiang et al. ^[137] introduced the EBC method, leveraging loop structures to assess network robustness against targeted attacks and precisely identify edges critical to resilience. Kouam et al. ^[138] simulated adversarial behavior to evaluate node influence, modeling attack progression toward the target. Zhou et al. ^[139] examined the NP-hard nature of the protection node problem and optimized key node selection via an influence redundancy mechanism. By minimizing the adjacency matrix's spectral radius after key node removal, they demonstrated submodular properties in the objective function and achieved an approximation ratio of $$ O(N\log N) $$. These advances enhance network resilience by refining critical node and edge, offering efficient solutions for targeted attacks. The multi-area power system can be described using power grid models and associated control models. In contrast, the networked $$ T-S $$ fuzzy system is modeled using $$ T-S $$ fuzzy models that consist of multiple fuzzy rules. The research on "Critical-metrics-based attack strategy and resilient $$ H_\infty $$ state estimator design for multi-area power systems" presents a critical-metrics-based attack strategy. From the attacker's perspective, this strategy targets the critical information packets in the key areas of the power system, thereby amplifying the impact of the attack on system performance. Correspondingly, from the defender's perspective, a resilient state estimator is designed to alleviate the adverse effects of potential critical-metrics-based attacks.

5.4. Minimum spanning tree

Chen et al. ^[140] evaluated the relative importance of two sets of nodes by comparing the number of spanning trees in the remaining network after node deletion. The fewer the number of spanning trees in the corresponding network after removing a set of nodes and their associated edges, the more important that set of nodes is considered to be. This method is simple to compute and provides a more accurate reflection of node importance. When the network size is large, the algorithm complexity of solving the problem increases. To improve the solving efficiency, the objective function is decomposed into multiple subproblems. Di Summa et al. ^[141] studied the minimization of the number of connected node pairs in the remaining graph after node deletion, designing the network as a tree structure to extend the solution to the CNP subproblem. Hermelin et al. ^[142] discussed the Critical Node Cut (CNC) problem: given a graph $$ G $$ with $$ n $$ vertices, determine $$ k $$ nodes, and after their removal, the remaining graph has at most $$ x $$ connected node pairs. Using a parameterized method, they proved that the problem can be solved in polynomial time by preprocessing it into a subproblem with lower complexity.

Regarding the linear framework of the network traffic and connectivity constraint problem, Addis et al. ^[143] focused on the combinatorial problem of node deletion. They provided a dynamic programming recursive method for solving the tree decomposition problem based on graphs, which can solve the CNP problem in polynomial time on general and special graphs (split graphs, bipartite graphs, and the complements of bipartite graphs). Aringhieri et al. ^[144] proposed two metaheuristics based on iterative local search and variable neighborhood search frameworks to achieve maximum fragmentation of graphs. They designed two computationally efficient neighborhoods, evaluated different exploration strategies, and found that the improved strategy produced a large number of new best solutions. Using betweenness centrality, they were able to reduce the runtime without compromising the solution quality. Wang et al. ^[145] combined the advantages of the minimum spanning tree (MST) structure and the minimum connected dominating set (MCDS) properties, introducing edge weight normalization to calculate the connection strength between nodes. They defined the MCDS efficiency (SEW) and excluded non-critical endpoints, further distinguishing node importance.

6.1. Information entropy

Entropy-based measures quantify the uncertainty or diversity in information propagation and have been widely applied to assess node centrality. Nikolaev et al. ^[146] introduced entropy centrality, which evaluates a node's potential for dissemination via discrete Markov processes. Specifically, a node's entropy centrality is defined as

The term $$ p_{ij}^{(t)} + p_{ij'}^{(t)} $$ represents the probability that an object originates from node $$ v_i $$ and that during $$ t $$ time periods, the node itself is found to possess node $$ v_j $$. Higher entropy indicates a more uniform spread, implying greater unpredictability in the information's destination. Building on this foundation, Zareie et al. ^[147] incorporated Shannon entropy and Jensen–Shannon divergence to develop the Diversity Strength Ranking (DSR) and Extended DSR (EDSR) algorithms, which account for both neighbor dispersion and influence range.

Other studies have leveraged entropy in various contexts. Nitt et al. ^[148] proposed a degree centrality mapping entropy (ME) to identify critical nodes through local interactions. Similarly, Fu et al. ^[149] defined global node information entropy based on the $$ k $$-shell index. To address the issue in the VoteRank algorithm where all nodes are roughly assigned the same voting capacity and attenuation factor during voting, Guo et al. ^[150] addressed limitations in VoteRank by introducing the EnRenew algorithm, which integrates connection-based entropy and an attenuation factor to update nodes' propagation capabilities. In response to the susceptibility of road networks to cascading failures caused by traffic accidents or abnormal events, Xu et al. ^[151] applied entropy concepts in the Origin-Destination Entropy and Flow (ODEF) and Crossroad Ranking (CRRank) to evaluate node importance using vehicle trajectory data. Tulu et al. ^[152] further developed a Community-based Mediator (CbM) method that combines internal and external density entropy with node degree to identify critical mediators in large-scale networks.

Network entropy is typically used to characterize the amount of information encoded in a network structure. Based on the assumption that removing more important nodes may lead to greater structural changes, Ai et al. ^[153] defined node importance as the change in network entropy before and after its removal. Wu et al. ^[154] proposed $$ k $$-order entropy combined with betweenness centrality to capture global and local information through different order neighbor dependencies. Based on K-shell, the internal and external effects of neighbor subnet structure are defined as information entropy and cross-entropy ^[155], respectively, to identify the information disseminator. Li et al. ^[156] further extended this approach by incorporating mutual information to derive a centrality measure (EMI) that considers both direct and second-order neighbor effects, effectively quantifying redundant and complementary information flows. These entropy-based approaches offer a rigorous framework to evaluate node importance by measuring the uncertainty and diversity inherent.

6.2. Clustering coefficient

The clustering coefficient is a crucial factor in determining the local influence of nodes. Chen et al. ^[157] combined the number of node neighbors, the influence of neighbor nodes, and the clustering coefficient to propose the ClusterRank method for local node importance ranking, specifically defined as:

The local clustering coefficient $$ c(v_{i}) $$ of node $$ v_i $$ is defined as: $$ c(v_i)=R(v_i)/k(v_i)(k(v_i)-1) $$, where $$ R(v_i) $$ represents the number of triangles formed by node $$ v_i $$, and $$ \Gamma_{i} $$ denotes the neighbors of node $$ v_i $$. The term "+1" accounts for the degree contribution of the node itself to its neighboring nodes. When ranking nodes based on local centrality, traditional methods overlook the structural connections among neighbors. To address this, Gao et al. ^[158] proposed Local Structural Centrality (LSC), which integrates both the number of a node's neighbors and their topological interconnectivity. By incorporating the local clustering coefficient, LSC quantifies the extent to which a node's neighbors are interconnected, capturing structural nuances often ignored in purely degree-based metric. The local clustering coefficient reflects the density of connections among a node's immediate neighbors, offering insights into its influence within the network. Nodes with similar local centrality values but higher clustering coefficients tend to exhibit stronger propagation capabilities, as their tightly connected neighborhoods facilitate more effective information diffusion. In addition, the traditional K-truss method, which decomposes networks based on edge clustering, may be affected by "false cores" when clustering characteristics are not accurately captured. Yang et al. ^[159] proposed an improved K-truss approach that incorporates both edge diffusivity and edge clustering coefficients, thus providing a balanced metric for identifying influential nodes. Complementarily, Zareie et al. ^[160] developed the ECRM method, which posits that nodes with lower correlation to their neighbors are more likely to be influential, as they can more effectively disseminate information to the network periphery.

To overcome the limitations of undirected graphs in representing conditional independence, Dablander et al. ^[161] developed a causal framework based on DAGs. Assuming the Markov condition holds, they introduced the concept of "faithfulness" to ensure that the DAG accurately captures variable independencies. They further quantified causal impacts using Average Causal Effect (ACE) and Kullback-Leibler (KL) divergence. Their findings indicate that eigenvector centrality outperforms traditional metrics in predicting the causal influence of nodes within such networks. Liu et al. ^[162] integrated latent group information in power systems by developing the Group-Driven Framework for Identifying Critical Nodes (GDF-ICN) algorithm. This framework combines the structural and operational states of power systems with node group affiliations, iteratively optimizing group partitions around critical nodes. A fuzzy closeness metric is incorporated to enhance the description of group structure, while leveraging clustering effects to bolster the robustness of critical node identification. Wang et al. ^[163] proposed an influential node evaluation algorithm grounded in information entropy theory. By defining metrics based on the number of triangles and edge weights, they introduced the concept of edge entropy weights - capturing differences in edge weights and their influence on neighboring nodes. This approach integrates k-core metrics to characterize local node influence, with higher entropy values indicating greater complexity and overall influence within the network. Zhang et al. ^[164] presented a novel method focused on maximizing the range of influence. Their approach constructs an information transmission probability matrix, which quantifies the probability of information transfer between arbitrary node pairs.

6.3. Machine learning

Machine learning offers a powerful framework for identifying influential nodes by reframing the problem as a regression task. These methods leverage supervised learning algorithms trained on node labels derived from epidemic model simulations and traditional centrality measures, capturing complex relationships between network structure and propagation potential. Zhao et al. ^[165] employed information infection vectors to encode topological characteristics and infection dynamics across diverse propagation scenarios. Using node labels obtained from susceptible-infected-recovered (SIR) model simulations, they trained classifiers and regressors - including Naïve Bayes, decision trees, random forests, Support Vector Machines (SVM), k-Nearest Neighbors (KNN), logistic regression, and Multilayer Perceptron (MLP) - to predict node importance. Yang et al. ^[166] introduced a network-aware local centrality index (NLC) that integrates topology with node embeddings. Applying DeepWalk to project network structures into a low-dimensional space, they incorporated third-order neighborhood information to refine influence estimation. Rezaei et al. ^[167] further advanced this paradigm by engineering collective node features - spanning connectivity, degree, and coreness measures - and training an SVR model with an RBF kernel, demonstrating the efficacy of tailored feature representations in predicting node influence. However, existing models face limitations in feature representation and scalability. The development of deep learning and graph neural network approaches provides a powerful new framework for analyzing node attributes and quantifying influence.

Graph conventional network: Zhao et al. ^[168] pioneered the deep learning framework InfGCN based on graph convolutional networks (GCN). InfGCN constructs node structural features - including degree, closeness, betweenness, and clustering coefficient - and builds a fixed neighbor network via BFS. By training with actual infection rate vectors from SIR model simulations, InfGCN minimizes the error between predicted and actual infection rates to accurately estimate node influence. Similarly, Kumar et al. ^[169] adopted the Stru2vec node embedding algorithm ^[170] along with a message-passing neural network (MPNN) to process node embeddings and SIR-based influence vectors, identifying the Top-$$ k $$ influential nodes. Zhang et al. ^[171] combined convolutional neural networks (CNN) with Graph Neural Networks (GNNs) in their CGNN algorithm, which simplifies feature matrices and focuses on first- and second-order neighbors to label nodes via the SIR model and optimize a loss function for precise identification of critical nodes. Liu et al. ^[172] developed a ranking method based on self-supervised learning and graph convolutional models, leveraging both node features and network structural information.

Graph embeddings: Wei et al. ^[173] focused on reducing computational complexity. They selected candidate nodes based on shell connections and topological features, then used deep learning to generate low-dimensional vectors for calculating propagation dependency. Keikha et al. ^[174] proposed Deep learning for Information Maximization(DeepIM) (an algorithm using deep learning techniques for influence maximization problem), which extracts global and local structural features via CARE, constructs custom paths, and employs Word2vec to learn node feature vectors for measuring user relevance. Bouyer et al. ^[175] presented Embedding Technique for Influence Maximization (ETIM), combining shell decomposition, graph embedding, and local structure features to decrease computation. Wu et al. ^[176] constructed node features using rule-equivalent similarity and Graph Convolutional Networks. Ahmad et al. ^[177] proposed frameworks (LCNN) that merge CNNs with local node representations and multi-scale metrics. Rashid et al. ^[178] introduced the GN model, integrating deep learning and probabilistic properties via Graph Convolutional Networks to detect overlapping communities and key nodes. Xiong et al. ^[179] proposed the AGNN algorithm, fusing autoencoders with GNNs to generate topological feature embeddings through GCN and optimizing the ranking prediction model using listMLE. Yu et al. ^[180] developed methods region-based CNNs (RCNN) that integrate GCNs and CNN-based adjacency features for effective critical node detection.

Graph attention network: Most existing node importance assessments in knowledge graphs fail to fully utilize available information and cannot capture node relationships and attribute features. To address this, Park et al. ^[181] developed graph estimation node importance (GENI) that uses predicate-aware attention mechanisms and flexible centrality adjustments to aggregate node and neighbor information across multiple GNN layers. It updates node embeddings via an aggregation function with a nonlinear transformation and maps these to importance scores using a scoring neural network. GENI also incorporates node in-degree centrality to adjust importance estimates. Define a GNN with $$ L $$ layers of networks, where the $$ l $$-th aggregates information from the $$ l-1 $$ th layer as follows,

where $$ \vec{h}_i^{l-1}$$ is the $$ v_i $$ represents the information aggregation of the $$ (l-1) $$ th layer, each neighbor node $$ N(i) $$ of node $$ v_i $$ denotes the set of its neighbors (each initialized with a weight $$ w_{i, j}^{l} $$). The aggregation function and nonlinear transformation function share parameters across all nodes. At each layer, node scores are updated through a weighted combination of their own value and neighbors' values, with attention mechanisms dynamically adjusting connection influence. Initial node scores come from feature embeddings processed through a neural scoring network. GENI also incorporates a centralization score based on node in-degree, refined through scaling and offset adjustments. Finally, a nonlinear activation function integrates this score with learned representations. Furthermore, Park et al. ^[182] designed MultiImport, an end-to-end latent variable model to infer node importance from multiple sparse and possibly overlapping input signals. MultiImport uses edge-aware attention aggregation and node centralization adjustment within a GNN framework to learn robust node representations. It models the knowledge graph structure and uses clustering to group nodes with similar functional signals. Munikoti et al. ^[183] introduced Inductive Learner for Graph Robustness (ILGR), a scalable GNN-based framework that approximates node and link importance through attention-driven embedding. ILGR encodes local structure by aggregating neighborhood information, with an attention mechanism assigning adaptive weights based on structural roles. Ge et al. ^[184] proposed Multi-perspective attention mechanism Fusion Algorithm to Node Importance Estimation (MFA-NIE), integrating structural, relational, and attribute features with an enhanced attention mechanism for feature extraction, and adjusts node importance using Technique for Order Preference by Similarity to Ideal Solution (TOPSIS) centrality. Chen et al. ^[185] developed a hierarchical graph-enhanced variational autoencoder that reconstructs neighborhood representations to learn social influence patterns, using hierarchical graph attention networks to capture influential neighborhoods and mitigate data sparsity. Liu et al. ^[186] introduced Node Importance Estimation-Graph Attention Network(NIE-GAT) for inter-domain routing networks, mapping static node features to dynamic cascading failure impacts through graph attention networks. Additionally, Kou et al. ^[187] refined GCN-based approaches by framing node influence prediction as a regression task and using a multi-head attention mechanism to integrate neighbor importance, with the Independent Cascade (IC) model providing simulation-based ground truth for optimization.

Graph contrast learning: Recent advancements in contrastive learning have improved node importance estimation by integrating multiview representations and attention mechanisms. Liu et al. ^[188] addressed the limitations of single-graph models by introducing the Multiview Contrastive Representation Learning (MCRL) framework, which employs dual graph encoders and contrastive learning to derive multi-perspective node representations. This approach enhances the estimation of node importance by comparing embeddings generated through GCN and graph attention mechanisms (GAT). By incorporating a positive-negative sampling strategy, MCRL identifies nodes that maintain both high similarity and distinctiveness across multiple structural views - key indicators of importance. Building on this concept, Zhang et al. ^[189] developed the Label-Contrastive Pretraining (LICAP) model, which employs hierarchical sampling to prioritize top-ranked nodes. LICAP utilizes a Predicate-Aware Graph Attention Network (PreGAT) to refine node embeddings, ensuring robust differentiation between influential and peripheral nodes. Meanwhile, Shu et al. ^[190] proposed node importance evaluation in heterogeneous network based on attention mechanism and graph contrastive learning method (AGCL), a contrastive learning framework for heterogeneous networks that leverages attention mechanisms to quantify both local and global node importance. By extracting structural features through contrastive learning and computing importance weights via attention mechanisms, AGCL offers a comprehensive approach to evaluating node influence in complex networks.

Graph neural networks: Huang et al. ^[191] introduced HIN Importance Value Estimation Network (HIVEN), a GNN-based framework designed for heterogeneous information networks (HINs). By integrating a heterogeneous information aggregator and a meta-path-based mechanism, HIVEN effectively captures the structural and relational intricacies of HINs, improving both accuracy and efficiency in node ranking. Building on structural knowledge integration, Chen et al. ^[192] developed SKES (Deep Structural Knowledge Exploitation and Synergy), which incorporates node centrality and similarity metrics to learn high-dimensional feature distributions. SKES refines importance predictions using optimal transport theory, enabling precise characterization of node significance within heterogeneous graphs. Similarly, Lin et al. ^[193] leveraged Large Language Models (LLMs) in the LLMs Empowered Node Importance Estimation (LENIE) framework to enhance semantic representations in knowledge graphs. By employing a clustering-based triplet sampling strategy and node-specific adaptive prompts, LENIE enriches node embeddings, thereby improving the initialization of node importance estimation models. Higher-order network structures have also been incorporated into learning-based ranking methods. Zhao et al. ^[194] proposed HONNMA, a high-order neural network framework that employs motif attention to capture complex topological dependencies. This model encodes interactions through a weighted motif adjacency matrix and refines node embeddings using a skip-connected architecture, allowing for more robust node importance estimation. Addressing the Critical Node Detection Problem, Michos et al. ^[195] applied Hopfield Neural Networks (HNN) to optimize network resilience. By reformulating as an energy minimization task, their approach identifies critical nodes by converging toward stable network states with minimal energy.

6.4. Reinforcement learning

Reinforcement learning influences key node selection by using rewards and penalties to guide the process, treating the impact of nodes - whether on overall network performance or individual propagation capability - as the value incentive. In this framework, the objective is to identify a set of important nodes by either maximizing or minimizing a value-based objective function. To tackle high time complexity in critical node identification, Fan et al. ^[196] proposed the FInding key players in complex Networks through DEep Reinforcement learning (FINDER) framework. It minimizes the accumulated normalized connectivity (ANC) through a node deletion strategy. The ANC is defined as:

where $$ c(v_{k}) $$ is the normalized removal cost of node $$ v_{k} $$, and $$ \sigma $$ measures network connectivity. This optimization process is modeled as a Markov Decision Process (MDP), defined by the following components: state space $$ \mathcal{S} $$ represents the residual graph $$ \mathscr{G}' $$ after a sequence of node removals, action space $$ \mathcal{A} $$ denotes the selection of a node $$ v\in V(\mathscr{G}') $$ for removal at each step, and reward function $$ r:\mathcal{S}\times \mathcal{A} $$ is the reduction in ANC resulting from removing node $$ v $$, incentivizing actions that lead to rapid network fragmentation. A strategy for selecting the next node to delete, updated iteratively via reinforcement learning algorithms as policy $$ \pi(a|s) $$. The iterative process involves evaluating candidate actions based on their expected rewards, selecting the node that maximizes the reward signal, and updating model parameters using a greedy or approximate policy improvement strategy. To further reduce the computational complexity of heuristic algorithm-based node deletion, Tan et al. ^[197] proposed a feature-sensitive graph attention network. This method represents nodes by their features and, combined with an adversarial double-depth network, constructs a flexible end-to-end framework for generalizing critical node identification across different scales.

To address information diffusion features in node importance analysis, several studies have integrated reinforcement learning with graph-based methods. Jaques et al. ^[198] used a multi-agent reinforcement learning framework with counterfactual reasoning and measures such as KL divergence to assess the impact of alternative actions on other agents, identifying influential nodes. Chen et al. ^[199] proposed DeepELE, combining graph embeddings with reinforcement learning in a susceptible-infected-susceptible (SIS) model. Each node is assigned a diffusion weight, and a state–action value function evaluates the network-wide infection impact after node removal, selecting key nodes by minimizing an objective function. Li et al. ^[200] introduced Deep learnIng-baSed influenCe maximization (DISCO), combining network embedding with deep reinforcement learning for various node-related problems. Chen et al. ^[201] developed ToupleGDD, an end-to-end deep reinforcement learning framework coupling three graph neural networks with a double deep Q-network for parameter learning, addressing IM while overcoming limitations such as narrow IM formulations and low scalability. Ling et al. ^[202] introduced DeepIM, generating latent representations of seed sets in a data-driven manner to capture diverse information diffusion patterns, and designing a novel objective function for optimal seed sets under flexible node centrality constraints. Li et al. ^[203] presented deeP reInforcement leArning-based iNfluence maximization (PIANO), merging deep reinforcement learning with network embedding to estimate node influence, providing a pre-trained model pool for direct application. Uthayasuriyan et al. ^[204] introduced Differential Evolution-Reinforcement Learning (DERL), integrating differential evolution with Deep Q Network (DQN)-based reinforcement learning, and Li et al. ^[205] proposed AdaRisk, a risk-adaptive deep reinforcement learning framework for detecting fragile nodes in uncertain graphs. Xu et al. ^[206] developed HEDRL-IM, reformulating IM in hypergraphs as a network weight optimization task solved via deep Q-networks, integrating evolutionary algorithms and propagation simulation. Zhu et al. ^[207] proposed BiGDN, employing bidirectional neighborhood aggregation and integrating deep reinforcement learning with multi-head attention for robust node representations. Ahmad et al. ^[208] developed CoreQ, using K-core decomposition and Q-learning to identify candidate seed nodes.

7.1. Gravity formula

The law of universal gravitation has been innovatively applied in network science. By defining the gravitational constant multiplied by the product of the masses of two nodes divided by the square of the distance between the nodes, the centrality and statistical indicators of nodes are considered as "mass", and the shortest distance between nodes is used as the distance, thus constructing a new framework for measuring node importance. Ma et al. ^[209] combined the K-shell index of nodes and the shortest path between nodes to identify important nodes in the network through the gravitational calculation formula, defining the importance of node $$ v_i $$ as:

where $$ ks(i) $$ and $$ ks(j) $$ denote the $$ k $$-shell values of nodes $$ v_i $$ and $$ v_j $$, $$ d_{ij} $$ is the shortest path between them, and $$ \Psi $$ is the set of neighbors within a radius $$ r $$ of node $$ v_i $$. In parallel, Maji et al. ^[210] addressed limitations stemming from empirically set free parameters in improved $$ k $$-shell decomposition algorithms by considering the influence of different levels of neighbors, thereby enhancing the adaptability, efficiency, and accuracy of the model.

In addition, Li et al. ^[211] proposed the Local Gravity Model (LGM), which extends the basic gravity model to include neighborhood information; nodes surrounded by neighbors with high $$ k $$-shell indices are considered closer to the network's center. Li et al. ^[212] further modified the model by replacing the $$ k $$-shell metric with the degree of neighboring nodes. Recognizing that a degree-based gravity model captures only local information. Liu et al. ^[213] introduced the eigenvector exponent of the adjacency matrix into the gravitational formula, proposing the Generalized Gravity Model (GMM) that incorporates both local and global network characteristics. Yang et al. ^[214] utilized $$ k $$-shell values to define an attraction coefficient between nodes, taking into account critical positional attributes of a node's neighborhood. Li et al. ^[215] measured local information using each node's local clustering coefficient and clustering degree, thereby defining a node's spreading ability as its mass derived from both neighbor information and node degree. In a related approach, Fei et al. ^[216] assessed node importance by defining mutual attraction based on the inverse-square law, though this method may overlook more complex inter-node relationships.

A single centrality measure often fails to fully capture the importance of nodes in a network. To address this, researchers have introduced weighted models based on gravitational principles, incorporating multiple attributes to assess node influence. Wang et al. ^[217] enhanced the gravity model method by integrating $$ k $$-shell value and degree centrality while further considering neighbor information to improve accuracy. Building on this approach, Li et al. ^[218] proposed the Local Gravity Model (LGM) method, which defines node importance as a weighted combination of degree, $$ k $$-shell value, and eigenvector centrality. To ensure comparability across different networks, these metrics are normalized, with a balancing parameter introduced to prevent the $$ k $$-shell value from disproportionately influencing smaller networks. Similarly, Yan et al. ^[219] adopted a multi-attribute decision-making approach, constructing a decision matrix based on multiple centrality measures and using entropy weighting to determine a node's overall importance. Beyond centrality weighting, researchers have also addressed the issue of influence overlap among high-centrality nodes. Wang et al. ^[220] introduced the centripetal centrality index, which integrates node attributes and connectivity to reduce redundancy in influence propagation, albeit at a high computational cost. Yang et al. ^[221] developed the AIGCrank algorithm, combining gravitational centrality with a recursive ranking strategy that integrates the h-index, domain core centrality, and clustering coefficient, effectively distinguishing key nodes while mitigating influence overlap. Other approaches focus on probability-based propagation and structural optimization. Zhu et al. ^[222] introduced the H-index-based gravity centrality (HVGC) method, incorporating the h-index, node distance, and an exponential decay factor to accurately identify bridge nodes that connect different network regions, even if they exhibit low $$ k $$-shell values. Additionally, Liu et al. ^[223] developed the entropy-based gravity model for identifying the most significant nodes (SEGM) and entropy-based gravity model (EGM) models, respectively, leveraging information entropy to capture the diffusion capabilities of nodes more effectively.

To mitigate the high computational cost of shortest path calculations, researchers have proposed alternative approaches that approximate or replace shortest path metrics with more efficient methods. Zhao et al. ^[224] employed random walks to estimate node distances, using degree centrality as a proxy for node influence. Extending this idea, Zhao et al. ^[225] introduced the Network Embedding and Gravity Model (NEGM), which replaces shortest path lengths with Euclidean distances derived from Node2Vec embeddings. Similarly, Shang et al. ^[226] defined a probabilistic distance using Markov chain-based transition probabilities, capturing latent inter-node relationships without computing exact shortest paths. Beyond shortest path approximations, alternative gravity-based models have been proposed. Curado et al. ^[227] introduced a method leveraging return-based random walks and effective distance to capture both static and dynamic network topologies. Yang et al. ^[228] refined interaction range definitions by incorporating an adaptive truncation radius and considering all-channel paths instead of shortest path constraints. Chen et al. ^[229] proposed the Degree Centrality Gravity Model (DCGM) model, integrating degree and average neighbor degree to enhance influence estimation. Further advancements address asymmetric interactions and multilayer structures. Meng et al. ^[230] developed the Asymmetric Attraction Model (AAM), transforming adjacency matrices into asymmetric attraction matrices to capture directional dependencies. Xu et al. ^[231] introduced the communicability-based adaptive gravity model (CAGM), incorporating influence probability, $$ k $$-shell, and degree information for adaptive gravity-based estimation. Li et al. ^[232] extended gravity-based models to multilayer networks, proposing the Adaptive PageRank Algorithm Modified by the Gravity Model (APAMGM) for multiplex transportation networks. Lü et al. ^[233] introduced improved gravity centrality based on multi-PageRank (PRGC), integrating multi-PageRank centrality with weighted shortest path distances. Chi et al. ^[234] developed a semi-global centrality measure inspired by stellar models, incorporating variable propagation speeds and the gravitational slingshot effect to quantify node efficiency in information diffusion.

7.2. Multiple metrics

To address challenges in identifying critical nodes arising from varied network structures and densities, researchers have developed composite centrality measures that integrate multiple metrics. For instance, Comin et al. ^[235] proposed a comprehensive centrality index that balances global and local characteristics by analyzing three different information propagation strategies. De Arruda et al. ^[236] further explored dynamic propagation by proposing the Random Walk Accessibility (RWA) expansion indicator, based on nine centrality measures, to assess the ability of nodes to spread information in both spatial and non-spatial networks. To integrate multiple centrality measures, Hu et al. ^[237] adopted linear discriminant analysis to integrate eigenvector, betweenness, closeness, degree centrality, and mutual information, developing a multi-metric evaluation algorithm. Hu et al. ^[238] then proposed the node importance contribution correlation matrix (NICCM) method, constructing a contribution matrix that defines importance by combining efficiency with weighted contributions.

Several studies have integrated multiple centrality measures to enhance prediction accuracy. Bucur et al. ^[239] combined statistical classifiers into composite metrics, demonstrating high predictive power in SIR epidemic models. Wei et al. ^[240] developed a heterogeneous mean-field model incorporating betweenness, degree, H-index, and core degree, showing that betweenness-based immunization strategies are effective in BA networks, whereas degree-based strategies perform well in real networks. An et al. ^[241] introduced the DIRCI method, leveraging dynamic influence scope, network layer centrality, and community centrality for critical node identification in multilayer networks. Wu et al. ^[242] proposed radiation centrality, which models information dissipation using attenuation and scattering theories. Other approaches combine local and global structural features. Cao et al. ^[243] introduced INLGC, integrating local network constraint coefficients with global community structure. Kopsidas et al. ^[244] merged centrality measures from different transport networks to assess metro station criticality. Wang et al. ^[245] proposed a multi-factor information matrix centrality algorithm, incorporating node influence, neighbor influence, and feedback-based mutual influence. Lei et al. ^[246] developed the Weighted Information Index (WII), which utilizes second-order neighbor information to construct an information distribution vector. Ullah et al. ^[247] introduced NPIC, integrating neighborhood and path information, while Zhang et al. ^[248] employed the Comprehensive Voting Ranking (CVR) algorithm, incorporating mutual information and k-center clustering to identify critical nodes in urban rail networks. Several iterative and hybrid models have also been proposed. Lee et al. ^[249] developed the Balanced Iterative Influence (BII) algorithm, iteratively combining local structural information with global influence. Esfandiari et al. ^[250] introduced HNPR, which integrates $$ k $$-shell and PageRank into a novel linear metric. Chen et al. ^[251] proposed the SFIMCO method, distinguishing overlapping from non-overlapping nodes to quantify intra-community influence. Zhang et al. ^[252] introduced the SLCMF metric, integrating structural, social, and semantic factors while improving scalability via distributed subgraphs and shortest path approximations. Dempster-Shafer evidence theory has also been applied to node importance estimation. Mo et al. ^[253] developed Comprehensive Evidence Centrality (CEC), integrating degree, betweenness, and closeness centrality. Xu et al. ^[254] introduced the Local-Global-Position (LGP-DS) algorithm, which combines global, local, and positional attributes, leveraging information entropy to evaluate and aggregate their contributions to node importance.

To address the challenge of distinguishing nodes within the same $$ k $$-shell layer, Sheikhahmadi et al. ^[255] introduced the MCDE hybrid index, integrating node shell, degree, and entropy information to enhance accuracy and efficiency. Wang et al. ^[256,257], Sheikhahmadi et al. ^[258], and Yang et al. ^[259] developed iterative removal-based indices that combine node position and factor indices to achieve efficient $$ O(n) $$ complexity. Namtirtha et al. ^[260] introduced the NGSC indicator, a weighted sum of $$ k $$-shell values and neighbor degrees, adaptable to both dense and sparse networks. Hybrid approaches integrating local and global structure have also been explored. Ullah et al. ^[261] developed the Global Structure Model (GSM) to capture global node influence, while the Local and Global Centrality (LGC) metric ^[262] combines $$ k $$-shell entropy with neighbor degree sums. Hu et al. ^[263] proposed a neighbor similarity coefficient, integrating $$ k $$-shell hierarchy and node degrees for improved influence evaluation. Wang et al. ^[264] developed the ALSI method, incorporating both inherent and neighbor-driven influence. Mukhtar et al. ^[265] introduced H-GSM, combining degree centrality and $$ k $$-shell centrality to overcome single-metric limitations. Yang et al. ^[266] refined influence ranking using a structural iteration factor method, distinguishing nodes through iteration steps to mitigate propagation limitations. Qiu et al. ^[267] proposed a hierarchical composite algorithm, integrating constraint coefficients from the salton index with improved $$ k $$-shell for local-global ranking.

7.3. Topsis and entropy-weight

The TOPSIS method integrates multiple centrality metrics, offering a comprehensive and objective approach to evaluate node importance. Du et al. ^[268] proposed a new method for assessing node importance in complex networks using the TOPSIS method. A decision matrix $$ D=(x_{mn}) $$ is constructed using the multiple attributes of nodes in the network, and the decision matrix is normalized as$$ r_{ij} = x_{ij} / \sum_{j=1}^{m}x_{ij}^{2}, \quad i=1, \dots, m, j=1, \dots, n $$. Then, multiply each column of this normalized matrix by its corresponding weight to obtain the weighted decision matrix $$ A=(v_{mn}): v_{ij}=w_{ij}\; \times r_{ij} $$ where $$ w_{j} $$ is the weight of the $$ v_j $$ column. The TOPSIS method selects the alternative that is simultaneously closest to the positive ideal solution and furthest from the negative ideal solution. Define the positive ideal solution as $$ A^{+} $$ and the negative ideal solution as $$ A^{-} $$, defined as follows:

where $$ K_{b} $$ and $$ K_{c} $$ are benefit and cost sets. The Euclidean distances to these ideals, $$ S^{+}_{i} $$ and $$ S^{-}_{i} $$ were calculated, and the relative closeness $$ C_{i} = \frac{S^{-}_{i}}{S^{-}_{i}+S^{+}_{i}}, i = 1, \dots, m. $$ A higher $$ C_i $$ indicates that the node is closer to the positive ideal solution and farther from the negative ideal, thus signifying greater importance. Several studies have applied and extended this methodology. For instance, Liu et al. ^[269] used degree, betweenness, closeness, and $$ k $$-shell values to construct and standardize a decision matrix for TOPSIS-based node evaluation. Hu et al. ^[270] incorporated the SIR model to adjust attribute weights and optimize the TOPSIS model. Other researchers have tailored TOPSIS to specific network types. Li et al. ^[271] combined resistance centrality with a weighted TOPSIS approach for weighted power grids. Dong et al. ^[272] defined a communication probability matrix based on shortest path length and number of paths between nodes, using relative entropy to measure differences in communication distributions in their TOPSIS system. These adaptations highlight TOPSIS's flexibility and effectiveness in evaluating node importance across diverse network types.

The entropy weight method and empowerment method enhance the highest attribute in the comprehensive evaluation system, increasing the distinction of relative tightness. Chen et al. ^[273] introduced an adjustable TOPSIS method to address the entropy weight method's tendency to overemphasize attributes with high data diversity. This method incorporates a weight coefficient to modulate the influence of entropy weights on the evaluation outcomes. Ishfaq et al. ^[274] employed the entropy weight technique to assign objective weights to each criterion and then applied TOPSIS to rank nodes. Yang et al. ^[275] proposed a local centrality indicator that incorporates multi-layer neighbor and clustering coefficient information. When combined with grey relational analysis (GRA) and the SIR model, this indicator more accurately identifies key nodes compared to traditional weighted TOPSIS. Vega-Oliveros et al. ^[276] introduced the multi-centrality index (MCI) for document keyword extraction by optimizing the combination of centrality indicators. Lu et al. ^[277] used relative entropy and gray relational degree to improve node evaluation in power networks. Zhang et al. ^[278] proposed a Multi-attribute Critic Network Decision Indicator (MCNDI) that integrates the H-index, closeness centrality, and other metrics using the objective CRITIC method for weighting. Ju et al. ^[279] introduced the Multi-Criteria Compromise Ranking Method (VIKOR) combined multiple rail transit networks into a multi-layer regional network, determined centrality criterion weights using an objective method.

8.1. Diffusion model

Diffusion-based ranking methods assess node influence by modeling information or disease spread. Macdonald et al. ^[280] applied the SIR model to compare centrality metrics, demonstrating that eigenvector centrality effectively identifies high-impact spreaders above a critical infection threshold. Borgatti et al. ^[281] introduced the KPP-POS and KPP-NEG algorithms: KPP-POS optimizes information flow by maximizing average diffusion efficiency, while KPP-NEG disrupts network connectivity by removing key nodes, enhancing influence identification for targeted dissemination. Zhuge et al. ^[282] proposed Topological Centrality (TC), iteratively updating node and edge weights to quantify influence, with a stable weight of 1 indicating centrality. Aral et al. ^[283] applied randomized experiments and a continuous-time proportional hazards model to distinguish individual influence from peer susceptibility. Addressing location-aware IM, Li et al. ^[284] developed approximation-ratio greedy algorithms: a boundary greedy method leveraging upper and lower bounds for Top-$$ k $$ spreader identification, and a hint-based approach precomputing clues for efficient high-impact node detection in real-time dissemination.

To overcome the limitations of traditional centrality metrics in assessing the spreading capability of non-topologically dominant nodes, Lawyer et al. ^[285] introduced the Expected Force (EXP) metric, which incorporates entropy to model the distribution of infectiousness across multiple propagation rounds. Similarly, Chen et al. ^[286] proposed three diffusion-based indicators - NEGD, diffusion speed, and diffusion scale - where NEGD, defined as the ratio of Expected Geodesic Distance (EGD) to Largest Geodesic Distance (LGD), quantifies overall propagation efficiency. Although these methods effectively identify influential nodes within local neighborhoods, they do not guarantee global optimality. Robinaugh et al. ^[287] improved influence estimation by introducing single-step and multi-step expected impact measures for analyzing psychopathology networks. Bozorgi et al. ^[288] proposed the INCIM algorithm, which combines local propagation dynamics with global network structure to evaluate both inter- and intra-community influence under the linear threshold model. Meanwhile, Holme et al. ^[289] investigated outbreak size, vaccination effects, and information diffusion using SIR simulations. Collectively, these diffusion-based approaches simulate the spread of information or disease to assess node influence, integrating both local and global network characteristics to offer practical solutions for identifying critical nodes in diverse network environments.

Recent advances further enhance influence estimation. Yin et al. ^[290] leveraged Compressed Sensing Theory (CST) to frame node identification as sparse signal reconstruction, applying the SIR model for efficient target detection. He et al. ^[291] proposed the Two-stage Iterative Framework for the Influence Maximization in social networks (TIFIM), combining descending iteration and top-advantage metrics for seed node selection. Tulu et al. ^[292] developed the Node Willingness and Influence (NWI) algorithm, integrating network structure and interaction frequency for key spreader detection. Zhong et al. ^[293] introduced the Improved Information Entropy (IIE) method, leveraging higher-order neighborhoods and weighted entropy to refine node importance. Li et al. ^[294] employed a Spearman-like correlation to enhance ranking precision, outperforming degree and betweenness centrality. Gong et al. ^[295] proposed the Probability-Driven Structure-Aware (PDSA) algorithm, which updates influence estimates via graph traversal in the IC model. Wang et al. ^[296] introduced the HGIM method, constructing a heterogeneous propagation graph to integrate topology with diffusion cascades. To model dynamic influence, Mohammadi et al. ^[297] proposed the Two-Sided Sign-Aware Matching (TSM) framework, incorporating trust and reciprocity in signed networks. Wang et al. ^[298] introduced the Dynamic Propagation Probability (DPP) model, redefining neighbor influence within a three-hop neighborhood. Xu et al. ^[299] developed the Local Propagation Probability (LPP) model, integrating hierarchical propagation influence across different orders.

For large-scale networks, Ai et al. ^[300] proposed the spreading probability centrality (SPC) method, which balances network connectivity with propagation precision by defining infection probabilities within a truncated radius. Zareie et al. ^[301] optimized key node selection using the Gray-golf algorithm, incorporating second-order neighbor effects for propagation efficiency. Chen et al. ^[302] introduced the Dynamic Influence Seed Selection (DYISSE) method, integrating two-hop triangular influence measures for robust diffusion estimation. Fink et al. ^[303] introduced virus centrality, leveraging weighted directed networks to estimate propagation potential. Sun et al. ^[304] further refined IDME by integrating neighborhood similarity and centrality. Ullah et al. ^[305] proposed the Local Structure System (LSS), which incorporates $$ k $$-shell, degree, and triangle count to quantify influence. Finally, Corsin et al. ^[306] developed an agent-based information diffusion model, demonstrating that source persistence has a greater impact on network consensus than source quantity, particularly in polarized environments.

8.2. Dynamical sensitivity

Liu et al. ^[307] have proposed the dynamic sensitive centrality (DSC) by integrating topological features and dynamic characteristics, considering a discrete time spreading model in which an infected node will infect its neighbors with a spreading rate $$ \beta $$ and recover with a recovery rate $$ \mu $$. Let $$ x(t)(t>0) $$ denote the approximate value of the cumulative probability of nodes being activated between time step 1 and $$ t $$, then $$ x(t)-x(t-1)(t>1) $$ is approximated as the probability of a node being infected at time step $$ t $$. If $$ v_i $$ is the unique initial infected node, then $$ x_{i}(0)=1 $$ and $$ x_{j\ne i}(0)=0 $$. In the first time step, $$ x(1)=\beta Ax(0) $$, and for $$ t>1 $$: $$ x(t)-x(t-1) = \beta A[\beta A+(1-\mu)I]^{t-1}x(0) $$, where $$ v_i $$ is the identity matrix. Let $$ H=\beta A +(1-\mu)I $$, then the cumulative probability of nodes being infected between time step 1 and $$ t $$ can be approximated as

Define $$ S_{i}(t) $$ as the spreading influence of node $$ i $$ at time step $$ t $$. In the case where node $$ i $$ is initially infected, it can be quantified as the sum of the infection probabilities of all nodes. The infection probability in the equation above is $$ x(t) = \sum_{r=0}^{t-1}\; \beta A H^{r} e_{i} $$ where $$ e_{i}=(0, \dots, 0, 1, \dots, 0)^{T} $$ is a vector with only the $$ i $$-th entry being 1. Therefore, the spreading influence of node $$ v_i $$ can be defined as $$ S_{i}(t) = [(\beta A +\beta AH + \dots + \beta AH^{t-1})^{T}L] $$ where $$ L=(1, 1, \dots, 1)^{T} $$ is a vector of size $$ n\times 1 $$. DS centrality directly measures node influence, capturing both structural and dynamic factors. Mo et al. ^[308] integrated multiple centrality metrics - including degree, betweenness, efficiency, and correlation - using the Dempster-Shafer (D-S) evidence theory. By treating these metrics as distinct probability assignments and applying evidence combination rules, they developed a comprehensive indicator for node importance. Du et al. ^[309] introduced an Improved Topological Potential Model (ITPE) that leverages topological entropy to assign weights to centrality measures such as weighted degree, betweenness, closeness, and eigenvector centrality. By optimizing control parameters to minimize topological entropy.

Acknowledgments

We acknowledge Prof. Guanrong Chen from City University of Hong Kong for insightful discussions. We also would like to express our great appreciation to the editors and reviewers.

Authors' contributions

Conceived and designed the study, and wrote the manuscript: Chen, D.; Chen, J.

Performed the literature collection, analysis, and contributed to the writing and revision of the manuscript: Zhang, X.; Jia, Q.; Liu, X.; Sun, Y.

Contributed to the discussion and provided significant feedback on the manuscript: Lü, L.

Supervised the research, provided overall guidance, and revised the manuscript: Yu, W.

All authors have read and agreed to the published version of the manuscript.

Availability of data and materials

Not applicable.

Financial support and sponsorship

This work has received funding from the National Key R&D Program of China under Grant 2022ZD0120004, the Zhishan Youth Scholar Program, the National Natural Science Foundation of China under Grants 62233004, 62273090, and 62073076, and the Jiangsu Provincial Scientific Research Center of Applied Mathematics under Grant BK20233002.

Conflicts of interest

This manuscript underwent a double-blind peer review process. Yu, W. serves as the Editor-in-Chief of Complex Engineering Systems, Chen, D. and Lü, L. are members of its Editorial Board. None of them were involved in any part of the editorial process for this manuscript, including reviewer selection, handling, or decision-making, while the other authors have declared that they have no conflicts of interest.

Ethical approval and consent to participate

Not applicable.

Consent for publication

Not applicable.

Copyright

© The Author(s) 2025.