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[0] * (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

On 2 Apr 2016, at 15:39, Tiago de Paula Peixoto <tiago@skewed.de> wrote:

On 01.04.2016 15:51, Stephen Bonner wrote:
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)[0] * (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()
v1 = triangle.add_vertex()
v2 = triangle.add_vertex()
v3 = triangle.add_vertex()
e = triangle.add_edge(v1, v2)
e = triangle.add_edge(v1, v3)
e = triangle.add_edge(v3, v2)

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?


Tiago de Paula Peixoto <tiago@skewed.de>

graph-tool mailing list