Re: [igraph] clustering coefficient in weighted or directional graphs

[Gábor Csárdi]

Hi Tom,

Barrat's version is included in the 0.6 development tree. You can
download a source R package, (or a Python and C package if you don't
use R) from here:
http://code.google.com/p/igraph/downloads/list

Be careful with the R package, this 0.6 version is not compatible with
code for 0.5.x, because it counts vertex and edge ids from 1 and not
from zero.

Newman's version should not be difficult to implement, especially not
in R. You query the successors of ego and store them. Then you query
the successors of each successor of ego and check whether these
"double successors" of ego are also first "successors". This is pretty
much it.

For the weighted version you need to make sure that the normalization
is appropriate.

I hope this helps,
G.

On Tue, Jan 17, 2012 at 5:25 AM, Tom Richardson
<address@hidden> wrote:
> Hi List,
> I am interested in assessing the (global) clustering coefficient in my
> graphs. However, as my edges are directed and weighted (though not all edges
> are connected to all others), the igraph function ('transitivity') for
> estimating the CC doesn't account for the directionality or the edge
> weighting.
>
> I notice that equation 5 in  Barrat et al (2004)* gives a clustering
> coefficient for *weighted* (undirected) networks.
>
> In Newman (2010)** he states (p201) "It is possible to generalize
> transitivity to take account of directed links. If we have a directed
> relation between vertices such as "U likes V' then we can say that a triple
> of vertices is closed or transitive if U likes V, V likes W, and U also
> likes W. (Note that there are many distinct ways for such a triple to be
> transitive, depending on the directions of the edges. The example given here
> is only one of six different possibilities). One can calculate a clustering
> coefficient or fraction of transitive triples in the obvious fashion for the
> directed case, counting all directed paths of length two that are closed,
> and dividing by the total number of directed paths of length two. For some
> reason, however, such measures have not often appeared in the literature"
>
> So, my questions are;
> - In igraph, how would one implement the weighted CC  (equation 5 in Barratt
> 2004)?
> - In igraph, how would one implement the directed CC suggested by Newman
> 2010?
> - Would it be possible to combine the two?
>
> I Apologies if parts of the above seem elementary, but i prefer to get good
> advice before embarking on a dodgy hack of my own.
>
> Thanks!
> Tom
>
> *  Barrat et al. 2004. The architecture of complex weighted networks. PNAS.
> 101
> ** Newman, M. 2010. Networks. An Introduction.
>
> _______________________________________________
> igraph-help mailing list
> address@hidden
> https://lists.nongnu.org/mailman/listinfo/igraph-help
>



-- 
Gabor Csardi <address@hidden>     MTA KFKI RMKI