iGraphMatch (version 2.0.5)

graph_match_percolation: Percolation Graph Matching Methods

Description

Percolation Graph Matching Methods

Usage

graph_match_percolation(
  A,
  B,
  seeds,
  similarity = NULL,
  r = 2,
  ExpandWhenStuck = FALSE
)

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

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.

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.

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

# matching accuracy with the true alignment being the identity
mean(GM_perco$corr_A == GM_perco$corr_B)
GM_perco$match_order

summary(GM_perco, g1, g2, true_label = 1:20)
plot(g1[], g2[], GM_perco)

# expand when stuck
GM_exp <- gm(g1, g2, seeds, method = "percolation", r = 4, ExpandWhenStuck = TRUE)
GM_exp