gm_isorank: Spectral Graph Matching Methods: IsoRank Algorithm

In dpmcsuss/iGraphMatch: Tools for Graph Matching

Spectral Graph Matching Methods: IsoRank Algorithm

Description

Spectral Graph Matching Methods: IsoRank Algorithm

Usage

graph_match_IsoRank(
  A,
  B,
  seeds = NULL,
  similarity,
  max_iter = 50,
  lap_method = "greedy"
)

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.
max_iter	A number. Maximum number of replacing matches.
lap_method	Choice of method to extract mapping from score matrix. One of "greedy" or "LAP".

Value

graph_match_IsoRank 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

seeds

a vector of logicals indicating if the corresponding vertex is a seed

soft

the functional similarity score matrix obtained from the power method with which one can extract more than one matching candidates

match_order

the order of vertices getting matched

lap_method

Method for extracting node mapping

References

R. Singh, J. Xu, B. Berger (2008), Global alignment of multiple protein interaction networks with application to functional orthology detection. Proceedings of the National Academy of Science. USA, pages 12763-12768.

Examples

cgnp_pair <- sample_correlated_gnp_pair(n = 10, corr =  0.3, p =  0.5)
g1 <- cgnp_pair$graph1
g2 <- cgnp_pair$graph2
# match G_1 & G_2 using IsoRank algorithm
startm <- as.matrix(init_start(start = "bari", nns = 10, soft_seeds = 1:4))

GM_IsoRank <- gm(g1, g2, similarity = startm, method = "IsoRank", lap_method = "greedy")
GM_IsoRank
summary(GM_IsoRank, g1, g2, true_label = 1:10)

GM_IsoRank[] # get the corresponding permutation matrix
GM_IsoRank %*% g2 # permute the second graph according to match result: PBP^T
GM_IsoRank %*% g2[] # output permuted matrix

# Visualize the edge-wise matching performance
plot(g1, g2, GM_IsoRank)
plot(g1[], g2[], GM_IsoRank)

dpmcsuss/iGraphMatch documentation built on May 22, 2024, 8:52 p.m.