
Title:
Clustering Coefficient Code  Intro to Algorithms

Description:

Here's a little bit of code for computing the clustering coefficient

at least one particular way of computing it.

Here's our list of flights on our map.

Catching between Chicago and Seattle, etc.,

and I just have that as a list of pairs.

And to create the graph, I start off with an empty graph,

and then for each of the pairs that constitute the end points of a flight,

we make a link between them like we were doing last time.

Then to compute the clustering coefficient for the graph at some node,

we list out the neighbors.

If there's only one neighbor, it turns out to be very hard

to compute the clustering coefficient.

So we have to give it some kind of value; I chose zero.

It actually kind of matters, but zero seems like a reasonable choice.

Then what we're going to do is we're going to count up

the number of links between these neighboring nodes.

So we start off at zero, we loop through all the neighbors,

and for each of those we loop through all the neighbors again

and then we ask if this pair

WUis there a link between them?

And if soin this case I'm counting it as a half

because I wrote this inefficiently.

It's going to do everything twice.

So it's going to notice that Seattle and Los Angeles are connected

and that Los Angeles and Seattle are connected.

So I give it a half each time so that the total number works out.

And then I apply the formula.

Two times the number of links divided by length of neighbors

times length of neighbors minus one.

So now that we can compute the clustering coefficient for any node V

we can actually loop through all the nodes in the graph

computing the total of their clustering coefficients

and then divide by the number of nodes to get the clustering coefficient

for the whole graph.

So in this case, it's a little bit of a quarter,

which is pretty clumpy.

So there's a fair amount of interconnection

between a node's neighbors.

From what I've read, social networks will often have clustering coefficients

that are in the 0.1, maybe even up to the 0.8 range

whereas the grid graphs, chain graphs, and ring graphs that we've looked at

actually have clustering coefficients of zero.