Hello Matthias

The clustering coefficient characterises the whole graph and it could be seen as a measure of "how far away" is a given graph G from a Clique K of the same order (i.e. If G has 20 nodes then the clustering coefficient will return information about "how far apart" is G -which can have any kind of connectivity- from a K20 (which is the complete graph with 20 nodes).

As you might perhaps already have noted, the clustering coefficient is first defined locally (i.e. you have to first derive the clustering coefficient of every node Ci(Vi) where V is the set of nodes in G) and then, globally, for the whole graph as the _mean_ of the node's clustering coefficients.

Coming back to your question, Strogatz and Watts where looking into random undirected networks where "each node is connected on average with k others".

If this is the case with some network G (like the ones that might be emerging in your work) then you can go ahead and use the typical arithmetic mean.

Otherwise, if you think that only a subgraph of your graph might appear to be clustered and therefore the clustering coefficient might not return an accurate feature for this graph then you could first look at the distribution of your Ci(Vi) first and choose a different expression for the "mean" (for example, the modal mean) OR use some other metric to work with your graphs.

Finally, just two notes about the short description of your application (NLP): a) The Clustering Coefficient is defined over undirected graphs (You are probably dealing with directed graphs) and b) If you can work with undirected graphs it is quite likely that you will end up with a graph with a reach structure of cycles (this is because words get re-used in a piece of text and you would therefore have to add edges that link back to words you have seen before and so on). Therefore you might need a different metric anyway.

I hope this helps

Please note:

Regarding cliques (http://en.wikipedia.org/wiki/Clique_%28graph_theory%29) and some terminology which you might find helpful all gathered in one place :-) (http://en.wikipedia.org/wiki/Glossary_of_graph_theory)

I think that Athanasios provided an excellent explanation, certainly more helpful than the one I could offer. Gianrocco Tucci

Hello Matthias,

Very interesting question, and very helpful answer from Athanasios Anastasiou ! I am happy to find people working on lexical graphs !

I do not have much to add to this, but you might want to check (but you probably know it already!) the betweenness centrality score of the nodes of your graph. If your goal is to find the subgraphs of you graph that might be more connected than the rest, then it could be useful to detect the nodes with high betweenness centrality. When filtering these nodes, the graph should split up (each connected component is then a cluster). The filtered nodes can then be reattached to one or more of these clusters.

I hope it helped.

Hello Aurélien,

Happy to find colleagues, to ! (More exactly, to meet them again on the web)

Using of centrality measures to inquiry about subgraphs structure and mutual organization of them is a simple and powerful idea. But it is said that many of these measures don't agree. Do you have an argument for the use of betweenness centrality ? I like this measure, because I understand how it works (shortest pathways). But what about HITS, closeness centrality, eigenvector centrality, etc. ?

If I have time, I will try extensively on your filtering method. It will help.

PS : I've begun working on graph communities, still on Gephi. I will refer to the communication you made in Besançon.

Sadly no ; I do not have an argument for the use of this metric over the other ones. I would love to work more on this subject, but I did not have much time lately!

Do you know nodeXL? It is a free open-source template for Excel (from 2007 - but Excel is NOT free open-source!). I did not have much time to try it out, but I think it is a great way to experiment freely with all these measures, because you will not have to code each one of them (I implemented HITS, and it is a very time consuming task). NodeXL allows you to easily visualize graphs and put many filters/colors on them, using metrics such as degree, betweenness centrality, PageRank, or HITS. You can download it here : http://nodexl.codeplex.com/.

I you have time to try it out, I would love to hear your comments on it. Using graph theory for linguistics is really great and I would really love to help you / work with you if you want :).

Have a good time playing with graphs!

PS : thanks for the citation :). However, it might be better to refer to my JADT2012 communication since it is described in much more details.

When you ask for an interpretation does it mean that you want an NLP interpretation of your coefficient? If yes, the closest your lexical graph is to a clique (cf previous explanations on the local clustering coefficient), the more your text focuses on a single semantic field, according to your graph building method. If you get a clique, or a quasi-clique, it means that all your text words tend to be highly co-occurrent. This seem to happen to words describing a given semantic field, or a conventional script.

Another piece of software you might want to try is Gephi (http://gephi.org/), I use it for visualizing large graphs. One issue I had with NodeXL was visualization, which it doesn't perform well for large graphs. I use NodeXL, but only for removal of duplicate edges.

As for your initial question, I think it was answered well by Athanasios, but a more informal way of thinking about clustering is "are my friends also friends?" If you have a group of friends and few of them know each other, that is low clustering; but if many of them know each other, that is high clustering. If everyone knows everyone, then you have a complete graph (or clique).

With regards to use of metric, you have to ask harder questions about the nature of nodes and links in your graph and what does the metric say about that relationship. Betweenness highlights nodes with the largest number of shortest paths, but the important question to ask is are shortest paths important in your network? I like to consider the flow of information when considering what metrics are important. A good paper to look at is Stephen Borgatti's 2005 paper "Centrality and network flow" in social. I found it very useful for my review on brain networks.

Thanks a lot for your answers !

I will try to write a more significant contribution later.

But I have found another smart (but too short) explanation of the clustering coefficient here : http://www.pnas.org/content/99/12/7821 (page 1, bottom).