A Survey on Triangle Listing and Counting

PhD Qualifying Examination


Title: "A Survey on Triangle Listing and Counting"

by

Mr. Bin WU


Abstract:

Graphs are a ubiquitous form to represent and model complex relations between 
entities in various areas, including biochemistry, information systems and 
social networks analysis. In recent years, with the explosion of available data 
(e.g. social networks), it’s very common to deal with a complex graph which has 
millions of nodes and billions of edges. To uncover the hidden structure and 
extract relevant information from these massive graphs, small dense subgraphs 
occurring in the graphs become a basic and valuable tool.  Specifically, 
triangle is one of the most fundamental small subgraphs: it is the shortest 
non-trivial cycle and the smallest non-trivial clique. The problem of triangle 
listing (or triangle counting) in a simple undirected graph is to list (or 
compute the number of) all triangles. Thereby, listing and counting triangles 
appears as a key issue from a theoretical point of view as well as for 
practical purposes.

The main intention of this survey is to present a general review and analysis 
of the existing triangle listing and counting algorithms under the following 
computational models: the traditional RAM model, the I/O model, the data stream 
model, and the MapReduce model. This survey will start with some preliminary 
knowledge, and then algorithms in different models will be discussed 
subsequently, as well as relevant lower bounds. At last, some future directions 
of research will be proposed.


Date:			Wednesday, 22 January 2014

Time:                   10:00am - 12:00noon

Venue:                  Room 3501
                         lifts 25/26

Committee Members:	Dr. Ke Yi (Supervisor)
 			Prof. Mordecai Golin (Chairperson)
 			Dr. Sunil Arya
 			Prof. Siu-Wing Cheng


**** ALL are Welcome ****