15

I'm doing some research and I've come to a point where I have calculate the clustering coefficient of a graph.

According to this paper directly related to my research:

The clustering coefficient C(p) is defined as follows. Suppose that a vertex v has kv neighbours; then at most (kv * (kv-1)) / 2 edges can exist between them (this occurs when every neighbour of v is connected to every other neighbour of v). Let Cv denote the fraction of these allowable edges that actually exist. Define C as the average of Cv over all v

But this wikipedia article on the subject says differently:

C = (number of closed triplets) / (number of connected triples)

It seems to me that the latter is more computationally expensive.

So really my question is: are they equivalent?

It should be noted that the paper is cited by the Wikipedia article.

Thanks for your time.

8
  • 2
    There's a site for that cstheory.stackexchange.com Commented Jul 10, 2011 at 21:01
  • Ah, I did not know about that. I shall ask the same over there. Thanks
    – Griffin
    Commented Jul 10, 2011 at 21:04
  • 1
    @Henk - sure? Isn't cstheory for research level CS? I'm not sure they're receptive to this kind of question.
    – user180247
    Commented Jul 10, 2011 at 21:44
  • May belong on math.stackexchange.com though
    – user180247
    Commented Jul 10, 2011 at 21:54
  • @Steve: I don't really know. But the current top question on their homepages is "What hierarchies and/or hierarchies theorems do you know?" so I think there's some spread in quality there too. Commented Jul 10, 2011 at 21:57

5 Answers 5

12

The two formulas are not the same; they are two different ways in which the global clustering coefficient can be calculated.

One way is by averaging the clustering coefficients (C_i [1]) of all nodes (this is the method you quoted from Watts and Strogatz). However, in [2, p204] Newman argues that this method is less preferable than the second one (the one you got from wikipedia). He justifies by pointing how the value of the global clustering coeff can be dominated by nodes of low degree, due to C_i's denominator [1]. So, in a network with many nodes of low degrees, you end up with a large value for the global clustering coeff, which Newman argues would be unrepresentative.

However, many network studies (or, in my experience, at least many studies concerned with online social networks) seem to have used this method, so in order to be able to compare your results with theirs, you would require to use the same method. Furthermore, the critique raised by Newman does not affect the extent to which comparisons of global clustering coefficients can be made, provided the same method was used in measuring them.

The two formulae are different and were proposed at different moments in time. The one you quoted from Watt and Strogatz is older, which is perhaps why it seems to have been more commonly used. Newman also explains that the two formulae are far from equivalent, and shouldn't be used as such. He says they can give substantially different numbers for a given network, however doesn't explain why.

[1] C_i = (number of pairs of neighbours of i that are connected) / (number of pairs of neighbours of i)

[2] Newman, M.E.J.. Networks : an introduction. Oxford New York: Oxford University Press, 2010. Print.

Edit:

I am including here a series of calculations for the same ER random graph. You can see how the two methods give different results, even for undirected graphs. (done using Mathematica)

1
5

I think they're equivalent. The wiki page you link to gives a proof that the triples formulation is equivalent to the fraction of possible edges formulation when calculating the local clustering coefficient, i.e. calculated just at a vertex. From there it seems that you just need to show that

sum_v lambda(v)/tau(v) = 3 x # triangles / # connected triples

where lambda(v) is the number of triangles containing v, and tau(v) is the number of connected triples for which v is the middle vertex, i.e. adjacent to each of the other 2 edges.

Now each triangle gets counted three times in the numerator of the LHS. However, each connected triple is only counted once for the middle vertex on the LHS, so the denominators are the same.

4
  • I'll have to come back fresh tomorrow to go over what you said again. Looking further down the page however, it seems that it is "Network average clustering coefficient" I am looking for. Since the page proves that the two methods are equivalent for local clustering coefficint. And that Network average clustering coefficient is just the average of all the local cluster coefficients. It would seem that the two methods are equivalent since the method in the paper and the citation in that section are from the same authors (Watts and Strogatz). What do you say?
    – Griffin
    Commented Jul 10, 2011 at 23:11
  • Yeah, the network average is what you're looking at. You just need to prove that the sum for the network average using the fraction of edges formulation is equivalent to the global clustering coefficient presented at the top of the page - this is what my answer is doing.
    – Whatang
    Commented Jul 10, 2011 at 23:14
  • Well, if you feel you want to accept it, yes :P But feel free to work it through and convince yourself that I'm right first!
    – Whatang
    Commented Jul 10, 2011 at 23:20
  • Ok, thank you very much for your help. I will report back tomorrow.
    – Griffin
    Commented Jul 10, 2011 at 23:22
2

I partially disagree with Whatang. These methods are only equivalent for undirected graphs. However for directed graphs they return different results. In my opinion the local clustering coefficient method is the correct one. Not to mention its less computationally expensive. For example

  <-----
4 -----> 5
|<--||-->
|   ||
|-> 6  -> 7

4(IN [5,6], OUT [5,6])
5(IN [4,6], OUT [4])
6(IN [4], OUT [4,5,7])
7(IN [6], OUT [])

central = 6

localCC = 2 / 4*3 = 1/6

globalCC = 1 / 3

0

I wouldn't trust that wikipedia article. The first formula you cited is currently defined as the Mean Clustering Coefficient, hence it is the mean of all local clustering coefficients for a graph g. This is in no way the same as the global clustering coefficient, as xk_id aptly put it.

0

there is a great page to learn the basics from!

http://www.learner.org/courses/mathilluminated/interactives/network/

all about cluster coefficients, small world and so on ...

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.