Title: An efficient sampling algorithm for network motif detection
Authors: Yinghan Chen - University of Nevada, Reno (United States) [presenting]
Yuguo Chen - University of Illinois at Urbana-Champaign (United States)
Abstract: Network motifs are substructures that appear significantly more often in a given network than in random networks. Motif detection is crucial for discovering new characteristics in biological, developmental, and social networks. 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.