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 Answer 1

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\$
6
  • \$\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, 2012 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, 2012 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, 2012 at 16:10
  • \$\begingroup\$ If you fix this, you'll win. No one else seems interested. \$\endgroup\$
    – Griffin
    Aug 7, 2012 at 14:53
  • \$\begingroup\$ Fixed! Probably not the most elegant way possible, but it should work now. \$\endgroup\$
    – ESultanik
    Aug 7, 2012 at 15:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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