In [ ]:

    

## As usual, attach the numpy and the netwrokx modules
import networkx as nx
import numpy as np
import numpy.random as rnd

import matplotlib.pyplot as plt

%matplotlib inline


    

In [ ]:

    

## Determine the group sizes
n = 1000
s1 = 4 * n / 10
s2 = n - s1

## Fix the probabilities
p1 = .8
p2 = .5
pb = .1

## Initialize the permutation
perm = np.random.permutation( n )
g1 = perm[:s1] ; g2 = perm[s1:]

## Compute the similarity matrix
A = np.zeros( (n,n), dtype = np.int )
A[np.ix_(g1,g1)] = np.random.uniform( size = s1*s1 ).reshape( s1, s1 ) < p1
A[np.ix_(g2,g2)] = np.random.uniform( size = s2*s2 ).reshape( s2, s2 ) < p2
A[np.ix_(g2,g1)] = np.random.uniform( size = s2*s1 ).reshape( s2, s1 ) < pb
A = np.triu(A) + np.triu(A).T


    

In [ ]:

    

## Do the clustering
## First the laplace matrix
D = np.diag(np.sum(A, axis=0))
L = D - A

## Compute the SVD of $L$: L = U s V
U, s, V  = np.linalg.svd( L )


print np.max(np.abs( L.dot(V.T) - U.dot(np.diag(s)) ))



# plt.plot(s, "^k")

i = np.argsort(U[:,n-2])

plt.figure(figsize=(10,10,))


    

In [ ]:

    

plt.imshow(A[np.ix_(i,i)])


    

In [ ]:

    

plt.imshow(A)


    

In [ ]:

    

A


    

In [ ]: