University of Victoria (Canada)
Triangle counting and listing in directed and undirected graphs using single machines
Abstract
dc:description.abstractTriangle enumeration is an important element in graph analysis, and because of this it is a topic that has been studied extensively. Although the formulation is simple, for large networks the computation becomes challenging as we have to deal with memory limitation and efficiency. Many algorithms have been proposed to overcome these problems. Some use distributed computing, where the computation is distributed among many machines in a cluster. However, this approach has a high cost in terms of hardware resources and energy. In this thesis we studied triangle counting/listing algorithms for both directed and undirected graphs, and searched for methods to do the computation on a single machine. Through detailed analysis, we found some ways to improve the efficiency of the computation. Programs that implement the algorithms were built and tested on large networks with up to almost a billion nodes. The results were then analysed and discussed.
Degree
thesis:*- Level thesis:degree_level
- Master of Science M.Sc.
- Department thesis:degree_department
- Department of Computer Science
- Year dc:date.issued
- 2018
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Santoso, Yudi
- Advisors dc:contributor.supervisor
-
- Thomo, Alex
- Srinivasan, Venkatesh
Subjects
dc:subject × 4Rights
dc:rights- Statement dc:rights
-
- Available to the World Wide Web
- Language dc:language.iso
- en, English
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- http://hdl.handle.net/1828/9902