twitter/cassovary — pull request #62 by szymonm (2014-04-03 13:51:09+00:00)
Title: triangle count - alpha version #49

Hi, I implemented alpha version of triangle counting as specified here: http://arxiv.org/pdf/1212.2264v3.pdf

The problem is, the algorithm isn't very exact when graphs are small. Thus, I failed writing good tests for that. I've tried with random graph with almost no edges (avgDegree = 2) and that works fine. When I verify the algorithm on random graph with 2000 nodes and avgDegree = 40, (with precision 20%) it often fails. Same with 50 nodes and complete graph. For smaller number of nodes, it is even less stable. And for this, tests take too long.

For now the implementation works assuming that a graph is mutual.