# Implementation of Vertex Similarity algorithm (Blondel's Similarity Measure)

I am implementing the vertex similarity algorithm in this paper. The adjacency matrices I will be dealing with, however, will be very large, on the order of 30k vertices (I provided sample matrices in the main method).

The algorithm is to calculate S(k+1) as an iterative matrix. The algorithm is given on page 2 of the paper (listed as 114).

According to the paper, the implementation below is correct. What I want feedback on is memory efficiency, to not make new matrices as much as possible.

public class Matrix {
private final int M, N;
private final double[][] data;

public Matrix(int M, int N) {
this.M = M;
this.N = N;
data = new double[M][N];
}

public Matrix(double[][] data) {
M = data.length;
N = data[0].length;
this.data = new double[M][N];
for (int i = 0; i < M; i++)
for (int j = 0; j < N; j++)
this.data[i][j] = data[i][j];
}

public Matrix transpose() {
Matrix A = new Matrix(N, M);
for (int i = 0; i < M; i++)
for (int j = 0; j < N; j++)
A.data[j][i] = data[i][j];
return A;
}

public Matrix plus(Matrix B) {
Matrix A = this;
assert B.M != A.M || B.N != A.N;
Matrix C = new Matrix(M, N);
for (int i = 0; i < M; i++)
for (int j = 0; j < N; j++)
C.data[i][j] = A.data[i][j] + B.data[i][j];
return C;
}

public Matrix times(Matrix B) {
Matrix A = this;
assert A.N == B.M;
Matrix C = new Matrix(A.M, B.N);
for (int i = 0; i < C.M; i++)
for (int j = 0; j < C.N; j++)
for (int k = 0; k < A.N; k++)
C.data[i][j] += (A.data[i][k] * B.data[k][j]);
return C;
}

@Override
public String toString() {
StringBuilder s = new StringBuilder();
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
s.append(data[i][j]).append(" ");
}
s.append("\n");
}
return s.toString();
}

public static void main(String[] args) {
// Sample matrices
double[][] a = {
{0,1,0,1},
{1,0,1,0},
{0,1,0,0},
{1,0,0,0}
};
double[][] b = {
{0,0,1,1,0,0},
{0,0,0,1,0,1},
{1,0,0,0,1,1},
{0,0,0,0,0,0},
{0,0,0,0,0,0},
{1,0,1,1,0,0}
};
// Xk is the iteration of the algorithm matrix.
double[][] xk = new double[b.length][a[0].length];
for (int i = 0; i < xk.length; i++) {
for (int j = 0; j < xk[0].length; j++) {
xk[i][j] = 1;
}
}
Matrix X = new Matrix(a);
Matrix Y = new Matrix(b);
Matrix Sk = new Matrix(xk);
int n = 10; // number of iterations of algorithm
for (int i=0; i<n; i++) {
// This is the actual algorithm.
Matrix firstProduct = Y.times(Sk).times(X.transpose());
Matrix secondProduct = Y.transpose().times(Sk).times(X);
Matrix totalProduct = firstProduct.plus(secondProduct);
double[][] data = totalProduct.transpose().data;
Sk = new Matrix(normalizeByRows(data)).transpose();
System.out.println(Sk);
System.out.println("------------");
}
// This is to calculate the average value in Sk.
double[][] data = Sk.data;
double sum = 0.0;
int count = 0;
for (double[] j : data) {
for (double l : j) {
count++;
sum += l;
}
}
sum /= count;
System.out.println(sum);
}

private static double[][] normalizeByRows(double[][] data) {
for (int k=0; k<data.length; k++) {
double[] row = data[k];
double max = 0;
for (double l : row) {
max += l;
}
for (int l = 0; l < data[k].length; l++) {
data[k][l] /= max;
}
}
return data;
}
}


private final int M, N;


It's Java. Albeit M and N may get big, you should use camelcase (small initial letters) for non-constant fields. Maybe something like width and height? Or rows and colums, or m and n, if you insist.

public Matrix(double[][] data) {
M = data.length;
N = data[0].length;
this.data = new double[M][N];
for (int i = 0; i < M; i++)
for (int j = 0; j < N; j++)
this.data[i][j] = data[i][j];
}


Either make the method non-public or check arguments, especially check that each row has the same length. Apart from this, the inner loop could be replaced by

this.data[i] = data[i].clone();


What I want feedback on is memory efficiency, to not make new matrices as much as possible.

Matrix firstProduct = Y.times(Sk).times(X.transpose());


Here you're creating an new matrix, while a view of the original would do (albeit probably slower). You could instead define a timesTransposed operation and have the full speed without any allocations. That's pretty simple and you can test it nicely using the existing operations.

Matrix totalProduct = firstProduct.plus(secondProduct);


Here you can avoid allocations by implementing the equivalent of +=. It surely doesn't make you code more readable, but sometimes that's the price for efficiency.

An operation like *= could get pretty complicated for matrices (and is rather impossible for non-square matrices, so lets forget it).

    double[][] data = totalProduct.transpose().data;
Sk = new Matrix(normalizeByRows(data)).transpose();


Here, you're refusing to use objects and I really can't why. normalizeByRows should be a method (either modifying an existing matrix or creating a new one; choose what you need, but be careful with naming).

// This is the actual algorithm.


So don't put it in main. Make a method, name it properly and save yourself that comment.

• The 2nd to last point was that the matrix is normalized by the column - I thought to make it more efficient (cache-miss wise) was to transpose it, normalize by the rows, and transpose back. But otherwise, thanks! Commented Oct 17, 2014 at 22:34
• @Ryan It can hardly be more efficient as you're touching and copying all the data multiple times. Actually, you can easily compute all column maxima in the first pass and scale it in the second. However, my point was that whatever you choose, you can do it with a Matrix instead of double[][]. For better cache locality consider mapping onto a 1D array, it's not really hard and it saves you the indirection. Commented Oct 17, 2014 at 22:43