# Triangle Counting

Is there a primitive function for counting triangles in graph-tool?

Currently i am explicitly creating a triangle graph and then using the motif function to search for this graph. -

triangle = Graph()
triangle.set_directed(False)

motifsgraph, num_triangles = motifs(tempG, 3, motif_list=[triangle])

Just wondering if there is a better way to do this as it is 1) slow and 2) turning up some strange results.

Many Thanks,

Rob

Is there a primitive function for counting triangles in graph-tool?

The closest one is global_clustering(), which returns:

3 x number of triangles / number of connected triples

the denominator is easy to compute from the degrees alone (the number of
triples a node with degree k participates is simply k(k-1)/2). Hence,
you can get the number of triangles with:

d = g.degree_property_map("out")
n_t = global_clustering(g) * (d.a * (d.a - 1) / 2) .sum() / 3

Currently i am explicitly creating a triangle graph and then using the motif function to search for this graph. -

triangle = Graph()
triangle.set_directed(False)

motifsgraph, num_triangles = motifs(tempG, 3, motif_list=[triangle])

Just wondering if there is a better way to do this as it is 1) slow and 2) turning up some strange results.

This should work too. What strange results are you seeing?

Best,
Tiago

Hi Tiago,

Thank you for your detailed reply, it cleared things up a lot! I would also like to thank you for your incredible work on graph-tool, its a great package!

Below is the code i now use to count the triangles -

# number of triangles
gc = global_clustering(tempG)
d = tempG.degree_property_map("total")
num_triangles = gc * (d.a * (d.a - 1) / 2).sum() / 3

My test dataset is the CA-HepPh network from SNAP - http://snap.stanford.edu/data/ca-HepPh.html

However i am not getting the reported number of triangles for the dataset which, according to SNAP, is - 3,358,499

However from the above graph-tool code i get - 13,434,795

Do you have any idea what might cause the discrepancy between the ground truth and the computed result?

Thanks again,

Stephen Bonner

attachment.html (5.08 KB)

Many SNAP datasets contain parallel edges, but apparently many of their
statistics ignore those. Graph-tool (correctly) incorporates them in the
triangle counting. If you remove the parallel edges (e.g. with
remove_parallel_edges()), you get the same triangle count as reported in
SNAP.

Best,
Tiago