Counting cycles by random sampling : theory and practice
by Junhong Cao
THESIS
2019
M.Phil. Computer Science and Engineering
ix, 49 pages : illustrations ; 30 cm
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(mk/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.
Post a Comment