文章基本信息

标题：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