YouTube

Got a YouTube account?

New: enable viewer-created translations and captions on your YouTube channel!

English subtitles

← Clustering Coefficient Code - Intro to Algorithms

Get Embed Code
3 Languages

Showing Revision 3 created 05/24/2016 by Udacity Robot.

  1. Here's a little bit of code for computing the clustering coefficient--
  2. at least one particular way of computing it.
  3. Here's our list of flights on our map.
  4. Catching between Chicago and Seattle, etc.,
  5. and I just have that as a list of pairs.
  6. And to create the graph, I start off with an empty graph,
  7. and then for each of the pairs that constitute the end points of a flight,
  8. we make a link between them like we were doing last time.
  9. Then to compute the clustering coefficient for the graph at some node,
  10. we list out the neighbors.
  11. If there's only one neighbor, it turns out to be very hard
  12. to compute the clustering coefficient.
  13. So we have to give it some kind of value; I chose zero.
  14. It actually kind of matters, but zero seems like a reasonable choice.
  15. Then what we're going to do is we're going to count up
  16. the number of links between these neighboring nodes.
  17. So we start off at zero, we loop through all the neighbors,
  18. and for each of those we loop through all the neighbors again
  19. and then we ask if this pair--
  20. WU--is there a link between them?
  21. And if so--in this case I'm counting it as a half
  22. because I wrote this inefficiently.
  23. It's going to do everything twice.
  24. So it's going to notice that Seattle and Los Angeles are connected
  25. and that Los Angeles and Seattle are connected.
  26. So I give it a half each time so that the total number works out.
  27. And then I apply the formula.
  28. Two times the number of links divided by length of neighbors
  29. times length of neighbors minus one.
  30. So now that we can compute the clustering coefficient for any node V
  31. we can actually loop through all the nodes in the graph
  32. computing the total of their clustering coefficients
  33. and then divide by the number of nodes to get the clustering coefficient
  34. for the whole graph.
  35. So in this case, it's a little bit of a quarter,
  36. which is pretty clumpy.
  37. So there's a fair amount of interconnection
  38. between a node's neighbors.
  39. From what I've read, social networks will often have clustering coefficients
  40. that are in the 0.1, maybe even up to the 0.8 range
  41. whereas the grid graphs, chain graphs, and ring graphs that we've looked at
  42. actually have clustering coefficients of zero.