给定顶点对应关系的图匹配 — match_vertices • igraph 网络分析库

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

用法

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

参数

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

值

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

详细信息

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

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

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

参考文献

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

参见

作者

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

示例


# 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_adjacency_matrix(g1)
B <- as_adjacency_matrix(g2)
P <- match_vertices(A, B, m = 3, start = diag(rep(1, nrow(A) - 3)), 20)
P
#> $corr
#>      [,1] [,2]
#> [1,]    4    4
#> [2,]    5    8
#> [3,]    6    6
#> [4,]    7   10
#> [5,]    8    9
#> [6,]    9    7
#> [7,]   10    5
#> 
#> $P
#>       [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
#>  [1,]    1    0    0    0    0    0    0    0    0     0
#>  [2,]    0    1    0    0    0    0    0    0    0     0
#>  [3,]    0    0    1    0    0    0    0    0    0     0
#>  [4,]    0    0    0    1    0    0    0    0    0     0
#>  [5,]    0    0    0    0    0    0    0    1    0     0
#>  [6,]    0    0    0    0    0    1    0    0    0     0
#>  [7,]    0    0    0    0    0    0    0    0    0     1
#>  [8,]    0    0    0    0    0    0    0    0    1     0
#>  [9,]    0    0    0    0    0    0    1    0    0     0
#> [10,]    0    0    0    0    1    0    0    0    0     0
#> 
#> $D
#> 7 x 7 sparse Matrix of class "dgCMatrix"
#>                   
#> [1,] 1 . . . . . .
#> [2,] . . . . 1 . .
#> [3,] . . 1 . . . .
#> [4,] . . . . . . 1
#> [5,] . . . . . 1 .
#> [6,] . . . 1 . . .
#> [7,] . 1 . . . . .
#>