在距离矩阵中找到边较短的三角形

Question

我试图在距离矩阵中找到三角形，其中直接路径比通过另一点的路径长。目标是减少全连接图中的边数。该函数适用于较低的 n 值，但适用于较大的值。我正试图找出如何加快这个过程。

我曾希望通过将数据保持为矩阵并对其进行处理，这样过程将被向量化并且速度非常快，但是，这并没有发生。

我曾尝试使用 lineprof 并单击以降低功能，但我不明白它在告诉我什么。我不知道 igraph 中是否有一些功能可以帮助？

library(purrr);library(magrittr); library(lineprof);library(shiny)

#The function used to find triangles
RemoveTri <- function(s){
  Smat<- col(s) 
  RemoveEdge <- 1:ncol(s) %>%
  map(~{
  print(.x)
    LogicMat <- s + s[,.x][Smat] < (s[,.x]) #I used this method to avoid transposing
    matrix(data = rowSums(LogicMat, na.rm = TRUE ) > 0, ncol = 1) #TRUE means edge can be removed
  }) %>%
  do.call(cbind,.)
  s[RemoveEdge] <- NA
return(s)
}

#This function just creates a dataframe
CreateData <- function(n, seed){
  set.seed(seed)
  s <- matrix(rnorm(n^2), n) #%>% cor
  s <- s +abs(min(s))+0.001
  s[lower.tri(s)] = t(s)[lower.tri(s)]
  diag(s) <- 0
  return(s)
 }

#Using a small amount of data
s <- CreateData(100, 876)
RemoveTri(s)

#using a larger amount of data
s2 <- CreateData(4000, 876)
RemoveTri(s2)

l <- lineprof(RemoveTri(s))
shine(l)

Answer 1

由于矩阵是对称的，可以通过仅计算下三角矩阵来加快处理速度。通过这样做，我们可以将计算次数从 $n^3$ 减少到
$\frac{n}{6}(2n^2+3n+1)$ 给出了 $\frac{(2n+1)(n+1)}{6n^2}$ 的比率，结果约为 2 /3 当n很大时计算总数减少。

调整后的功能如下

此函数启动缓慢，随着计算的行数增加而加快。在 n 值较小时，由于额外的开销，它比原始函数慢，但当 n 大于几百时，它会变得更快。

RemoveTri  <- function(s){
      Smat <- col(s) 

      RemoveEdge <- 1:ncol(s) %>%
      map(~{
        print(.x)
        TargetRows <- .x:ncol(s)
        LogicMat <- s[TargetRows,TargetRows, drop = F] + s[TargetRows,.x][Smat[1:length(TargetRows),1:length(TargetRows)]]  < s[TargetRows,.x]


        matrix(data = c(rep(NA, .x-1),rowSums(LogicMat, na.rm = TRUE ) > 0), ncol = 1) #TRUE means edge should be removed

      }) %>%
      do.call(cbind,.)

      RemoveEdge[upper.tri(RemoveEdge)]  <- t(RemoveEdge)[upper.tri(RemoveEdge)]

      s[RemoveEdge] <- NA 

    s

}

在距离矩阵中找到边较短的三角形

Find triangles with shorter edges in a distance matrix

r

matrix

igraph

adjacency-matrix