OPTIMAL ATTACK AND REINFORCEMENT OF A NETWORK
OPTIMAL ATTACK AND REINFORCEMENT OF A NETWORK
复制标题
DOI：
10.1145/3828.3829
复制
发表时间：
1985-01-01
影响因子：
2.5
通讯作者：
CUNNINGHAM, WH
中科院分区：
文献类型：
--
作者：
CUNNINGHAM, WH
在非负边加权网络中，边的权重表示攻击者破坏边所需的努力，并且攻击者通过破坏边来获得每个新组件的好处。攻击者可能希望在边缘的子集上最小化所引起的努力与所接收的收益之间的差异（或比率）。这一想法导致了网络“强度”的定义，这是衡量网络对此类攻击的抵抗力的一个指标。最佳攻击问题的有效算法，计算强度的问题，并找到一个最小的成本“加固”，以达到所需的强度的问题。这些问题也解决了一个不同的模型，其中攻击者希望从一个固定的中心顶点分离顶点。
In a nonnegative edge-weighted network, the weight of an edge represents the effort required by an attacker to destroy the edge, and the attacker derives a benefit for each new component created by destroying edges. The attacker may want to minimize over subsets of edges the difference between (or the ratio of) the effort incurred and the benefit received. This idea leads to the definition of the “strength” of the network, a measure of the resistance of the network to such attacks. Efficient algorithms for the optimal attack problem, the problem of computing the strength, and the problem of finding a minimum cost “reinforcement” to achieve a desired strength are given. These problems are also solved for a different model, in which the attacker wants to separate vertices from a fixed central vertex.