Graph Theory: Calculating Clustering Coefficient

user_745808 0
Viewed 15075

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.

cluster-analysis graph-theory algorithm
5 Answers

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

user_10702580
Related