vasia/gelly-streaming

Exact global and local triangle count

vasia opened this issue · 0 comments

vasia commented

We can use a modified version of the Triest-Base algorithm from this paper to compute exact global and local triangle counts. The algorithm requires storing the complete graph in memory plus the counters and it requires one neighborhood set intersection per edge.
We should look into:

  • efficient neighborhood representations
  • algorithms for efficient neighborhood intersection, e.g. keep neighborhoods sorted and use binary search if one of them is much smaller than the other
  • a version of the algorithm using windows to batch together multiple intersections.