EEpre {GMPro}

Edge exploited degree profile graph matching with preprocessing.

Description

This function uses seeds to compute edge-exploited matching results. Seeds are nodes with high degrees. EEpre uses seeds to extend the matching of seeds to the matching of all nodes.

Usage

EEpre(A, B, d, seed = NULL, AB_dist = NULL)

Arguments

A, B

Two 0/1 addjacency matrices.

d

A positive integer, indicating the number of candicate matching.

seed

A matrix indicating pair of seeds. seed can be null.

AB_dist

A nonnegative distance matrix, which can be null. If AB_dist is null, EEpre will apply DPdistance to find it.

Details

The high degree vertices have many neighbours and enjoy ample information for a successful matching. Thereforem, this function employ these high degree vertices to match other nodes. If the information of seeds is unavailable, EEpre will conduct a grid search grid search to find the optimal collection of seeds. These vertices are expected to have high degress and their distances are supposed to be the smallest among the pairs in consideration.

Value

Dist

The distance matrix between two graphs

Z

An indicator matrix. Entry Z_{i, j} = 1 indicates a matching between node i \in A and node j \in B, 0 otherwise.

Examples

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]
EEpre(A = A, B = B, d = 5)