首页    期刊浏览 2024年11月23日 星期六
登录注册

文章基本信息

  • 标题:Efficient Shortest Paths in Scale-Free Networks with Underlying Hyperbolic Geometry
  • 作者:Thomas Bl{\"a}sius ; Cedric Freiberger ; Tobias Friedrich
  • 期刊名称:LIPIcs : Leibniz International Proceedings in Informatics
  • 电子版ISSN:1868-8969
  • 出版年度:2018
  • 卷号:107
  • 页码:20:1-20:14
  • DOI:10.4230/LIPIcs.ICALP.2018.20
  • 出版社:Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
  • 摘要:A common way to accelerate shortest path algorithms on graphs is the use of a bidirectional search, which simultaneously explores the graph from the start and the destination. It has been observed recently that this strategy performs particularly well on scale-free real-world networks. Such networks typically have a heterogeneous degree distribution (e.g., a power-law distribution) and high clustering (i.e., vertices with a common neighbor are likely to be connected themselves). These two properties can be obtained by assuming an underlying hyperbolic geometry. To explain the observed behavior of the bidirectional search, we analyze its running time on hyperbolic random graphs and prove that it is {O~}(n^{2 - 1/alpha} + n^{1/(2 alpha)} + delta_{max}) with high probability, where alpha in (0.5, 1) controls the power-law exponent of the degree distribution, and delta_{max} is the maximum degree. This bound is sublinear, improving the obvious worst-case linear bound. Although our analysis depends on the underlying geometry, the algorithm itself is oblivious to it.
  • 关键词:random graphs; hyperbolic geometry; scale-free networks; bidirectional shortest path
Loading...
联系我们|关于我们|网站声明
国家哲学社会科学文献中心版权所有