1
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ I don't get the question. What is your particular problem when implementing the algorithm? $\endgroup$
    – Raphael
    Commented Nov 8, 2014 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 Dougherty
    Commented Nov 8, 2014 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
    Commented Nov 8, 2014 at 21:13
  • $\begingroup$ Some context for the question, in case people were wondering: academia.stackexchange.com/questions/31410/… $\endgroup$
    – apnorton
    Commented Nov 8, 2014 at 21:15

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\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 Dougherty
    Commented Nov 8, 2014 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
    Commented Nov 8, 2014 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 Dougherty
    Commented Nov 8, 2014 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 Dougherty
    Commented Nov 8, 2014 at 22:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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