GMPro (version 0.1.0)

EEpost: Post-processing step for edge-exploited graph matching.

Description

Funtions DPmatching or DPedge can produce a preliminary graph matching result. This function, EEPost works on refining the result iteratively. In addition, EEpost is able to provide a convergence indicator vector FLAG for each matching as a reference for the certainty about the matching since in practice,it has been observed that the true matches usually reach the convergence and stay the same after a few iterations, while the false matches may keep changing in the iterations.

Usage

EEpost(W = NULL, A, B, rep, tau = NULL, d = NULL, matching = NULL)

Arguments

W

A distance matrix.

A, B

Two 0/1 adjacency matrices.

rep

A positive integer, indicating the number of iterations.

tau

A positive threshold. The default value is \(rep/10\).

d

A positive integer, indicating the number of candidate matching. The default value is 1.

matching

A preliminary matching result for EEpost. If matching is null, EEpost will apply DPedge accordingly to generate the initial matching.

Value

Dist

The distance matrix between two graphs.

match

A vector containing matching results.

FLAG

An indicator vector indicating whether the matching result is converged. 0 for No and 1 for Yes.

converged.match

Converged match result. NA indicates the matching result for a certain node is not v=convergent.

converged.size

The number of converged nodes.

Details

Similar to function EEpre, EEpost uses maximum bipartite matching to maximize the number of common neighbours for the matched vertices with the knowledge of a preliminary matching result by defining the similarity between \(i \in A\) and \(j \in B\) as the number of common neighbours between \(i\) and \(j\) according to the preliminary matching. Then, given a matching result \(\Pi_t\), post processing step is to seek a refinement \(\Pi_{t+1}\) satisfying \(\Pi_{t+1} \in\) argmax \(\langle \Pi, A \Pi_t B \rangle\), where \(\Pi\) is a permutation matrix of dimension \((n_A, n_B)\).

Examples

# NOT RUN {
set.seed(2020)
n = 10;p = 1; q = 1/2; s = 1
Parent = matrix(rbinom(n*n, 1, q), nrow = n, ncol = n)
Parent[lower.tri(Parent)] = t(Parent)[lower.tri(Parent)]
diag(Parent) <- 0
### Generate graph A
dA = matrix(rbinom(n*n, 1, s), nrow = n, ncol=n)
dA[lower.tri(dA)] = t(dA)[lower.tri(dA)]
A1 = Parent*dA;
tmp = rbinom(n, 1, p)
n.A = length(which(tmp == 1))
indA = sample(1:n, n.A, replace = FALSE)
A = A1[indA, indA]
### Generate graph B
dB = matrix(rbinom(n*n, 1, s), nrow = n, ncol=n)
dB[lower.tri(dB)] = t(dB)[lower.tri(dB)]
B1 = Parent*dB
tmp = rbinom(n, 1, p)
n.B = length(which(tmp == 1))
indB = sample(1:n, n.B, replace = FALSE)
B = B1[indB, indB]
matching1= DPmatching(A, B)$Dist
EEpost(A = A, B = B, rep = 10, d = 5)
EEpost(A = A, B = B, rep = 10, d = 5, matching = matching1)

# }