igraph-help
[Top][All Lists]

## Re: [igraph] Transitivity

 From: Moses Boudourides Subject: Re: [igraph] Transitivity Date: Tue, 20 Mar 2012 15:16:53 +0200

```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
> 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
>> 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
>>> https://lists.nongnu.org/mailman/listinfo/igraph-help
>>
>> _______________________________________________
>> igraph-help mailing list
>> https://lists.nongnu.org/mailman/listinfo/igraph-help
>
>
>
> --
> Gabor Csardi <address@hidden>     MTA KFKI RMKI
>
> _______________________________________________
> igraph-help mailing list