Transitivity calculation and node ordering

Development
1

@Gabor I am working with the transitivity calculation code and trying to make sure it does not misbehave for multigraphs (or directed graphs with reciprocal edges).

It appears that several of the functions order the nodes by decreasing degree before processing them. Here is one example (global transitivity):

And here is another one:

However, all this ordering does not seem to be necessary for the function to work correctly. Am I missing something here? Was there a performance benefit to the ordering? I cannot see one when I do some basic benchmarking.

The reason I need to deal with this is that there is a mismatch between how the degrees and neighbours are computed for multigraphs. The degree calculation takes multi-edges and self-loops into account while the neighbour calculation does not. I have already corrected such mismatches elsewhere in the code, but in this particular case it does not seem to matter at all, as it simple affects the order in which nodes are processed, which does not seem to matter anyway. I want to make sure that I did not miss anything before going forward.

2

See Support multigraphs with transitivity calculations by szhorvat · Pull Request #1790 · igraph/igraph · GitHub

3

Try some very skewed graphs where the high degree nodes come last.

But if you don’t see any difference, then maybe it was premature optimization.

Or some update, e.g. using the adj lists, made it faster without the ordering.

4

I tried that, although perhaps I didn’t make it skewed enough. I also tried removing the ordering entirely, and the result was correct. By reading the code, the result should be correct regardless of ordering.

I’ll improve the benchmarks a bit to see if any difference is revealed.

5

I was wrong that the ordering makes no difference in performance. I was using the wrong benchmarks. See the linked PR for an update. It can cause either a slowdown or a speedup.