Triangle Counting

graph-tool
1

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()
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)
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

2

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)
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

3

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

attachment.html (5.08 KB)

4

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