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$ 既有很小的概率使随机图 $G$ 满足 $A$，但高概率下有一个小扰动可以将 $G$ 转化为满足 $A$ 的图形，我们称该属性为反随机属性。虽然对于标记图，可以通过二进制覆盖码轻松获得这些属性，但无标记图的反随机特性并不明显。如果可接受的扰动是添加或删除一个边，则我们展示了一个反随机属性，该属性在随机无标记图的阶数为 n 时以概率 $(2+o(1))/n^2$ 满足，这是最小可能的。我们还根据图的度序列表达了另一种反随机属性。这个属性的概率是 $(2+o(1))/(n\ln n)$，这是最优秀的，最多可以乘以 2。
相关内容
微信扫码咨询专知VIP会员