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 <[email protected]> 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 <[email protected]> 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 >> [email protected] >> https://lists.nongnu.org/mailman/listinfo/igraph-help > > _______________________________________________ > igraph-help mailing list > [email protected] > https://lists.nongnu.org/mailman/listinfo/igraph-help -- Gabor Csardi <[email protected]> MTA KFKI RMKI _______________________________________________ igraph-help mailing list [email protected] https://lists.nongnu.org/mailman/listinfo/igraph-help
