Neighborhood Information-based Probabilistic Algorithm for Network Disintegration

• URL: http://arxiv.org/abs/2003.04713v1
• Date: Sun, 8 Mar 2020 15:09:25 GMT
• Title: Neighborhood Information-based Probabilistic Algorithm for Network Disintegration
• Authors: Qian Li, San-Yang Liu, Xin-She Yang
• Abstract summary: This paper presents a probabilistic approach based on neighborhood information and node importance. We also define a new centrality-based importance measure (IM) Experiments suggest that the proposed NIPA is most effective among all four methods.
• Score: 7.511240139514371
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Many real-world applications can be modelled as complex networks, and such networks include the Internet, epidemic disease networks, transport networks, power grids, protein-folding structures and others. Network integrity and robustness are important to ensure that crucial networks are protected and undesired harmful networks can be dismantled. Network structure and integrity can be controlled by a set of key nodes, and to find the optimal combination of nodes in a network to ensure network structure and integrity can be an NP-complete problem. Despite extensive studies, existing methods have many limitations and there are still many unresolved problems. This paper presents a probabilistic approach based on neighborhood information and node importance, namely, neighborhood information-based probabilistic algorithm (NIPA). We also define a new centrality-based importance measure (IM), which combines the contribution ratios of the neighbor nodes of each target node and two-hop node information. Our proposed NIPA has been tested for different network benchmarks and compared with three other methods: optimal attack strategy (OAS), high betweenness first (HBF) and high degree first (HDF). Experiments suggest that the proposed NIPA is most effective among all four methods. In general, NIPA can identify the most crucial node combination with higher effectiveness, and the set of optimal key nodes found by our proposed NIPA is much smaller than that by heuristic centrality prediction. In addition, many previously neglected weakly connected nodes are identified, which become a crucial part of the newly identified optimal nodes. Thus, revised strategies for protection are recommended to ensure the safeguard of network integrity. Further key issues and future research topics are also discussed.

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)
• Improving Critical Node Detection Using Neural Network-based Initialization in a Genetic Algorithm [3.5877750256097465]
  The primary objective of CNP-1a is to minimize the pair-wise connectivity in the remaining network after deleting a limited number of nodes from a network. To improve the efficiency of solving CNP-1a, a knowledge-guided genetic algorithm named K2GA has been proposed. The effectiveness of the proposed knowledgeguided genetic algorithm is verified by experiments on 26 realworld instances of complex networks.
  arXiv  Detail & Related papers  (2024-02-01T07:53:25Z)
• 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)
• 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)
• SSSNET: Semi-Supervised Signed Network Clustering [4.895808607591299]
  We introduce a novel probabilistic balanced normalized cut loss for training nodes in a GNN framework for semi-supervised signed network clustering, called SSSNET. The main novelty approach is a new take on the role of social balance theory for signed network embeddings.
  arXiv  Detail & Related papers  (2021-10-13T10:36:37Z)
• Layer Adaptive Node Selection in Bayesian Neural Networks: Statistical Guarantees and Implementation Details [0.5156484100374059]
  Sparse deep neural networks have proven to be efficient for predictive model building in large-scale studies. We propose a Bayesian sparse solution using spike-and-slab Gaussian priors to allow for node selection during training. We establish the fundamental result of variational posterior consistency together with the characterization of prior parameters.
  arXiv  Detail & Related papers  (2021-08-25T00:48:07Z)
• AM-GCN: Adaptive Multi-channel Graph Convolutional Networks [85.0332394224503]
  We study whether Graph Convolutional Networks (GCNs) can optimally integrate node features and topological structures in a complex graph with rich information. We propose an adaptive multi-channel graph convolutional networks for semi-supervised classification (AM-GCN) Our experiments show that AM-GCN extracts the most correlated information from both node features and topological structures substantially.
  arXiv  Detail & Related papers  (2020-07-05T08:16:03Z)
• 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)
• Graph Prototypical Networks for Few-shot Learning on Attributed Networks [72.31180045017835]
  We propose a graph meta-learning framework -- Graph Prototypical Networks (GPN) GPN is able to perform textitmeta-learning on an attributed network and derive a highly generalizable model for handling the target classification task.
  arXiv  Detail & Related papers  (2020-06-23T04:13:23Z)
• Proximity-based Networking: Small world overlays optimized with particle swarm optimization [0.0]
  Small world networks can be incredibly useful in the dissemination and lookup of information within an internet network. We propose a networking scheme that incorporates geographic location in chord for the organization of peers within each node's partitioned key space. The flexibility of our proposed schemes enables a variety of swarm models, and agents.
  arXiv  Detail & Related papers  (2020-06-03T01:40:46Z)

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.