Re: [igraph] Transitivity

[Gábor Csárdi]

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
<address@hidden> wrote:
> 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
>> http://bazaar.launchpad.net/~igraph/igraph/0.6-main/view/head:/src/structural_properties.c
>> 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
>> <address@hidden> wrote:
>>> 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
>>>> address@hidden
>>>> https://lists.nongnu.org/mailman/listinfo/igraph-help
>>>
>>> _______________________________________________
>>> igraph-help mailing list
>>> address@hidden
>>> https://lists.nongnu.org/mailman/listinfo/igraph-help
>>
>>
>>
>> --
>> Gabor Csardi <address@hidden>     MTA KFKI RMKI
>>
>> _______________________________________________
>> igraph-help mailing list
>> address@hidden
>> https://lists.nongnu.org/mailman/listinfo/igraph-help
>
> _______________________________________________
> igraph-help mailing list
> address@hidden
> https://lists.nongnu.org/mailman/listinfo/igraph-help



-- 
Gabor Csardi <address@hidden>     MTA KFKI RMKI