Re: [igraph] Transitivity

[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
> 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