igraph-help
[Top][All Lists]

Re: [igraph] What exactly does igraph_transitivity_undirected() compute

 From: Gábor Csárdi Subject: Re: [igraph] What exactly does igraph_transitivity_undirected() compute for directed graphs? Date: Mon, 7 Dec 2015 14:25:21 +0000

```On Mon, Dec 7, 2015 at 1:28 PM, Szabolcs Horvát <address@hidden> wrote:
[...]
> Do you think a patch that converts directed graphs to undirected
> simple graphs before computing the local clustering coefficient would
> be appropriate here?

Converting the whole graph is not a good solution, because that is
O(n+m), and local transitivity is O(1).

Converting the graph locally, at the queried vertex, is maybe a better
idea, but also harder to implement. So we might as well modify the
local transitivity code.

Gabor

> On 7 December 2015 at 13:16, Gábor Csárdi <address@hidden> wrote:
>> I am not sure if it is defined. I guess this is just a case when the
>> behavior is not defined for multi-graphs.
>>
>> Gabor
>>
>> On Mon, Dec 7, 2015 at 12:14 PM, Szabolcs Horvát <address@hidden> wrote:
>>> Thank you for the explanation.
>>>
>>> Could you elaborate a bit on how igraph defines the local clustering
>>> coefficient when multiple (parallel) edges are present?
>>>
>>> On 7 December 2015 at 12:56, Gábor Csárdi <address@hidden> wrote:
>>>> It's because of the multiple edges in the first graph. I.e.:
>>>>
>>>>> transitivity(as.undirected(g, mode = "each"),"local")
>>>> [1] 0.3333333 0.3333333 1.0000000
>>>>
>>>> Gabor
>>>>
>>>> On Mon, Dec 7, 2015 at 10:05 AM, Szabolcs Horvát <address@hidden> wrote:
>>>>> Hello,
>>>>>
>>>>> What precisely does igraph_transitivity_undirected() compute for
>>>>> directed graphs?
>>>>>
>>>>> The C documentation states that
>>>>>
>>>>> "Directed graphs are considered as undirected ones."
>>>>>
>>>>> but this is not exactly the case.
>>>>>
>>>>> With an example using the R interface (for simplicity),
>>>>>
>>>>>> g<-make_graph(c(1,2, 2,1, 2,3, 3,1))
>>>>>> transitivity(g,"local")
>>>>> [1] 0.3333333 0.3333333 1.0000000
>>>>>
>>>>>> transitivity(as.undirected(g),"local")
>>>>> [1] 1 1 1
>>>>>
>>>>> Can someone clarify what precisely is computed in the directed case?
>>>>>
>>>>> Szabolcs
>>>>>
>>>>> _______________________________________________
>>>>> igraph-help mailing list
>>>>> https://lists.nongnu.org/mailman/listinfo/igraph-help
>>>>
>>>> _______________________________________________
>>>> igraph-help mailing list
>>>> https://lists.nongnu.org/mailman/listinfo/igraph-help
>>>
>>> _______________________________________________
>>> igraph-help mailing list
>>> https://lists.nongnu.org/mailman/listinfo/igraph-help
>>
>> _______________________________________________
>> igraph-help mailing list