The idemetric property: when most distances are (almost) the same
The idemetric property: when most distances are (almost) the same
复制标题
idemetric 属性：当大多数距离（几乎）相同时
DOI：
10.1098/rspa.2018.0283
复制
发表时间：
2018-04
期刊：
影响因子：
--
通讯作者：
Tim Roughgarden
中科院分区：
文献类型：
--
作者：
George Barmpalias;Peng Huang;Andrew Lewis-Pye;Angsheng Li;Xuechen Li;Yicheng Pan;Tim Roughgarden
我们引入了等距属性，它形式化了图中大多数节点之间具有相似距离的想法，并且在小世界网络模型中是相当标准的。模合理的稀疏性假设，然后我们能够证明，一个强形式的理想性实际上是等价于一个非常弱的扩展条件（）。这提供了一种直接的方法来提供简短的证明，证明小世界网络模型（如Watts-Strogatz模型）是强等距的（对于广泛的参数），也提供了进一步的证据，证明等距是一个共同的属性。然后，我们考虑如何满足的理想属性是相关的算法设计。对于等度图，我们观察到，例如，一个单一的广度优先搜索提供了一个解决方案的所有对最短路径问题，只要一个准备接受的路径是拉伸接近2的概率很高。由于我们能够证明克莱因伯格的模型是等距的，这些结果与克莱因伯格关于寻找短路径的有效分散算法的众所周知的否定结果形成了很好的对比：对于与克莱因伯格的否定结果完全相同的模型，我们能够证明，如果允许合理的预处理，则存在非常有效的（和分散的）算法。对于确定性的分布式路由算法，我们也能够得到的结果证明，更少的路由信息需要的等距图比在最坏的情况下，以实现拉伸小于3的高概率：而Ω（n2）路由信息需要在最坏的情况下，拉伸严格小于3几乎所有的对，等距图所需的总路由信息是O（nlog（n））。
We introduce the idemetric property, which formalizes the idea that most nodes in a graph have similar distances between them, and which turns out to be quite standard amongst small-world network models. Modulo reasonable sparsity assumptions, we are then able to show that a strong form of idemetricity is actually equivalent to a very weak expander condition (PUMP). This provides a direct way of providing short proofs that small-world network models such as the Watts-Strogatz model are strongly idemetric (for a wide range of parameters), and also provides further evidence that being idemetric is a common property. We then consider how satisfaction of the idemetric property is relevant to algorithm design. For idemetric graphs, we observe, for example, that a single breadth-first search provides a solution to the all-pairs shortest paths problem, so long as one is prepared to accept paths which are of stretch close to 2 with high probability. Since we are able to show that Kleinberg's model is idemetric, these results contrast nicely with the well known negative results of Kleinberg concerning efficient decentralized algorithms for finding short paths: for precisely the same model as Kleinberg's negative results hold, we are able to show that very efficient (and decentralized) algorithms exist if one allows for reasonable preprocessing. For deterministic distributed routing algorithms we are also able to obtain results proving that less routing information is required for idemetric graphs than in the worst case in order to achieve stretch less than 3 with high probability: while Ω(n2) routing information is required in the worst case for stretch strictly less than 3 on almost all pairs, for idemetric graphs the total routing information required is O(nlog(n)).
登录
查看更多内容
DOI：
--
发表时间：
2008-05
期刊：
--
影响因子：
--
作者：
R. Ladner;Cynthia Dwork
通讯作者：
R. Ladner;Cynthia Dwork
DOI：
10.1017/9781316779422
发表时间：
2016
期刊：
--
影响因子：
--
作者：
R. Hofstad
通讯作者：
R. Hofstad
影响因子：
2.5
作者：
WARSHALL, S
通讯作者：
WARSHALL, S
DOI：
10.1016/j.jcss.2021.11.003
发表时间：
2016-12
期刊：
J. Comput. Syst. Sci.
影响因子：
--
作者：
K. Bringmann;Ralph Keusch;J. Lengler;Yannic Maus;A. R. Molla
通讯作者：
K. Bringmann;Ralph Keusch;J. Lengler;Yannic Maus;A. R. Molla
影响因子：
1.2
作者：
Norros, I;Reittu, H
通讯作者：
Reittu, H