Re: [igraph] Transitivity

[Gábor Csárdi]

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