COUNTING CYCLES BY RANDOM SAMPLING: THEORY AND PRACTICE

MPhil Thesis Defence


Title: "COUNTING CYCLES BY RANDOM SAMPLING: THEORY AND PRACTICE"

By

Mr. Junhong CAO


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.


Date:			Monday, 19 August 2019

Time:			3:00pm - 5:00pm

Venue:			Room 4475
 			Lifts 25/26

Committee Members:	Prof. Ke Yi (Supervisor)
 			Prof. Cunsheng Ding (Chairperson)
 			Prof. Fangzhen Lin


**** ALL are Welcome ****