5.6. Clustering¶

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 NaN.

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.

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.

Support Runestone Academy Today

You have attempted 1 of 2 activities on this page