论文标题
使用连接查询映射网络状态
Mapping Network States Using Connectivity Queries
论文作者
论文摘要
我们可以推断基础架构网络的所有失败组件，从供应节点提供了可触及的节点的样本？自然灾害后最关键的干扰后过程之一是快速确定关键基础设施组件的损害或故障状态。但是，考虑到颠覆性事件后通常只能访问或观察到的组件通常只有一小部分。过去的工作已经研究了给定点探测器的失败组件，即使用直接的失败组件样本。相比之下，我们研究了一些“可用”可及节点的部分信息和一小部分探针样本，这是推断失败组件的更困难问题，这是第一个通常更实用的。我们使用最小描述长度（MDL）原理提出了这个新的问题，然后提出了一种贪婪的算法，该算法有效地将MDL成本降至最低。我们在地震后对真实网络的域 - 专家模拟进行了评估算法。我们的算法成功地识别了失败的组件，尤其是影响整体系统性能的关键组件。
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.
