Critical Nodes Identification in Complex Networks: A Survey

• URL: http://arxiv.org/abs/2507.06164v1
• Date: Tue, 08 Jul 2025 16:45:48 GMT
• Title: Critical Nodes Identification in Complex Networks: A Survey
• Authors: Duxin Chen, Jiawen Chen, Xiaoyu Zhang, Qinghan Jia, Xiaolu Liu, Ye Sun, Linyuan Lv, Wenwu Yu,
• Abstract summary: This paper provides a comprehensive review of critical node identification techniques.<n>It categorizes them into seven main classes: intrinsic, critical nodes deletion problem, influence, network control, artificial intelligence, higher-order and dynamic methods.<n>It identifies key challenges, such as algorithmic, real-time evaluation in dynamic networks, analysis of higher-order structures, and computational efficiency in large-scale networks.
• Score: 14.782530229717349
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Complex networks have become essential tools for understanding diverse phenomena in social systems, traffic systems, biomolecular systems, and financial systems. Identifying critical nodes is a central theme in contemporary research, serving as a vital bridge between theoretical foundations and practical applications. Nevertheless, the intrinsic complexity and structural heterogeneity characterizing real-world networks, with particular emphasis on dynamic and higher-order networks, present substantial obstacles to the development of universal frameworks for critical node identification. This paper provides a comprehensive review of critical node identification techniques, categorizing them into seven main classes: centrality, critical nodes deletion problem, influence maximization, network control, artificial intelligence, higher-order and dynamic methods. Our review bridges the gaps in existing surveys by systematically classifying methods based on their methodological foundations and practical implications, and by highlighting their strengths, limitations, and applicability across different network types. Our work enhances the understanding of critical node research by identifying key challenges, such as algorithmic universality, real-time evaluation in dynamic networks, analysis of higher-order structures, and computational efficiency in large-scale networks. The structured synthesis consolidates current progress and highlights open questions, particularly in modeling temporal dynamics, advancing efficient algorithms, integrating machine learning approaches, and developing scalable and interpretable metrics for complex systems.

Related papers

• Network Alignment [10.625951311359923]
  Review comprehensively summarizes the latest advancements in network alignment research.<n>It focuses on analyzing network alignment characteristics and progress in various domains such as bioinformatics, computational linguistics and privacy protection.<n>It provides a detailed analysis of various methods' implementation principles, processes, and performance differences.
  arXiv  Detail & Related papers  (2025-04-15T16:32:09Z)
• LayerPlexRank: Exploring Node Centrality and Layer Influence through Algebraic Connectivity in Multiplex Networks [4.130399938456945]
  This paper introduces LayerPlexRank, an algorithm that simultaneously assesses node centrality and layer influence in multiplex networks.<n>We substantiate the utility of LayerPlexRank with theoretical analyses and empirical validations on varied real-world datasets.
  arXiv  Detail & Related papers  (2024-05-09T06:52:24Z)
• Identification of important nodes in the information propagation network based on the artificial intelligence method [2.1331883629523634]
  We introduce a novel technique that combines the Decision-making Trial and Evaluation Laboratory (DEMATEL) and the Global Structure Model (GSM) This method is applied across various complex networks, such as social, transportation, and communication systems. Our analysis highlights the structural dynamics and resilience of these networks, revealing insights into node connectivity and community formation.
  arXiv  Detail & Related papers  (2024-02-29T23:43:08Z)
• Unsupervised Graph Attention Autoencoder for Attributed Networks using K-means Loss [0.0]
  We introduce a simple, efficient, and clustering-oriented model based on unsupervised textbfGraph Attention textbfAutotextbfEncoder for community detection in attributed networks. The proposed model adeptly learns representations from both the network's topology and attribute information, simultaneously addressing dual objectives: reconstruction and community discovery.
  arXiv  Detail & Related papers  (2023-11-21T20:45:55Z)
• Towards Improving Robustness Against Common Corruptions using Mixture of Class Specific Experts [10.27974860479791]
  This paper introduces a novel paradigm known as the Mixture of Class-Specific Expert Architecture. The proposed architecture aims to mitigate vulnerabilities associated with common neural network structures.
  arXiv  Detail & Related papers  (2023-11-16T20:09:47Z)
• Rank Diminishing in Deep Neural Networks [71.03777954670323]
  Rank of neural networks measures information flowing across layers. It is an instance of a key structural condition that applies across broad domains of machine learning. For neural networks, however, the intrinsic mechanism that yields low-rank structures remains vague and unclear.
  arXiv  Detail & Related papers  (2022-06-13T12:03:32Z)
• A Comprehensive Survey on Community Detection with Deep Learning [93.40332347374712]
  A community reveals the features and connections of its members that are different from those in other communities in a network. This survey devises and proposes a new taxonomy covering different categories of the state-of-the-art methods. The main category, i.e., deep neural networks, is further divided into convolutional networks, graph attention networks, generative adversarial networks and autoencoders.
  arXiv  Detail & Related papers  (2021-05-26T14:37:07Z)
• A neural anisotropic view of underspecification in deep learning [60.119023683371736]
  We show that the way neural networks handle the underspecification of problems is highly dependent on the data representation. Our results highlight that understanding the architectural inductive bias in deep learning is fundamental to address the fairness, robustness, and generalization of these systems.
  arXiv  Detail & Related papers  (2021-04-29T14:31:09Z)
• Investigating Bi-Level Optimization for Learning and Vision from a Unified Perspective: A Survey and Beyond [114.39616146985001]
  In machine learning and computer vision fields, despite the different motivations and mechanisms, a lot of complex problems contain a series of closely related subproblms. In this paper, we first uniformly express these complex learning and vision problems from the perspective of Bi-Level Optimization (BLO) Then we construct a value-function-based single-level reformulation and establish a unified algorithmic framework to understand and formulate mainstream gradient-based BLO methodologies.
  arXiv  Detail & Related papers  (2021-01-27T16:20:23Z)
• A Survey of Community Detection Approaches: From Statistical Modeling to Deep Learning [95.27249880156256]
  We develop and present a unified architecture of network community-finding methods. We introduce a new taxonomy that divides the existing methods into two categories, namely probabilistic graphical model and deep learning. We conclude with discussions of the challenges of the field and suggestions of possible directions for future research.
  arXiv  Detail & Related papers  (2021-01-03T02:32:45Z)
• Learning Connectivity of Neural Networks from a Topological Perspective [80.35103711638548]
  We propose a topological perspective to represent a network into a complete graph for analysis. By assigning learnable parameters to the edges which reflect the magnitude of connections, the learning process can be performed in a differentiable manner. This learning process is compatible with existing networks and owns adaptability to larger search spaces and different tasks.
  arXiv  Detail & Related papers  (2020-08-19T04:53:31Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.