gm_perco: Percolation Graph Matching Methods

In dpmcsuss/iGraphMatch: Tools for Graph Matching

Percolation Graph Matching Methods

Description

Percolation Graph Matching Methods

Usage

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

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.

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

# 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

dpmcsuss/iGraphMatch documentation built on Feb. 15, 2024, 3:26 p.m.