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

文章基本信息

  • 标题:Efficient Embedding of Scale-Free Graphs in the Hyperbolic Plane
  • 本地全文:下载
  • 作者:Thomas Bl{\"a}sius ; Tobias Friedrich ; Anton Krohmer
  • 期刊名称:LIPIcs : Leibniz International Proceedings in Informatics
  • 电子版ISSN:1868-8969
  • 出版年度:2016
  • 卷号:57
  • 页码:16:1-16:18
  • DOI:10.4230/LIPIcs.ESA.2016.16
  • 出版社:Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
  • 摘要:Hyperbolic geometry appears to be intrinsic in many large real networks. We construct and implement a new maximum likelihood estimation algorithm that embeds scale-free graphs in the hyperbolic space. All previous approaches of similar embedding algorithms require a runtime of Omega(n^2). Our algorithm achieves quasilinear runtime, which makes it the first algorithm that can embed networks with hundreds of thousands of nodes in less than one hour. We demonstrate the performance of our algorithm on artificial and real networks. In all typical metrics like Log-likelihood and greedy routing our algorithm discovers embeddings that are very close to the ground truth.
  • 关键词:hyperbolic random graphs; embedding; power-law graphs; hyperbolic plane
国家哲学社会科学文献中心版权所有