igraph-help
[Top][All Lists]

## Re: [igraph] Transitivity

 From: Gábor Csárdi Subject: Re: [igraph] Transitivity Date: Tue, 20 Mar 2012 09:23:36 -0400

```I still cannot find it, but see the references here:
http://www.sciencedirect.com/science/article/pii/S0304397508005392
This seems to be about global transitivity, but it should be close.

G.

On Tue, Mar 20, 2012 at 9:16 AM, Moses Boudourides
> Gabor, I would appreciate if you could tell me more about that paper
> when you manage to find it.
>
> Thanks,
>
> --Moses
>
>
> On Tue, Mar 20, 2012 at 3:07 PM, Gábor Csárdi <address@hidden> wrote:
>> There are actually four different implementations in igraph for local
>> transitivity, see
>> Two of them are used, depending on the graph size.
>>
>> There was also a paper about different algorithms for calculating
>> transitivity, but I cannot find it now...
>>
>> Best,
>> Gabor
>>
>> On Mon, Mar 19, 2012 at 3:17 PM, Moses Boudourides
>>> I see. However, I'm wondering whether it would be faster to move along
>>> a spanning tree (derived from a search algorithm) in which fundamental
>>> cycles might be also marked (plus the fact that the computation of
>>> 2-paths over a tree is more direct). Has anybody proceeded in this
>>> way?
>>>
>>> --Moses
>>>
>>> On Mon, Mar 19, 2012 at 9:01 PM, Tamás Nepusz <address@hidden> wrote:
>>>>> Which algorithm do you use to compute transitivity?
>>>>
>>>> It is a simple exhaustive search, nothing fancy. Starting from the node
>>>> with the highest degree, the algorithm simply takes each node and
>>>> considers it as a "middle" node in a 2-path, then enumerates all possible
>>>> neighbor pairs of the node to find the "first" and "last" nodes in the
>>>> 2-path. For each such pair, the denominator is increased. If the "first"
>>>> and the "last" nodes are connected, the numerator is also increased. The
>>>> result then follows from a simple division.
>>>>
>>>> Best,
>>>> Tamas
>>>>
>>>>
>>>> _______________________________________________
>>>> igraph-help mailing list
>>>> https://lists.nongnu.org/mailman/listinfo/igraph-help
>>>
>>> _______________________________________________
>>> igraph-help mailing list
>>> https://lists.nongnu.org/mailman/listinfo/igraph-help
>>
>>
>>
>> --
>> Gabor Csardi <address@hidden>     MTA KFKI RMKI
>>
>> _______________________________________________
>> igraph-help mailing list
>> https://lists.nongnu.org/mailman/listinfo/igraph-help
>
> _______________________________________________
> igraph-help mailing list