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
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.

  • 1
    $\begingroup$ I don't get the question. What is your particular problem when implementing the algorithm? $\endgroup$
    – Raphael
    Nov 8 '14 at 16:57
  • $\begingroup$ There is no explanation I can find that details how the algorithm works nor an existing implementation of the algorithm. The only part that I can't find is about the Hungarian assignment part. $\endgroup$
    – Ryan
    Nov 8 '14 at 16:58
  • $\begingroup$ See page 13 of this slide deck. Per my understanding, the entries in $S$ need not be integral for the algorithm to still work. $\endgroup$
    – apnorton
    Nov 8 '14 at 21:13
  • $\begingroup$ Some context for the question, in case people were wondering: academia.stackexchange.com/questions/31410/… $\endgroup$
    – apnorton
    Nov 8 '14 at 21:15

The article you linked assumes that the reader knows how to apply the Hungarian algorithm on a similarity matrix because they have note in the introduction to Section 3 that Zager et. al. used the Hungarian algorithm for this purpose in the paper here.

Furthermore, there is no requirement in the Hungarian algorithm that necessitates integral entries; neither the Wikipedia article and this slide deck mention any requirement for the entries to be integers. Authors may use integer values for examples because they're easy to work with, but that does not mean the algorithm requires them.

  • $\begingroup$ Thanks for your response, but what I meant was that the output was not necessarily integers from what I understand, not the input. $\endgroup$
    – Ryan
    Nov 8 '14 at 21:58
  • $\begingroup$ @Ryan The Hungarian algorithm yields a selection of elements in $S$ such that their sum is maximal. (It does not return an integer.) Since each row/column in $S$ corresponds to a vertex in the first/second graph to compare, we can consider an entry in $S$ to provide a map from the first graph to the second graph. The row/columns of $S$ that are selected then generates a mapping between the two graphs. Does that help, or am I misunderstanding your question? $\endgroup$
    – apnorton
    Nov 8 '14 at 22:12
  • $\begingroup$ It helps a little, but I'm wondering how the mapping works. The algorithms given by Blondel and Zager give a correlation value between vertices of the graphs, but this algorithm seems to be giving something else that I'm not quite getting. $\endgroup$
    – Ryan
    Nov 8 '14 at 22:16
  • $\begingroup$ Also, an implementation of the algorithm in some form in any language would be very helpful - however, I cannot seem to find one in existence. $\endgroup$
    – Ryan
    Nov 8 '14 at 22:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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