Abstract:
|
The major task of detection network motif is to count the frequencies of subgraph patterns. In this paper we propose a new sequential importance sampling method to estimate the frequency of subgraphs. The method is based on sampling subgraphs node by node with proposal weights. By viewing subgraph as rooted trees, we propose a recursive formula to approximate the number of subgraphs that contains a specific node, and the proposal weight is in proportion to this approximate number. The proposal distribution of our method is closer to uniform sampling than previous proposal from edge sampling method, and it gives a larger effective sample size. The results of motifs are presented in two biological networks and two social networks.
|