Back to search

University of Victoria (Canada)

Triangle counting and listing in directed and undirected graphs using single machines

Abstract

dc:description.abstract

Triangle 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 × 4

Rights

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

Chain of custody

source
Harvested from
University of Victoria (Canada)
Base URL
dspace.library.uvic.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Santoso, Yudi. Triangle counting and listing in directed and undirected graphs using single machines. Master of Science M.Sc. thesis, 2018. http://hdl.handle.net/1828/9902