Re: Clustering coefficient in directed graphs - possible bug in Cytoscape?

[Alexander Pico]

This is an excellent bug report for the Network Analyzer tool within Cytoscape. I've add it to our bug tracker and added your email as a contact. Feel free to report bugs anytime directly to the tracker via:

http://chianti.ucsd.edu/cyto_web/bugreport/bugreport.php

Thanks!

 - Alex

On Thursday, March 28, 2013 3:26:13 AM UTC-7, Federico Vaggi wrote:

Hi everyone,

I just started using Cytoscape, and noticed that Cytoscape was reporting numbers that were slightly off from those I calculated using the formula described here: http://web1.sssup.it/pubblicazioni/ugov_files/303163_PRE_2007.pdf - I did a fair bit of digging, and found out the source of the discrepancy.

Usually, the clustering coefficient is informally defined as the fraction of triangles that are present in near a node, divided by the total number of possible triangles.  For a non-directed graph, this is the same as the fraction of total possible edges, divided by the actual of edges present.

However, for a directed network, the two definitions give subtly different answers.  If you are interested in the fraction of possible edges, the correct normalization is:

k_n*(k_n-1) - as described here: http://med.bioinf.mpi-inf.mpg.de/netanalyzer/help/2.6.1/#clustCoef

where k_n is the total degree of node n.

If you are interested in the fraction of possible triangles, then the correct normalization is:

k_n*(k_n-1) - 2(k_mutual) 

where k_n is the total degree of node n, and k_mutual is the number of mutual edges between nodes - for example an edge going between i and j and one going between j and i.

 http://web1.sssup.it/pubblicazioni/ugov_files/303163_PRE_2007.pdf explains this well, in the paragraph immediately after Equation 8.  Wikipedia's definition (not authoritative) defines clustering coefficient in terms of triplets.  I don't think either definition is necessarily correct, but it's something that should be probably documented and discussed.

Thank you very much!

Federico