A Fast Algorithm for Moderating Critical Nodes via Edge Removal
- URL: http://arxiv.org/abs/2309.06392v1
- Date: Sat, 9 Sep 2023 13:54:34 GMT
- Title: A Fast Algorithm for Moderating Critical Nodes via Edge Removal
- Authors: Changan Liu, Xiaotian Zhou, Ahad N. Zehmakan, and Zhongzhi Zhang
- Abstract summary: 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.
- Score: 19.130541561303293
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Critical nodes in networks are extremely vulnerable to malicious attacks to
trigger negative cascading events such as the spread of misinformation and
diseases. Therefore, effective moderation of critical nodes is very vital for
mitigating the potential damages caused by such malicious diffusions. The
current moderation methods are computationally expensive. Furthermore, they
disregard the fundamental metric of information centrality, which measures the
dissemination power of nodes.
We investigate the problem of removing $k$ edges from a network to minimize
the information centrality of a target node $\lea$ while preserving the
network's connectivity. We prove that this problem is computationally
challenging: it is NP-complete and its objective function is not supermodular.
However, we propose three approximation greedy algorithms using novel
techniques such as random walk-based Schur complement approximation and fast
sum estimation. One of our algorithms runs in nearly linear time in the number
of edges.
To complement our theoretical analysis, we conduct a comprehensive set of
experiments on synthetic and real networks with over one million nodes. Across
various settings, the experimental results illustrate the effectiveness and
efficiency of our proposed algorithms.
Related papers
- Minimum Topology Attacks for Graph Neural Networks [70.17791814425148]
Graph Neural Networks (GNNs) have received significant attention for their robustness to adversarial topology attacks.
We propose a new type of topology attack, named minimum-budget topology attack, aiming to adaptively find the minimum perturbation sufficient for a successful attack on each node.
arXiv Detail & Related papers (2024-03-05T07:29:12Z) - Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
We propose a class of novel distributed Adam-type algorithms (emphi.e., SketchedAMSGrad) utilizing sketching.
Our new algorithm achieves a fast convergence rate of $O(frac1sqrtnT + frac1(k/d)2 T)$ with the communication cost of $O(k log(d))$ at each iteration.
arXiv Detail & Related papers (2022-10-14T01:42:05Z) - LGTBIDS: Layer-wise Graph Theory Based Intrusion Detection System in
Beyond 5G [9.63617966257402]
Intrusion detection signifies a central approach to ensuring the security of the communication network.
A Layerwise Graph Theory-Based Intrusion Detection System (LGTBIDS) algorithm is designed to detect the attacked node.
Results validate the better performance, low time computations, and low complexity.
arXiv Detail & Related papers (2022-10-06T05:32:03Z) - 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) - Robust Training and Verification of Implicit Neural Networks: A
Non-Euclidean Contractive Approach [64.23331120621118]
This paper proposes a theoretical and computational framework for training and robustness verification of implicit neural networks.
We introduce a related embedded network and show that the embedded network can be used to provide an $ell_infty$-norm box over-approximation of the reachable sets of the original network.
We apply our algorithms to train implicit neural networks on the MNIST dataset and compare the robustness of our models with the models trained via existing approaches in the literature.
arXiv Detail & Related papers (2022-08-08T03:13:24Z) - Identifying critical nodes in complex networks by graph representation
learning [2.304938062591095]
Influence is one of the main problems in critical nodes mining.
IMGNN is a graph learning framework that takes centralities of nodes in a network as input and the probability that nodes in the optimal initial spreaders as output.
IMGNN is more efficient than human-based algorithms in minimizing the size of initial spreaders under the fixed infection scale.
arXiv Detail & Related papers (2022-01-20T03:41:22Z) - 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) - Efficiently Learning Any One Hidden Layer ReLU Network From Queries [27.428198343906352]
We give the first-time algorithm for learning arbitrary one hidden layer neural networks activations provided black-box access to the network.
Ours is the first with fully-time guarantees of efficiency even for worst-case networks.
arXiv Detail & Related papers (2021-11-08T18:59:40Z) - Multiple Node Immunisation for Preventing Epidemics on Networks by Exact
Multiobjective Optimisation of Cost and Shield-Value [0.0]
This paper deals with the problem of selecting multiple nodes for removal.
As compared to previous work on multiple-node selection, the trade-off between cost and benefit is considered.
The main contribution of this paper is the insight that, if time permits, exact and problem-specific methods approximation should be used.
arXiv Detail & Related papers (2020-10-13T15:49:00Z) - Bayesian Optimization with Machine Learning Algorithms Towards Anomaly
Detection [66.05992706105224]
In this paper, an effective anomaly detection framework is proposed utilizing Bayesian Optimization technique.
The performance of the considered algorithms is evaluated using the ISCX 2012 dataset.
Experimental results show the effectiveness of the proposed framework in term of accuracy rate, precision, low-false alarm rate, and recall.
arXiv Detail & Related papers (2020-08-05T19:29:35Z)
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.