Abstract
The problem of our interest is counting k-node cycles and other subgraphs containing such cycles. Practical performance of exact counting methods is good only on small k value. The linear-time pre-processing required by state-of-art algorithms is also hindering flexible application on large graphs in reality. We propose a new sublinear-time algorithm, based on multilayer random sampling, for counting k-node cycles and other subgraphs. The algorithm will be shown to achieve a constant-error estimate of cycle counts t in expected time O(m^k/2/t), where m is the number of edges. This thesis includes review for MOSS5 and color-coding algorithms, which are implemented and used in our experiments for performance comparison.