Percolation Graph Matching Methods
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-nmatrix containing vertex similarities.- r
A number. Threshold of neighboring pair scores.
- ExpandWhenStuck
A logical. TRUE if expand the seed set when Percolation algorithm stops before matching all the vertices.
Value
graph_match_percolation 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\)
- match_order
the order of vertices getting matched
- seeds
a vector of logicals indicating if the corresponding vertex is a seed
References
L. Yartseva and M. Grossglauser (2013), On the performance of percolation graph matching. COSN, Boston, MA, USA, pages 119–130.
E. Kazemi, S. H. Hassani, and M. Grossglauser (2015), Growing a graph matching from a handful of seeds. Proc. of the VLDB Endowment, 8(10):1010–1021.
Examples
# match G_1 & G_2 using percolation graph matching method
cgnp_pair <- sample_correlated_gnp_pair(n = 20, corr = 0.5, p = 0.8)
g1 <- cgnp_pair$graph1
g2 <- cgnp_pair$graph2
seeds <- 1:10 <= 3
GM_perco <- gm(g1, g2, seeds, method = "percolation", r = 2, ExpandWhenStuck = FALSE)
GM_perco
#> gm(A = g1, B = g2, seeds = seeds, method = "percolation", r = 2,
#> ExpandWhenStuck = FALSE)
#>
#> Match (20 x 20):
#> corr_A corr_B
#> 1 1 1
#> 2 2 2
#> 3 3 3
#> 4 4 8
#> 5 5 12
#> 6 6 11
#> 7 7 17
#> 8 8 6
#> 9 9 19
#> 10 10 10
#> 11 11 18
#> 12 12 9
#> 13 13 5
#> 14 14 14
#> 15 15 15
#> 16 16 16
#> 17 17 4
#> 18 18 7
#> 19 19 13
#> 20 20 20
# matching accuracy with the true alignment being the identity
mean(GM_perco$corr_A == GM_perco$corr_B)
#> [1] 0.4
GM_perco$match_order
#> [1] 1 2 3 7 13 6 19 4 18 15 5 11 14 9 8 16 10 17 12 20
summary(GM_perco, g1, g2, true_label = 1:20)
#> Call: gm(A = g1, B = g2, seeds = seeds, method = "percolation", r = 2,
#> ExpandWhenStuck = FALSE)
#>
#> # Matches: 17
#> # True Matches: 5, # Seeds: 3, # Vertices: 20, 20
#>
#> common_edges 132.000000
#> missing_edges 20.000000
#> extra_edges 17.000000
#> fnorm 8.602325
plot(g1[], g2[], GM_perco)
# expand when stuck
GM_exp <- gm(g1, g2, seeds, method = "percolation", r = 4, ExpandWhenStuck = TRUE)
GM_exp
#> gm(A = g1, B = g2, seeds = seeds, method = "percolation", r = 4,
#> ExpandWhenStuck = TRUE)
#>
#> Match (20 x 20):
#> corr_A corr_B
#> 1 1 1
#> 2 2 2
#> 3 3 3
#> 4 4 9
#> 5 5 10
#> 6 6 15
#> 7 7 20
#> 8 8 6
#> 9 9 19
#> 10 10 17
#> 11 11 4
#> 12 12 5
#> 13 13 12
#> 14 14 18
#> 15 15 8
#> 16 16 7
#> 17 17 14
#> 18 18 11
#> 19 19 13
#> 20 20 16