Generalization of transitivity to directed graphs

[vtraag]

In #907 the issue was raised that the current implementation of transitivity may yield incorrect results on directed graphs and multigraphs. That issue was addressed in #1217 by simply enforcing the input to be simple and undirected.

It would be more desirable to create a proper implementation of transitivity for directed graphs.

[stale]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.

[szhorvat]

It would be more desirable to create a proper implementation of transitivity for directed graphs.

Relevant reference:

• https://journals.aps.org/pre/abstract/10.1103/PhysRevE.76.026107

[aj2duncan]

There is another publication https://www.sciencedirect.com/science/article/abs/pii/S096007791730509X?via%3Dihub (also available on arXiv and the authors have written an R package - Directed Clustering which implements both methods. Hope this helps the conversation.

[szhorvat]

It would be useful if someone could write a small summary of the various approaches, their usage in practice, advantages and disadvantages, etc. It is clear that there are many different possible approached. It is not reasonable to just pick one and call it "the" directed clustering coefficient in igraph. The paper I linked (Fagiolo) presents not just one definition, but a framework to define various types of directed clusterings. Clemente and Grassi seem to be saying that Fagiolo's definitions have issues with weights in practical usage and propose modifications.

In this context Fagiolo ([24]) attempts to bridge different approaches (proposed in [21], [25]) in order to present a unifying framework for computing local clustering for weighted directed networks (WDN). In addition to the measures already discussed in [21], [25], the coefficient proposed in [24] allows to explicitly account for directed and weighted links and to define a specific clustering coefficient for any type of triangle pattern. However, as partially2 noticed also in [26], this coefficient does not properly account for the strength of a node, resulting in a clustering coefficient too affected by weights.

@aj2duncan If you already have some familiarity with the topic, would you mind giving a short summary?

[aj2duncan]

I can try... pretty busy at the moment but will try to get something together as soon as I can.

[szhorvat]

Thank you! If you do find the time, it would be quite useful, but of course it is up to you.

You can also post on https://igraph.discourse.group/ which is more discussion friendly, and importantly: it supports math ($x^2$, etc.)

[szarnyasg]

Followup from the discussion at the Implementing the LDBC Graphalytics benchmark thread: this benchmark needs directed LCC, defined in its specification as follows:

IMHO this directed definition is quite cumbersome. To mitigate this, there are two examples to clarify the expected results, see example 1, example 2

@szhorvat wrote:

It is not reasonable to just pick one and call it "the" directed clustering coefficient in igraph.

I completely agree.

[ntamas]

The way I see it it seems like we should have some kind of an igraph_transitivity_local_directed() function with an extra igraph_directed_transitivity_method_t enum argument that allows the user to select a particular variant for the directed transitivity. The one outlined above could then be one possible variant and it could be used in the LDBC Graphalytics benchmark, and we could add new methods any time without breaking the API (assuming that new methods don't have additional arguments).

Is anyone familiar with any alternative proposals for directed transitivity? Personally I am not, but I can start looking into the topic from September.

[szhorvat]

The paper I linked above discusses several alternatives.