Comparison with vertex cover method

[LucaCappelletti94]

Hi @lecfab!

A while ago, I implemented a parallel version of this method based on Vertex cover.

You can find a jupyter notebook I wrote detailing the method and its performance here.

In my implementation, it is possible to count the triangles in graphs like clueweb09 on my desktop (12 cores, 128GB ram) in about eight hours in the penultimate version (the one in the notebook) and 4 hours in the current one.

Would you like to compare the two methods? The algorithm I implemented could be sleeker, and I'd be happy to learn and implement something faster.

Luca

[lecfab]

Dear Luca,
Thanks for writing and sorry for the delay.

I was not aware of the VC technique to avoid checking all the adjacency lists. This seems very clever to accelerate the counting, and it reminds me of a colouring technique used for clique-listing in Li et al. 2020 .
In my work, we want to list triangles as opposed to count them for the clustering coefficient. This is only a slight difference but it has some consequences:

• some methods for counting do not apply to listing, for instance those that use matrix multiplication.
• in the listing, we want to avoid repeated triplets like (u,v,w), (v,w,u), (u,w,v)... and only keep one. While in the paper you provided, one challenge is actually to count all 6 triplets.

The current technique I use is based on orderings (such as degeneracy) that "direct" the edges, so that if u<v<w, only the intersection of u and v will show w. I think it has the same effect as finding a VC that would contain u and v but not w. Moreover, the linear greedy algorithm to find a VC is also based on orderings, and possibly the degeneracy one.
So in the end i wonder if the VC technique and the ordering technique do the same thing mathematically speaking.
What do you think?

Also, i'm downloading clueweb09 to see roughly the time that it takes with my code! I'd be happy to discuss more about all that, maybe by email?

Sorry again for the late reply, and enjoy the week,
Fabrice

[LucaCappelletti94]

Sure, I am replying to the email. Thanks!