 ## ← Clustering Coefficient Code - Intro to Algorithms

• 3 Followers
• 42 Lines

### Get Embed Code x Embed video Use the following code to embed this video. See our usage guide for more details on embedding. Paste this in your document somewhere (closest to the closing body tag is preferable): ```<script type="text/javascript" src='https://amara.org/embedder-iframe'></script> ``` Paste this inside your HTML body, where you want to include the widget: ```<div class="amara-embed" data-url="http://www.youtube.com/watch?v=cp3C5EPRoww" data-team="udacity"></div> ``` 3 Languages

• English [en] original
• Hindi [hi]
• Japanese [ja]

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.