An Efficient Sampling Algorithm for Network Motif Detection. Issue 3 (3rd July 2018)

• Record Type: Journal Article
• Authors: Chen, Yinghan; Chen, Yuguo
• Is Part Of: Journal of computational and graphical statistics. Volume 27:Issue 3(2018)
• Page Start: 503
• Page End: 515
• Publication Date: 2018-07-03
• Subjects: Motif detection -- Sequential importance sampling -- Subgraph concentration; Mathematical statistics -- Data processing -- Periodicals; Mathematical statistics -- Graphic methods -- Periodicals; 519.50285
• DOI: 10.1080/10618600.2017.1391696
• Languages: English
• ISSNs: 1061-8600

Abstract

ABSTRACT: We propose a sequential importance sampling strategy to estimate subgraph frequencies and detect network motifs. The method is developed by sampling subgraphs sequentially node by node using a carefully chosen proposal distribution. Viewing the subgraphs as rooted trees, we propose a recursive formula that approximates the number of subgraphs containing a particular node or set of nodes. The proposal used to sample nodes is proportional to this estimated number of subgraphs. The method generates subgraphs from a distribution close to uniform, and performs better than competing methods. We apply the method to four real-world networks and demonstrate outstanding performance in practical examples. Supplemental materials for the article are available online.