3
\$\begingroup\$

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 ; ...]

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Griffin Jul 19 '12 at 22:26
  • \$\begingroup\$ @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.) \$\endgroup\$ – ESultanik Jul 23 '12 at 12:14
  • \$\begingroup\$ 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 \$\endgroup\$ – Griffin Jul 23 '12 at 16:10
  • \$\begingroup\$ Ah, you're right. Thanks! \$\endgroup\$ – ESultanik Jul 23 '12 at 16:19
  • \$\begingroup\$ If you fix this, you'll win. No one else seems interested. \$\endgroup\$ – Griffin Aug 7 '12 at 14:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.