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

文章基本信息

  • 标题:A Dynamic Algorithm for Network Propagation
  • 本地全文:下载
  • 作者:Barak Sternberg ; Roded Sharan
  • 期刊名称:LIPIcs : Leibniz International Proceedings in Informatics
  • 电子版ISSN:1868-8969
  • 出版年度:2018
  • 卷号:113
  • 页码:1-13
  • DOI:10.4230/LIPIcs.WABI.2018.7
  • 出版社:Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
  • 摘要:Network propagation is a powerful transformation that amplifies signal-to-noise ratio in biological and other data. To date, most of its applications in the biological domain employed standard techniques for its computation that require O(m) time for a network with n vertices and m edges. When applied in a dynamic setting where the network is constantly modified, the cost of these computations becomes prohibitive. Here we study, for the first time in the biological context, the complexity of dynamic algorithms for network propagation. We develop a vertex decremental algorithm that is motivated by various biological applications and can maintain propagation scores over general weights at an amortized cost of O(m/(n^{1/4})) per update. In application to real networks, the dynamic algorithm achieves significant, 50- to 100-fold, speedups over conventional static methods for network propagation, demonstrating its great potential in practice.
  • 关键词:Network propagation; Dynamic graph algorithm; protein-protein interaction network
国家哲学社会科学文献中心版权所有