LIPIcs.WABI.2018.7.pdf
- Filesize: 479 kB
- 13 pages
Document
A Dynamic Algorithm for Network Propagation
Authors
Barak Sternberg 
,
-
Part of:
Volume:
18th International Workshop on Algorithms in Bioinformatics (WABI 2018)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Workshop on Algorithms in Bioinformatics (WABI) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2018-08-02
File
Document Identifiers
Author Details
Cite As Get BibTex
Barak Sternberg and Roded Sharan. A Dynamic Algorithm for Network Propagation. In 18th International Workshop on Algorithms in Bioinformatics (WABI 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 113, pp. 7:1-7:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.WABI.2018.7
Abstract
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.
Subject Classification
ACM Subject Classification
- Theory of computation → Dynamic graph algorithms
Keywords
- Network propagation
- Dynamic graph algorithm
- protein-protein interaction network
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Amy N. Langville and Carl D. Meyer. Deeper Inside PageRank. Internet Mathematics, 1(3), jan 2004. URL: http://dx.doi.org/10.1080/15427951.2004.10129091.
- Dengyong Zhou, Olivier Bousquet, Thomas N. Lal, Jason Weston, and Bernhard Scholkopf. Learning with Local and Global Consistency. In Proceedings of the 16th International Conference on Neural Information Processing Systems, pages 321-328. MIT Press, 2004. URL: http://papers.nips.cc/paper/2506-learning-with-local-and-global-consistency.pdf.
- Glen Jeh and Jennifer Widom. Scaling Personalized Web Search. In Proceedings of the Twelfth International World Wide Web Conference, WWW 2003, Budapest, Hungary, May 20-24, 2003, WWW '03, pages 271-279, New York, NY, USA, 2003. ACM. URL: http://dx.doi.org/10.1145/775152.775191.
- Gregorio Alanis-Lobato, Miguel A. Andrade-Navarro, and Martin H. Schaefer. HIPPIE v2.0: enhancing meaningfulness and reliability of protein–protein interaction networks. Nucleic Acids Research, 45(D1):D408-D414, jan 2017. URL: http://dx.doi.org/10.1093/nar/gkw985.
- Hongyang Zhang, Peter Lofgren, and Ashish Goel. Approximate Personalized PageRank on Dynamic Graphs. arXiv:1603.07796 [cs], 2016. arXiv: 1603.07796. URL: http://arxiv.org/abs/1603.07796.
- Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. The PageRank Citation Ranking: Bringing Order to the Web., nov 1999. URL: http://ilpubs.stanford.edu:8090/422/.
- Lenore Cowen, Trey Ideker, Benjamin J. Raphael, and Roded Sharan. Network propagation: a universal amplifier of genetic associations. Nature Reviews. Genetics, 18(9):551-562, 2017. URL: http://dx.doi.org/10.1038/nrg.2017.38.
- Minji Yoon, WooJeong Jin, and U Kang. Fast and Accurate Random Walk with Restart on Dynamic Graphs with Guarantees. arXiv:1712.00595 [cs], 2017. arXiv: 1712.00595. URL: http://arxiv.org/abs/1712.00595.
- Monica Bianchini, Marco Gori, and Franco Scarselli. PageRank and Web communities. In Proceedings IEEE/WIC International Conference on Web Intelligence (WI 2003), pages 365-371, oct 2003. URL: http://dx.doi.org/10.1109/WI.2003.1241217.
- Naoto Ohsaka, Takanori Maehara, and Ken-ichi Kawarabayashi. Efficient PageRank Tracking in Evolving Networks. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Sydney, NSW, Australia, August 10-13, 2015, KDD '15, pages 875-884, New York, NY, USA, 2015. ACM. URL: http://dx.doi.org/10.1145/2783258.2783297.
- Oron Vanunu, Oded Magger, Eytan Ruppin, Tomer Shlomi, and Roded Sharan. Associating Genes and Protein Complexes with Disease via Network Propagation. PLOS Computational Biology, 6(1):e1000641, 2010. URL: http://dx.doi.org/10.1371/journal.pcbi.1000641.
- Ortal Shnaps, Eyal Perry, Dana Silverbush, and Roded Sharan. Inference of Personalized Drug Targets via Network Propagation. Pacific Symposium on Biocomputing. Pacific Symposium on Biocomputing, 21:156-67, 2016. URL: https://www.semanticscholar.org/paper/Inference-of-Personalized-Drug-Targets-via-Network-Shnaps-Perry/b57104bd662ffeb95bb150d00adb381caffce013.
- Peter Lofgren, Siddhartha Banerjee, and Ashish Goel. Bidirectional PageRank Estimation: From Average-Case to Worst-Case. In Algorithms and Models for the Web Graph - 12th International Workshop, WAW 2015, Eindhoven, The Netherlands, December 10-11, 2015, Proceedings, WAW 2015, pages 164-176, New York, NY, USA, 2015. Springer-Verlag New York, Inc. URL: http://dx.doi.org/10.1007/978-3-319-26784-5_13.
- Sushant Patkar, Assaf Magen, Roded Sharan, and Sridhar Hannenhalli. A network diffusion approach to inferring sample-specific function reveals functional changes associated with breast cancer. PLoS Computational Biology 13(11): e1005793, in press, 13, nov 2017. URL: http://dx.doi.org/10.1371/journal.pcbi.1005793.
- Yomtov Almozlino, Nir Atias, Dana Silverbush, and Roded Sharan. ANAT 2.0: reconstructing functional protein subnetworks. BMC bioinformatics, 18(1):495, 2017. URL: http://dx.doi.org/10.1186/s12859-017-1932-1.