0.25
0.5
0.75
1.25
1.5
1.75
2
A space efficient streaming algorithm for triangle counting using the birthday paradox
Published on Sep 27, 20134106 Views
We design a space efficient algorithm that approximates the transitivity (global clustering coefficient) and total triangle count with only a single pass through a graph given as a stream of edges. Ou
Related categories
Chapter list
A space efficient streaming algorithm for triangle counting using the birthday paradox00:00
Real-world graphs: An Example00:13
Real-world graphs00:51
Transitivity: Triangle “density” - 101:40
Transitivity: Triangle “density” - 202:04
Transitivity: Triangle “density” - 302:11
Transitivity: Triangle “density” - 402:27
Transitivity: Triangle “density” - 502:36
Why Count Triangles in Graphs?02:55
Graph as stream of edges - 103:19
Graph as stream of edges - 203:56
Graph as stream of edges - 304:25
Graph as stream of edges - 404:29
Graph as stream of edges - 504:32
Graph as stream of edges - 604:34
Graph as stream of edges - 704:59
Graph as stream of edges - 805:00
Graph as stream of edges - 905:01
Graph as stream of edges - 1005:06
Graph as stream of edges - 1105:07
Graph as stream of edges - 1205:08
Our Contributions : Theoretical05:15
Our Contributions : Practical05:54
Data Structures of the Algorithm07:07
The Algorithm - 108:50
The Algorithm - 209:15
The Algorithm - 309:43
The Birthday Paradox to Rescue09:58
Experimental Results10:56
Our Algorithm vs Buriol et al11:03
Accuracy of Transitivity Estimate12:20
Accuracy of Transitivity Estimate12:53
Convergence of Estimates13:26
Future Work13:45