I want to implement the "vertex similarity" algorithm described in the paper Graph Isomorphism Detection Using Vertex Similarity Measure. The algorithm is as follows:
S(0) <- appropriately sized matrix filled with 1's for k=1 to 10 do: S(k) = Y*S(k-1)*X^T + Y^T*S(k-1)*X k++ Apply Hungarian assignment algorithm on similarity matrix S.
where X^T means the transpose of the matrix X.
Basically, given two graphs G1, G2 (not necessarily the same # of vertices), create their adjacency matrices X and Y. Then, do this iterative process 10 times, and then apply the Hungarian assignment algorithm. The result would be a similarity matrix where entry (i,j) represents a real number between 0 and 1 that gives how "similar" vertex i is of G1 to vertex j of G2.
My question is: how would this algorithm be implemented? I looked up the algorithm on Wikipedia, and the explanation seems as though all entries in S would be integers, but what is expected is real numbers between 0 and 1.