  Counting the frequencies of 3-, 4-, and 5-node undirected motifs (also know
as graphlets) is widely used for understanding complex networks such as social
and biology networks. However, it is a great challenge to compute these metrics
for a large graph due to the intensive computation. Despite recent efforts to
count triangles (i.e., 3-node undirected motif counting), little attention has
been given to developing scalable tools that can be used to characterize 4- and
5-node motifs. In this paper, we develop computational efficient methods to
sample and count 4- and 5- node undirected motifs. Our methods provide unbiased
estimators of motif frequencies, and we derive simple and exact formulas for
the variances of the estimators. Moreover, our methods are designed to fit
vertex centric programming models, so they can be easily applied to current
graph computing systems such as Pregel and GraphLab. We conduct experiments on
a variety of real-word datasets, and experimental results show that our methods
are several orders of magnitude faster than the state-of-the-art methods under
the same estimation errors.
