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 <[email protected]> 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 <[email protected]> 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 >> <[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 > > _______________________________________________ > 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
