Please use this identifier to cite or link to this item: http://localhost/handle/Hannan/583536
Title: Counting Triangles in Large Graphs by Random Sampling
Authors: Bin Wu;Ke Yi;Zhenguo Li
subject: random sampling|Triangle counting
Year: 2016
Publisher: IEEE
Abstract: The problem of counting triangles in graphs has been well studied in the literature. However, all existing algorithms, exact or approximate, spend at least linear time in the size of the graph (except a recent theoretical result), which can be prohibitive on today's large graphs. Nevertheless, we observe that the ideas in many existing triangle counting algorithms can be coupled with random sampling to yield potentially sublinear-time algorithms that return an approximation of the triangle count without looking at the whole graph. This paper makes these random sampling algorithms more explicit, and presents an experimental and analytical comparison of different approaches, identifying the best performers among a number of candidates.
Description: 
URI: http://localhost/handle/Hannan/165222
http://localhost/handle/Hannan/583536
ISSN: 1041-4347
volume: 28
issue: 8
Appears in Collections:2016

Files in This Item:
File Description SizeFormat 
7457266.pdf705.23 kBAdobe PDFThumbnail
Preview File
Title: Counting Triangles in Large Graphs by Random Sampling
Authors: Bin Wu;Ke Yi;Zhenguo Li
subject: random sampling|Triangle counting
Year: 2016
Publisher: IEEE
Abstract: The problem of counting triangles in graphs has been well studied in the literature. However, all existing algorithms, exact or approximate, spend at least linear time in the size of the graph (except a recent theoretical result), which can be prohibitive on today's large graphs. Nevertheless, we observe that the ideas in many existing triangle counting algorithms can be coupled with random sampling to yield potentially sublinear-time algorithms that return an approximation of the triangle count without looking at the whole graph. This paper makes these random sampling algorithms more explicit, and presents an experimental and analytical comparison of different approaches, identifying the best performers among a number of candidates.
Description: 
URI: http://localhost/handle/Hannan/165222
http://localhost/handle/Hannan/583536
ISSN: 1041-4347
volume: 28
issue: 8
Appears in Collections:2016

Files in This Item:
File Description SizeFormat 
7457266.pdf705.23 kBAdobe PDFThumbnail
Preview File
Title: Counting Triangles in Large Graphs by Random Sampling
Authors: Bin Wu;Ke Yi;Zhenguo Li
subject: random sampling|Triangle counting
Year: 2016
Publisher: IEEE
Abstract: The problem of counting triangles in graphs has been well studied in the literature. However, all existing algorithms, exact or approximate, spend at least linear time in the size of the graph (except a recent theoretical result), which can be prohibitive on today's large graphs. Nevertheless, we observe that the ideas in many existing triangle counting algorithms can be coupled with random sampling to yield potentially sublinear-time algorithms that return an approximation of the triangle count without looking at the whole graph. This paper makes these random sampling algorithms more explicit, and presents an experimental and analytical comparison of different approaches, identifying the best performers among a number of candidates.
Description: 
URI: http://localhost/handle/Hannan/165222
http://localhost/handle/Hannan/583536
ISSN: 1041-4347
volume: 28
issue: 8
Appears in Collections:2016

Files in This Item:
File Description SizeFormat 
7457266.pdf705.23 kBAdobe PDFThumbnail
Preview File