DeltaCon structural distance between two graphs

DeltaCon-0 similarity from fast-belief-propagation affinities: for each graph \(S = (I + \epsilon^2 D - \epsilon A)^{-1}\) (eq. 2.2), with \(\epsilon = 1/(1 + \max_i d_{ii})\) taken over both graphs so one constant is shared; the distance is the root Euclidean (Matusita) distance \(d = \sqrt{\sum_{ij} (\sqrt{s_{1,ij}} - \sqrt{s_{2,ij}})^2}\) (eq. 3.3) and the similarity is \(1/(1+d)\) (Algorithm 1).

Usage

Strdis(G1, G2, eps = NULL)

structural_distance(G1, G2, eps = NULL)

Arguments

G1, G2

Adjacency matrices on the same node set.

eps

Optional override of the influence constant.

Value

List with distance, similarity, estimate, eps, n.

References

Koutra, D., Vogelstein, J. T. and Faloutsos, C. (2013). DeltaCon: a principled massive-graph similarity function. SIAM SDM 2013, arXiv:1304.4657, eqs. (2.2), (3.3), Table 1, Algorithm 1.

Examples

A <- matrix(0, 3, 3); A[1, 2] <- A[2, 1] <- 1; A[2, 3] <- A[3, 2] <- 1
B <- A; B[1, 3] <- B[3, 1] <- 1
Strdis(A, B)
#> $distance
#> [1] 0.4868302
#> 
#> $similarity
#> [1] 0.6725718
#> 
#> $estimate
#> [1] 0.6725718
#> 
#> $eps
#> [1] 0.3333333
#> 
#> $n
#> [1] 3
#> 
#> $method
#> [1] "DeltaCon-0 (FaBP affinities, RootED distance)"
#>