Counting Graphlets Approximately by Random Sampling

The Hong Kong University of Science and Technology
Department of Computer Science and Engineering

Final Year Thesis Oral Defense

Title: "Counting Graphlets Approximately by Random Sampling"

by

YIP Chi Hoi

Abstract:

Counting the number of graphlets with a certain pattern in a large graph 
is a fundamental problem in graph mining, which has been extensively 
studied in both theory and practice. Since exact counting is 
time-consuming and often unnecessary, the problem of approximated counting 
becomes increasingly important.

In this thesis, we first explore the pattern of standard techniques using 
approximation algorithms based on random sampling. With the pattern, we 
know what we are aiming to optimize is to minimize the number of potential 
candidates. Then, to give an upper bound of the size of candidates, we 
introduce the entropy method and then prove the AGM bound. Finally, using 
the AGM bound, we come up with an algorithm with running time 
$O(\frac{m^{\rho^*}}{t})$, where $m$ is the number of edges of the graph, 
$t$ is the actual size of graphlets, and $\rho^*$ is the fractional edge 
cover of the given graphlet.


Date            : 1 May 2019 (Wednesday)

Time            : 15:40 - 16:20

Venue           : Room 2405 (near lifts 17/18), HKUST

Advisor         : Dr. YI Ke

2nd Reader      : Prof. DING Cunsheng