Re: [igraph] Transitivity

[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
> address@hidden
> https://lists.nongnu.org/mailman/listinfo/igraph-help