gm_Umeyama: Spectral Graph Matching Methods: Umeyama Algorithm

In dpmcsuss/iGraphMatch: Tools for Graph Matching

Spectral Graph Matching Methods: Umeyama Algorithm

Description

Spectral Graph Matching Methods: Umeyama Algorithm

Usage

graph_match_Umeyama(A, B, seeds = NULL, similarity = NULL)

Arguments

A	A matrix, igraph object, or list of either.
B	A matrix, igraph object, or list of either.
seeds	A vector of integers or logicals, a matrix or a data frame. If the seed pairs have the same indices in both graphs then seeds can be a vector. If not, seeds must be a matrix or a data frame, with the first column being the indices of G_1 and the second column being the corresponding indices of G_2.
similarity	A matrix. An n-by-n matrix containing vertex similarities.

Value

graph_match_Umeyama returns an object of class "graphMatch" which is a list containing the following components:

corr_A

matching correspondence in G_1

corr_B

matching correspondence in G_2

soft

the functional similarity score matrix with which one can extract more than one matching candidates

lap_method

Choice for solving the LAP

seeds

a vector of logicals indicating if the corresponding vertex is a seed

References

S. Umeyama (1988), An eigendecomposition approach to weighted graph matching problems. IEEE TPAMI. USA, pages 695-703.

Examples

# match G_1 & G_2 using Umeyama algorithm
G <- sample_correlated_gnp_pair(10, .9, .5)
g1 <- G$graph1
g2 <- G$graph2
startm <- matrix(0, 10, 10)
diag(startm)[1:4] <- 1

GM_Umeyama <- gm(g1, g2, similarity = startm, method = "Umeyama")
GM_Umeyama
# generate the corresponding permutation matrix
GM_Umeyama[]

summary(GM_Umeyama, g1, g2)
# visualize the edge-wise matching performance
plot(g1, g2, GM_Umeyama)
plot(g1[], g2[], GM_Umeyama)

dpmcsuss/iGraphMatch documentation built on May 22, 2024, 8:52 p.m.