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
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) 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 -- Tiago de Paula Peixoto <tiago@skewed.de>
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) 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
-- Tiago de Paula Peixoto <tiago@skewed.de>
_______________________________________________ graph-tool mailing list graph-tool@skewed.de https://lists.skewed.de/mailman/listinfo/graph-tool
On 04.04.2016 14:13, Stephen Bonner wrote:
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?
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 -- Tiago de Paula Peixoto <tiago@skewed.de>
participants (2)
-
Stephen Bonner -
Tiago de Paula Peixoto