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 &lt; M; i++)
        for (int j = 0; j &lt; N; j++)
                this.data[i][j] = data[i][j];
}

public Matrix transpose() {
    Matrix A = new Matrix(N, M);
    for (int i = 0; i &lt; M; i++)
        for (int j = 0; j &lt; 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 &lt; M; i++)
        for (int j = 0; j &lt; 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 &lt; C.M; i++)
        for (int j = 0; j &lt; C.N; j++)
            for (int k = 0; k &lt; 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 &lt; M; i++) {
        for (int j = 0; j &lt; 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 &lt; xk.length; i++) {
        for (int j = 0; j &lt; 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&lt;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&lt;data.length; k++) {
        double[] row = data[k];
        double max = 0;
        for (double l : row) {
            max += l;
        }
        for (int l = 0; l &lt; 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 &lt; M; i++)
        for (int j = 0; j &lt; 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.