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

[Tamás Nepusz]

Hi Tom,

Gabor has said pretty much everything that's relevant to your question; I only 
have a small addition. Newman's directed CC is just one possible extension and 
there have been other proposals as well; take a look at this paper for another 
possible generalization (well, actually, _four_ possible generalizations):

http://pre.aps.org/abstract/PRE/v78/i3/e036112

Cheers,
Tamas


On 17 Jan 2012, at 11:25, Tom Richardson 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