1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
|
% Generated by roxygen2: do not edit by hand
% Please edit documentation in R/sgm.R
\name{match_vertices}
\alias{match_vertices}
\alias{seeded.graph.match}
\title{Match Graphs given a seeding of vertex correspondences}
\usage{
match_vertices(A, B, m, start, iteration)
}
\arguments{
\item{A}{a numeric matrix, the adjacency matrix of the first graph}
\item{B}{a numeric matrix, the adjacency matrix of the second graph}
\item{m}{The number of seeds. The first \code{m} vertices of both graphs are
matched.}
\item{start}{a numeric matrix, the permutation matrix estimate is
initialized with \code{start}}
\item{iteration}{The number of iterations for the Frank-Wolfe algorithm}
}
\value{
A numeric matrix which is the permutation matrix that determines the
bijection between the graphs of \code{A} and \code{B}
}
\description{
Given two adjacency matrices \code{A} and \code{B} of the same size, match
the two graphs with the help of \code{m} seed vertex pairs which correspond
to the first \code{m} rows (and columns) of the adjacency matrices.
}
\details{
The approximate graph matching problem is to find a bijection between the
vertices of two graphs , such that the number of edge disagreements between
the corresponding vertex pairs is minimized. For seeded graph matching, part
of the bijection that consist of known correspondences (the seeds) is known
and the problem task is to complete the bijection by estimating the
permutation matrix that permutes the rows and columns of the adjacency
matrix of the second graph.
It is assumed that for the two supplied adjacency matrices \code{A} and
\code{B}, both of size \eqn{n\times n}{n*n}, the first \eqn{m} rows(and
columns) of \code{A} and \code{B} correspond to the same vertices in both
graphs. That is, the \eqn{n \times n}{n*n} permutation matrix that defines
the bijection is \eqn{I_{m} \bigoplus P} for a \eqn{(n-m)\times
(n-m)}{(n-m)*(n-m)} permutation matrix \eqn{P} and \eqn{m} times \eqn{m}
identity matrix \eqn{I_{m}}. The function \code{match_vertices()} estimates
the permutation matrix \eqn{P} via an optimization algorithm based on the
Frank-Wolfe algorithm.
See references for further details.
}
\examples{
# require(Matrix)
g1 <- sample_gnp(10, 0.1)
randperm <- c(1:3, 3 + sample(7))
g2 <- sample_correlated_gnp(g1, corr = 1, p = g1$p, permutation = randperm)
A <- as_adjacency_matrix(g1)
B <- as_adjacency_matrix(g2)
P <- match_vertices(A, B, m = 3, start = diag(rep(1, nrow(A) - 3)), 20)
P
}
\references{
Vogelstein, J. T., Conroy, J. M., Podrazik, L. J., Kratzer, S.
G., Harley, E. T., Fishkind, D. E.,Vogelstein, R. J., Priebe, C. E. (2011).
Fast Approximate Quadratic Programming for Large (Brain) Graph Matching.
Online: \url{https://arxiv.org/abs/1112.5507}
Fishkind, D. E., Adali, S., Priebe, C. E. (2012). Seeded Graph Matching
Online: \url{https://arxiv.org/abs/1209.0367}
}
\seealso{
\code{\link[=sample_correlated_gnp]{sample_correlated_gnp()}},\code{\link[=sample_correlated_gnp_pair]{sample_correlated_gnp_pair()}}
}
\author{
Vince Lyzinski \url{https://www.ams.jhu.edu/~lyzinski/}
}
\concept{sgm}
\keyword{graphs}
|
