随机图形转换的可能性有多大? (How likely is a random graph shift-enabled?)

The shift-enabled property of an underlying graph is essential in designing distributed filters. This article discusses when a random graph is shift-enabled. In particular, popular graph models ER, WS, BA random graph are used, weighted and unweighted, as well as signed graphs. Our results show that the considered unweighted connected random graphs are shift-enabled with high probability when the number of edges is moderately high. However, very dense graphs, as well as fully connected graphs, are not shift-enabled. Interestingly, this behaviour is not observed for weighted connected graphs, which are always shift-enabled unless the number of edges in the graph is very low.

翻译：在设计分布式过滤器时, 基本图形的转换属性是必不可少的。此文章讨论随机图形在启用转换功能时的属性。特别是, 流行的图形模型ER、 WS、 BA 随机图形被使用, 加权和未加权, 以及签名的图形。我们的结果表明, 考虑的未加权连接的随机图形在边缘为中等高度时具有高度的转换功能。然而, 非常稠密的图形以及完全连接的图形没有被转换功能。有趣的是, 加权连接的图形没有观察到这种行为, 除非图形的边缘非常低, 否则这些图形总是被转换功能。