Back to search

University of Victoria (Canada)

Fast and scalable triangle counting in graph streams: the hybrid approach

Abstract

dc:description.abstract

Triangle counting is a major graph problem with several applications in social network analysis, anomaly detection, etc. A considerable amount of work has contributed to approximately computing the global triangle counts using several computational models. One of the most popular streaming models considered is Edge Streaming in which the edges arrive in the form of a graph stream. We categorize the existing literature into two categories: Fixed Memory (FM) approach, and Fixed Probability (FP) approach. As the size of the graphs grows, several challenges arise such as memory space limitations, and prohibitively long running time. Therefore, both FM and FP categories exhibit some limitations. FP algorithms fail to scale for massive graphs. We identified a limitation of FM category $i.e.$ FM algorithms have higher computational time than their FP variants. In this work, we present a new category called the Hybrid approach that overcomes the limitations of both FM and FP approaches. We present two new algorithms that belong to the hybrid category: Neighbourhood Hybrid Multisampling (NHMS) and Triest/ThinkD Hybrid Sampling (THS) for estimating the number of global triangles in graphs. These algorithms are highly scalable and have better running time than FM and FP variants. We experimentally show that both NHMS and THS outperform state-of-the-art algorithms in space-efficient environments.

Degree

thesis:*
Level thesis:degree_level
Master of Science M.Sc.
Department thesis:degree_department
Department of Computer Science
Year dc:date.issued
2020

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Singh, Paramvir
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/12445

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

Singh, Paramvir. Fast and scalable triangle counting in graph streams: the hybrid approach. Master of Science M.Sc. thesis, 2020. http://hdl.handle.net/1828/12445