We study vulnerability of a uniformly distributed random graph to an attack by an adversary who aims for a global change of the distribution while being able to make only a local change in the graph. We call a graph property $A$ anti-stochastic if the probability that a random graph $G$ satisfies $A$ is small but, with high probability, there is a small perturbation transforming $G$ into a graph satisfying $A$. While for labeled graphs such properties are easy to obtain from binary covering codes, the existence of anti-stochastic properties for unlabeled graphs is not so evident. If an admissible perturbation is either the addition or the deletion of one edge, we exhibit an anti-stochastic property that is satisfied by a random unlabeled graph of order $n$ with probability $(2+o(1))/n^2$, which is as small as possible. We also express another anti-stochastic property in terms of the degree sequence of a graph. This property has probability $(2+o(1))/(n\ln n)$, which is optimal up to factor of 2.
翻译:我们研究一个统一分布的随机图对一个对手的攻击的脆弱性,该对手的目标是在全球改变分布,但只能对图作局部改动。我们称一个图形属性为$A$反随机性,如果一个随机图能满足$A$的概率很小,但极有可能发生小的扰动,将G美元转换成一个能满足$A美元的图表。对于标签图来说,这种属性很容易从覆盖代码的二进制中获得,但对于未贴标签的图形来说,反随机性能的存在并不明显。如果一种可允许的扰动性是增加或删除一个边缘,我们则将展示一种可被随机无标签的排序图能满足的抗随机性属性,其概率为$(2+o(1))/n%2美元,该值尽可能小。我们还用图表的度序列表示另一种反随机性属性。这种属性的概率为$(2+o(1)/n\ n)/nn,最优的值为2。