论文标题
通过切割边缘攻击最短路径
Attacking Shortest Paths by Cutting Edges
论文作者
论文摘要
识别网络中节点之间的最短路径是一个常见的图形分析问题，对于许多涉及资源路由的应用程序很重要。可以操纵图形结构的对手可以改变流量模式以获取一些好处（例如，通过将流量引导到收费公路来赚更多的钱）。本文提出了力路径切割问题，其中对手从图中取下边缘，以使特定路径在其末端节点之间最短。我们证明了这个问题是APX-HARD，但是引入了Pathattack，这是一种多项式时间近似算法，可以保证在最佳值的对数因子内的解决方案。此外，我们引入了力边缘切割和力节点切割问题，其中对手分别针对特定的边缘或节点，而不是整个路径。我们为这些问题得出了非凸优化公式，并得出了使用Pathattack作为子例程的启发式算法。我们在各种真实和合成网络集中演示了所有这些算法，说明了从提出的算法中受益最大的网络类型。
Identifying shortest paths between nodes in a network is a common graph analysis problem that is important for many applications involving routing of resources. An adversary that can manipulate the graph structure could alter traffic patterns to gain some benefit (e.g., make more money by directing traffic to a toll road). This paper presents the Force Path Cut problem, in which an adversary removes edges from a graph to make a particular path the shortest between its terminal nodes. We prove that this problem is APX-hard, but introduce PATHATTACK, a polynomial-time approximation algorithm that guarantees a solution within a logarithmic factor of the optimal value. In addition, we introduce the Force Edge Cut and Force Node Cut problems, in which the adversary targets a particular edge or node, respectively, rather than an entire path. We derive a nonconvex optimization formulation for these problems, and derive a heuristic algorithm that uses PATHATTACK as a subroutine. We demonstrate all of these algorithms on a diverse set of real and synthetic networks, illustrating the network types that benefit most from the proposed algorithms.
