Heuristic algorithms for the stochastic critical node detection problem

• URL: http://arxiv.org/abs/2512.01497v1
• Date: Mon, 01 Dec 2025 10:18:24 GMT
• Title: Heuristic algorithms for the stochastic critical node detection problem
• Authors: Tuguldur Bayarsaikhan, Altannar Chinchuluun, Ashwin Arulselvan, Panos Pardalos,
• Abstract summary: Given a network, the critical node detection problem finds a subset of nodes whose removal disrupts the network connectivity.<n>In this paper, we consider a version of the critical node detection problem, where the existence of edges is given by certain probabilities.<n>We proposes and learning-based methods for the problem and compare them with existing algorithms.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Given a network, the critical node detection problem finds a subset of nodes whose removal disrupts the network connectivity. Since many real-world systems are naturally modeled as graphs, assessing the vulnerability of the network is essential, with applications in transportation systems, traffic forecasting, epidemic control, and biological networks. In this paper, we consider a stochastic version of the critical node detection problem, where the existence of edges is given by certain probabilities. We propose heuristics and learning-based methods for the problem and compare them with existing algorithms. Experimental results performed on random graphs from small to larger scales, with edge-survival probabilities drawn from different distributions, demonstrate the effectiveness of the methods. Heuristic methods often illustrate the strongest results with high scalability, while learning-based methods maintain nearly constant inference time as the network size and density grow.

Related papers

• Conformal Prediction for Multi-Source Detection on a Network [59.17729745907474]
  We study the multi-source detection problem.<n>Given snapshot observations of node infection status on a graph, estimate the set of source nodes that initiated the propagation.<n>We propose a novel conformal prediction framework that provides statistically valid recall guarantees for source set detection.
  arXiv  Detail & Related papers  (2025-11-12T01:09:56Z)
• Solving Probabilistic Verification Problems of Neural Networks using Branch and Bound [3.0567348883549816]
  Probabilistic verification problems of neural networks are concerned with formally analysing the output distribution of a neural network under a probability distribution of the inputs.<n>We present a new algorithm for solving these problems based on an algorithm for computing and iteratively refining lower and upper bounds on probabilities over the outputs of a neural network.
  arXiv  Detail & Related papers  (2024-05-27T18:00:03Z)
• A Fast Algorithm for Moderating Critical Nodes via Edge Removal [19.130541561303293]
  We study the problem of removing $k$ edges from a network to minimize the information centrality of a target node. We propose three approximation greedy algorithms using novel techniques such as random walk-based Schur complement approximation and fast sum estimation. To complement our theoretical analysis, we conduct a comprehensive set of experiments on synthetic and real networks with over one million nodes.
  arXiv  Detail & Related papers  (2023-09-09T13:54:34Z)
• Cycle Consistency-based Uncertainty Quantification of Neural Networks in Inverse Imaging Problems [10.992084413881592]
  Uncertainty estimation is critical for numerous applications of deep neural networks. We show an uncertainty quantification approach for deep neural networks used in inverse problems based on cycle consistency.
  arXiv  Detail & Related papers  (2023-05-22T09:23:18Z)
• A Systematic Evaluation of Node Embedding Robustness [77.29026280120277]
  We assess the empirical robustness of node embedding models to random and adversarial poisoning attacks. We compare edge addition, deletion and rewiring strategies computed using network properties as well as node labels. We found that node classification suffers from higher performance degradation as opposed to network reconstruction.
  arXiv  Detail & Related papers  (2022-09-16T17:20:23Z)
• Learning to Detect Critical Nodes in Sparse Graphs via Feature Importance Awareness [53.351863569314794]
  The critical node problem (CNP) aims to find a set of critical nodes from a network whose deletion maximally degrades the pairwise connectivity of the residual network. This work proposes a feature importance-aware graph attention network for node representation. It combines it with dueling double deep Q-network to create an end-to-end algorithm to solve CNP for the first time.
  arXiv  Detail & Related papers  (2021-12-03T14:23:05Z)
• Community detection using low-dimensional network embedding algorithms [1.052782170493037]
  We rigorously understand the performance of two major algorithms, DeepWalk and node2vec, in recovering communities for canonical network models. We prove that, given some fixed co-occurrence window, node2vec using random walks with a low non-backtracking probability can succeed for much sparser networks.
  arXiv  Detail & Related papers  (2021-11-04T14:57:43Z)
• Bayesian Attention Belief Networks [59.183311769616466]
  Attention-based neural networks have achieved state-of-the-art results on a wide range of tasks. This paper introduces Bayesian attention belief networks, which construct a decoder network by modeling unnormalized attention weights. We show that our method outperforms deterministic attention and state-of-the-art attention in accuracy, uncertainty estimation, generalization across domains, and adversarial attacks.
  arXiv  Detail & Related papers  (2021-06-09T17:46:22Z)
• Anomaly Detection on Attributed Networks via Contrastive Self-Supervised Learning [50.24174211654775]
  We present a novel contrastive self-supervised learning framework for anomaly detection on attributed networks. Our framework fully exploits the local information from network data by sampling a novel type of contrastive instance pair. A graph neural network-based contrastive learning model is proposed to learn informative embedding from high-dimensional attributes and local structure.
  arXiv  Detail & Related papers  (2021-02-27T03:17:20Z)
• ESPN: Extremely Sparse Pruned Networks [50.436905934791035]
  We show that a simple iterative mask discovery method can achieve state-of-the-art compression of very deep networks. Our algorithm represents a hybrid approach between single shot network pruning methods and Lottery-Ticket type approaches.
  arXiv  Detail & Related papers  (2020-06-28T23:09:27Z)

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.