Before you keep reading...
Runestone Academy can only continue if we get support from individuals like you. As a student you are well aware of the high cost of textbooks. Our mission is to provide great books to you for free, but we ask that you consider a $10 donation, more if you can or less if $10 is a burden.
Before you keep reading...
Making great stuff takes time and $$. If you appreciate the book you are reading now and want to keep quality materials free for other students please consider a donation to Runestone Academy. We ask that you consider a $10 donation, but if you can give more thats great, if $10 is too much for your budget we would be happy with whatever you can afford as a show of support.
The next step is to compute the clustering coefficient, which quantifies the tendency for the nodes to form cliques. A clique is a set of nodes that are completely connected; that is, there are edges between all pairs of nodes in the set.
Suppose a particular node,
u, has k neighbors. If all of the neighbors are connected to each other, there would be \(k(k−1)/2\) edges among them. The fraction of those edges that actually exist is the local clustering coefficient for \(u\), denoted \(C_u\).
If we compute the average of \(C_u\) over all nodes, we get the “network average clustering coefficient”, denoted \(C\).
Here is a function that computes it.
def node_clustering(G, u): neighbors = G[u] k = len(neighbors) if k < 2: return np.nan possible = k * (k-1) / 2 exist = 0 for v, w in all_pairs(neighbors): if G.has_edge(v, w): exist +=1 return exist / possible
Again I use
G[u], which returns a dictionary with the neighbors of
u as keys.
If a node has fewer than 2 neighbors, the clustering coefficient is undefined, so we return
np.nan, which is a special value that indicates “Not a Number”.
Otherwise we compute the number of possible edges among the neighbors, count the number of those edges that actually exist, and return the fraction that exist.
We can test the function like this:
>>> lattice = make_ring_lattice(10, 4) >>> node_clustering(lattice, 1) 0.5
In a ring lattice with \(k=4\), the clustering coefficient for each node is \(0.5\) (if you are not convinced, take another look at Figure 5.1).
Now we can compute the network average clustering coefficient like this:
def clustering_coefficient(G): cu = [node_clustering(G, node) for node in G] return np.nanmean(cu)
The NumPy function
nanmean computes the mean of the local clustering coefficients, ignoring any values that are
We can test
clustering_coefficient like this:
>>> clustering_coefficient(lattice) 0.5
In this graph, the local clustering coefficient for all nodes is \(0.5\), so the average across nodes is \(0.5\). Of course, we expect this value to be different for WS graphs.