Mapping Network States Using Connectivity Queries

• URL: http://arxiv.org/abs/2012.03413v3
• Date: Thu, 24 Dec 2020 03:15:06 GMT
• Title: Mapping Network States Using Connectivity Queries
• Authors: Alexander Rodr\'iguez, Bijaya Adhikari, Andr\'es D. Gonz\'alez, Charles Nicholson, Anil Vullikanti, B. Aditya Prakash
• Abstract summary: Can we infer all the failed components of an infrastructure network, given a sample of reachable nodes from supply nodes? We formulate this novel problem using the Minimum Description Length (MDL) principle. We evaluate our algorithm on domain-expert simulations of real networks in the aftermath of an earthquake.
• Score: 64.93225229494976
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Can we infer all the failed components of an infrastructure network, given a sample of reachable nodes from supply nodes? One of the most critical post-disruption processes after a natural disaster is to quickly determine the damage or failure states of critical infrastructure components. However, this is non-trivial, considering that often only a fraction of components may be accessible or observable after a disruptive event. Past work has looked into inferring failed components given point probes, i.e. with a direct sample of failed components. In contrast, we study the harder problem of inferring failed components given partial information of some `serviceable' reachable nodes and a small sample of point probes, being the first often more practical to obtain. We formulate this novel problem using the Minimum Description Length (MDL) principle, and then present a greedy algorithm that minimizes MDL cost effectively. We evaluate our algorithm on domain-expert simulations of real networks in the aftermath of an earthquake. Our algorithm successfully identify failed components, especially the critical ones affecting the overall system performance.

Related papers

• Mitigating the Effect of Incidental Correlations on Part-based Learning [50.682498099720114]
  Part-based representations could be more interpretable and generalize better with limited data. We present two innovative regularization methods for part-based representations. We exhibit state-of-the-art (SoTA) performance on few-shot learning tasks on benchmark datasets.
  arXiv  Detail & Related papers  (2023-09-30T13:44:48Z)
• 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)
• Quantum amplitude estimation with error mitigation for time-evolving probabilistic networks [0.0]
  We consider networks of nodes, where each node can be in one of two states: good or failed. Our method can evaluate arbitrary network topologies for any number of time steps. We present the results of a low-depth quantum amplitude estimation on a simulator with a realistic noise model.
  arXiv  Detail & Related papers  (2023-03-29T10:45:11Z)
• Affordance detection with Dynamic-Tree Capsule Networks [5.847547503155588]
  Affordance detection from visual input is a fundamental step in autonomous robotic manipulation. We introduce the first affordance detection network based on dynamic tree-structured capsules for sparse 3D point clouds. Our algorithm is superior to current affordance detection methods when faced with grasping previously unseen objects.
  arXiv  Detail & Related papers  (2022-11-09T21:14:08Z)
• 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)
• Reliability Assessment of Neural Networks in GPUs: A Framework For Permanent Faults Injections [1.0992151305603266]
  This paper proposes a framework, resorting to a binary instrumentation tool, to perform fault injection campaigns on a GPU. This environment allows for the first time assessing the reliability of CNNs deployed on a GPU considering the presence of permanent faults.
  arXiv  Detail & Related papers  (2022-05-24T16:21:53Z)
• 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)
• 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)
• Firearm Detection and Segmentation Using an Ensemble of Semantic Neural Networks [62.997667081978825]
  We present a weapon detection system based on an ensemble of semantic Convolutional Neural Networks. A set of simpler neural networks dedicated to specific tasks requires less computational resources and can be trained in parallel. The overall output of the system given by the aggregation of the outputs of individual networks can be tuned by a user to trade-off false positives and false negatives.
  arXiv  Detail & Related papers  (2020-02-11T13:58:16Z)

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.