# Calculate Network Average Clustering Coefficient

The clustering coefficient of a graph (or network) is a:

measure of degree to which nodes in a graph tend to cluster together

The Wikipedia article gives a much better description of how network average clustering coefficient is calculated from local clustering coefficients than I could give.

## The Challenge

Given an adjacency matrix a describing an undirected network (or graph) with no self loops, calculate it's network average clustering coefficient.

### Details

• You must write a program/function/procedure/code block which calculates the network average clustering coefficient for any undirected graph with no self loops.
• The output may only contain the coefficient and nothing else.
• You are to assume that your program (or whatever) has access to an adjacency matrix describing the graph through a variable/the stack/file/whatever
• You may not use any inbuilt functionality your language may have to calculate clustering coefficients
• Shortest code wins

### Test Examples

Test inputs and outputs can be found in this pastebin

### My solution: GNU Octave, 93 chars

(behind spoiler)

f=sum(a);c=0;for i=find(f>1)c+=sum(a(t=find(a(i,:)),t)(:))/(f(i)*(f(i)-1));endfor;c/length(a)

Which can be tested here, the matrix needs to be in the format a = [row ; row ; row ; ...]

# Python: 192 Characters (not including whitespace)

import itertools
def l(a,i,r):
s=[b for b in r if a[i][b]]
k=len(s)
if k<2:
return 0
return 2.0*sum(map(lambda x:a[x[0]][x[1]],itertools.combinations(s,2)))/k/(k-1)
def g(a):
n=len(a)
r=range(n)
return sum([l(a,i,r) for i in r])/n


# Example Usage:

>>> g([[1, 1, 1], [1, 1, 1], [1, 1, 1]])
1.0
>>> g([[0, 1, 0, 0, 0, 1, 0, 0],
[1, 0, 1, 1, 1, 0, 1, 0],
[0, 1, 0, 0, 0, 1, 0, 0],
[0, 1, 0, 0, 1, 0, 0, 0],
[0, 1, 0, 1, 0, 1, 1, 0],
[1, 0, 1, 0, 1, 0, 0, 1],
[0, 1, 0, 0, 1, 0, 0, 1],
[0, 0, 0, 0, 0, 1, 1, 0]])
0.233333333333
>>> g([[0, 1, 0, 0, 1],
[1, 0, 1, 0, 0],
[0, 1, 0, 1, 0],
[0, 0, 1, 0, 1],
[1, 0, 0, 1, 0]])
0.0
>>> g([[0,1,1,1,0,1,1,1,1,0,1,0,0,0,1,0,0,0,0,1],
[1,0,0,0,1,0,0,0,1,1,1,1,0,1,0,0,1,0,0,1],
[1,0,0,1,1,1,0,0,1,0,0,0,0,0,0,0,0,0,1,0],
[1,0,1,0,0,0,0,1,1,1,0,1,0,1,1,1,0,0,0,1],
[0,1,1,0,0,1,0,1,1,0,0,0,0,1,0,0,0,0,1,0],
[1,0,1,0,1,0,0,1,0,0,1,1,0,0,0,1,0,1,1,1],
[1,0,0,0,0,0,0,1,1,0,0,1,1,0,1,1,0,0,1,0],
[1,0,0,1,1,1,1,0,1,1,0,0,0,0,0,0,1,0,0,0],
[1,1,1,1,1,0,1,1,0,0,1,0,1,0,0,0,1,0,1,0],
[0,1,0,1,0,0,0,1,0,0,1,0,0,0,0,1,0,1,0,0],
[1,1,0,0,0,1,0,0,1,1,0,0,1,0,0,0,0,1,1,0],
[0,1,0,1,0,1,1,0,0,0,0,0,1,1,1,1,0,1,0,0],
[0,0,0,0,0,0,1,0,1,0,1,1,0,0,1,0,1,1,0,1],
[0,1,0,1,1,0,0,0,0,0,0,1,0,0,0,0,1,1,1,0],
[1,0,0,1,0,0,1,0,0,0,0,1,1,0,0,1,1,1,1,0],
[0,0,0,1,0,1,1,0,0,1,0,1,0,0,1,0,0,0,1,1],
[0,1,0,0,0,0,0,1,1,0,0,0,1,1,1,0,0,0,1,1],
[0,0,0,0,0,1,0,0,0,1,1,1,1,1,1,0,0,0,0,0],
[0,0,1,0,1,1,1,0,1,0,1,0,0,1,1,1,1,0,0,1],
[1,1,0,1,0,1,0,0,0,0,0,0,1,0,0,1,1,0,1,0]])
0.389888167388
>>> g([[0,1,1],
[1,0,0],
[1,0,0]])
0.0

• Wooo, an answer! Unfortunately your answer is not quite right. Some graphs (where neighbouring nodes have no edges between them) force division by zero, see the 3rd test example. When division by zero occurs, it is assumed that zero is returned. Jul 19, 2012 at 22:26
• @Griffin: I did run the third example and it appears to return zero, as desired. (I just left it out of the examples here to save room, but I added it back.) Jul 23, 2012 at 12:14
• Strange, I got a divide by zero on the third example, but I don't anymore. However I still get a divide by zero error with this example: ideone.com/k9e4l Jul 23, 2012 at 16:10
• Ah, you're right. Thanks! Jul 23, 2012 at 16:19
• If you fix this, you'll win. No one else seems interested. Aug 7, 2012 at 14:53