R igraph 手册页

match_vertices {igraph}

R 文档

根据顶点对应关系的种子匹配图

描述

给定两个大小相同的邻接矩阵 A 和 B，使用 m 个种子顶点对来匹配这两个图，这些种子顶点对对应于邻接矩阵的前 m 行（和列）。

用法

match_vertices(A, B, m, start, iteration)

参数

A	一个数值矩阵，第一个图的邻接矩阵
B	一个数值矩阵，第二个图的邻接矩阵
m	种子的数量。两个图的前 m 个顶点是匹配的。
开始	一个数值矩阵，排列矩阵估计值以 start 初始化
iteration	Frank-Wolfe 算法的迭代次数

详细信息

近似图匹配问题是找到两个图的顶点之间的双射，使得对应顶点对之间的边不一致的数量最小化。对于种子图匹配，部分由已知对应关系（种子）组成的双射是已知的，问题任务是通过估计排列矩阵来完成双射，排列矩阵排列第二个图的邻接矩阵的行和列。

假设对于提供的两个邻接矩阵 A 和 B，它们的大小均为 n\times n，A 和 B 的前 m 行（和列）对应于两个图中的相同顶点。也就是说，定义双射的 n \times n 排列矩阵是 I_{m} \bigoplus P，其中 P 是一个 (n-m)\times (n-m) 排列矩阵，I_{m} 是一个 m 乘以 m 的单位矩阵。函数 match_vertices 通过基于 Frank-Wolfe 算法的优化算法估计排列矩阵 P。

有关更多详细信息，请参阅参考文献。

值

一个数值矩阵，它是确定 A 和 B 图之间双射的排列矩阵

作者

Vince Lyzinski https://www.ams.jhu.edu/~lyzinski/

参考

Vogelstein, J. T., Conroy, J. M., Podrazik, L. J., Kratzer, S. G., Harley, E. T., Fishkind, D. E.,Vogelstein, R. J., Priebe, C. E. (2011). 用于大型（脑）图匹配的快速近似二次规划。在线： https://arxiv.org/abs/1112.5507

Fishkind, D. E., Adali, S., Priebe, C. E. (2012). 种子图匹配在线： https://arxiv.org/abs/1209.0367

参见

sample_correlated_gnp,sample_correlated_gnp_pair

示例

 #require(Matrix)
 g1 <- sample_gnp(10, 0.1)
 randperm <- c(1:3, 3+sample(7))
 g2 <- sample_correlated_gnp(g1, corr=1, p=g1$p, permutation=randperm)
 A  <- as.matrix(get.adjacency(g1))
 B  <- as.matrix(get.adjacency(g2))
 P  <- match_vertices(A, B, m=3, start=diag(rep(1, nrow(A)-3)), 20)
 P

---