Talk:Clustering coefficient

From Wikipedia, the free encyclopedia

Duno is this is the right place to discuss about this but it seems like there is an error on this page. According to other websites and research papers, the maximum of links within the neighbourhood in a directed graph is k_i(k_i-1), not 2k_i(k_i-1).

One of the sources : http://www.elvis.ac.nz/brain?ClusteringCoefficient

It is indeed the correct place to discuss it. It was indeed incorrect, I've changed it. Thank you for your correction. --stochata 16:55, 1 Mar 2005 (UTC)

p.s., do not be afraid to be bold and correct it yourself!

Added a few wikilinks to explore for us aspiring math dummies out there. ^^ Zanturaeon 23:21, August 1, 2005 (UTC)

Isn't problematic if e_ij is e_ii an edge leading to the vertex whrer it starts? (that was from 83.135.204.222 in June 2006)

Indeed. If there is an assumption that i doesn't equal j in the definition of N, it ought to be stated. Or is it not a problem? 72.248.65.171 22:44, 18 March 2007 (UTC)

Shouldn't this definition be restricted to vertices with degree greater than or equal to zero? Can you find the clustering coefficient of an isolated vertex? Possie11 20:21, 24 April 2007 (UTC)

I think you mean degree strictly greater than one. Yes, you're clearly right, because a vertex with degree zero is isolated, and has an empty neighborhood; one with degree one has a singleton neighborhood, which can have no edges (well, no self-edges, anyway). BrianTung (talk) 21:20, 7 February 2008 (UTC)

The link on the bottom of the page doesn't work anymore. Someone might want to update it. 15:29, 27 May 2007 (UTC)

Sorry but... I think the page is very incomplete. First of all, there is no definition of the concept of clustering coefficient given. A formula is not a concept, is just an expression of a manner to estimate a quantity. Second, Watts and Strogatz did not invent the clustering coefficient, what is a quite old concept. Third, there is no distinction between the global and the local clustering coefficients. The global clustering, C, is the overall conditional probability that any two nodes are connected provided that they share at least one common neighbour. The local clustering Ci of a node i represents the probability of its neighbours to be connected within each other. In directed networks, there is no clear and commonly accepted manner of defining C (at least to my knowledge). However, the local clustering Ci can be applied to individual nodes of a directed network, and then averaged. BUT, if you calculate C of an undirected graph, and the average Ci of all its nodes, C and <Ci> are not the same! Please, let me know what you think about my comments. I will be happy to collaborate.

[edit] Small World != Clustering Coefficient

I believe the clustering coefficent has nothing to do with the "small-world"-effect, at least not directly. Think of a "big graph", which consists of a lot of throughly connected subgraphs, but the individual subgraphs are not connected to each other. Then the clustering coefficient of the "big graph" will be 1, but there is no small world effect. Most of the networks exhibiting the small world effect will have a high clustering coefficient, but a high clustering coefficient does not mean that the graph exhibits a small world effect. I think "ntroduced the clustering coefficient[1] graph measure to determine whether or not a graph is a small-world network." and "A graph is considered small-world, if its average clustering coefficient \bar{C} is significantly higher than a random graph constructed on the same vertex set." is wrong. 88.65.98.195 14:57, 15 September 2007 (UTC)

Please read the paper[1]. It defines the "small world phenomenon" as L slightly greater than Lrnd, while C much greater than Crnd. L is the Average path length, C is the Clustering Coefficient, and the Xrnd values are calculated for a random graph with the same number of edges and vertices. So in a way, you're right, a high clustering coefficient does not suffice for a small world (the paper even states that you can't detect a small world from clustering coefficient alone). The problem is that the clustering coefficient is a local graph measure, while the small world property is a global one. just my 2E-2 Euros. --80.136.95.157 14:58, 2 October 2007 (UTC)

I already knew the paper before. I did not find the explicit definition of "small world network" in the paper like you said. I think you mean this passage: "We find that these systems can be highly clustered, like regular lattices, yet have small characteristic path lengths, like random graphs. We call them ‘small-world’ networks, by ...". I think the meaning is "We call networks with small characteristic path lengths small world networks", not "We call highly clustered networks with small characteristic path lenghts small world models". Anyway, i feel the gist of the paper is: "Is it possible that a network with small path length is highly clustered?" and not "How can we find out whether a network is a small world network?". Besides, defining "small world" through the clustering coefficient is quite illogical IMHO. 88.65.77.185 —Preceding signed but undated comment was added at 15:57, 8 October 2007 (UTC)

I agree, the small world property is as indicated by the name, a property of graphs that have a small average distance. The literature is however often interested in real-world small world graphs, they tend to have a large clustering coefficient too. The disregard for trivial small world graphs in literature has confused the author of this article.