r - 基于节点权重构建图的优化算法

标签 r algorithm igraph

我正在尝试改进一个功能，以根据从某些节点属性计算出的分数来构建网络。该函数试图从最大化节点属性乘积的图中找到最佳子网。

该函数从一个随机节点开始，并开始在第一个邻居中搜索，如果有一些邻居的节点分数满足阈值，则将邻居添加到第一个节点并继续该过程，直到不再添加(添加邻居不会产生所需的分数增量)。如果第一个邻居中没有节点产生分数的增量，则该函数将查找第二个邻居。在这种情况下，很可能有几条路径连接节点(2 度邻居)，在这种特定情况下，选择的路径将是最短且权重最高的路径(节点属性之一)。

我可以对代码进行一些并行处理，尽管我不知道如何在此类函数中实现它。

函数如下:

build_network <-
function (G, seed, d= 2){
    net <- G
    d <- d

    score.fun<-function(g){
    Za <- sum(V(g)$weight*V(g)$RWRNodeweight)/sqrt(sum(V(g)$RWRNodeweight^2))
    k <- vcount(g)
    tmp <- genesets.length.null.stat[[as.character(k)]] # genesets.length.null.stat is a list with the median of Za and sd of Za calculated for 1000 replicates of networks of size k
    Sa <- (Za-tmp[1])/tmp[2]
    }

    best.fun<-function(in.nodes,out.nodes)  {
    score<-(-Inf); best<-character()
    for(node in out.nodes){
     subG.update<-induced.subgraph(net, c(in.nodes,node))
     if( score.fun(subG.update) > score ){
        score<-score.fun(subG.update)
        best<-node
        }
    }
    list("node"=best,"score"=score)
    }   

    subG <- induced.subgraph(net, seed)
    if (!is.connected(subG)) {          #the seed must be connected
        stop("Input seeds are disjoint")
    }

    while (TRUE) {
        in.nodes <- V(subG)$name
        node_num <- vcount(subG)
        subsum <- score.fun(subG)
        #subx <- V(subG)$name
        for (rad in 1:d) {
            tmp.neigh <- unlist(neighborhood(net, order = rad, nodes = V(subG)$name)) 
            pot.nodes <- V(net)[tmp.neigh]$name
            out.nodes <- setdiff(pot.nodes, in.nodes)
            if (length(out.nodes) == 0) break

            best_node<-best.fun(in.nodes, out.nodes) 
            new_score<-best_node$score
            best_node<-best_node$node 

            if (new_score > subsum + 0.01) {
                tmp <- unlist(lapply(best_node, function(x) node2treePath(net,V(subG)$name, x))) # node2treePath is a function to retrieve the shortest path with the highest node weights
                in.nodes <- c(tmp, V(subG)$name)
                subG <- induced.subgraph(net, in.nodes)
                break
            }
        }
        if (node_num == vcount(subG)) break
    }
    return(subG)
}

我正在尝试将此函数应用于约 10,000 个节点的图形。这里将是运行该函数的代码的近似值

### generate some example data
library(igraph)
my_graph <- erdos.renyi.game(10000, 0.0003)
V(my_graph)$name <- 1:vcount(my_graph)
V(my_graph)$weight <- rnorm(10000)
V(my_graph)$RWRNodeweight <- runif(10000, min=0, max=0.05)

### Run the function
sublist = list()
for (node in V(G)$name) {
    subnet <- build_network(G, node, d)
    sublist[[node]] <- subnet }

编辑:这里是 dput的 head(genesets.length.null.stat) 

structure(list(`1` = c(1.01397367504035, 1.18858228819048), `2` = c(1.61970348041337, 1.30189433386605), `3` = c(2.11767222957028, 1.36222065695878), `4` = c(2.47710421934929, 1.36968129959296), `5` = c(2.776011866622, 1.36318885187196), `6` = c(3.16885126246671, 1.42577861995897)), .Names = c("1", "2", "3", "4", "5", "6"))

这是 node2treePath功能:

node2treePath <- function (G, Tnodes, node){

tmp.path <- get.all.shortest.paths(G, node, Tnodes)$res
tmp.l <- unlist(lapply(tmp.path, length))
index <- which(tmp.l == min(tmp.l))

tmp.path = tmp.path[index]
tmp.sum <- unlist(lapply(tmp.path, function(x)return(sum(V(G)[x]$weight))))
index <- which(tmp.sum == max(tmp.sum))

selected.path = tmp.path[index]
collect <- unlist(lapply(selected.path, function(x)return(V(G)[x]$name)))

return(collect)
}

最佳答案

对于您想要执行的逻辑(我想您可能希望以与上述答案不兼容的方式进行更改)，以下代码大约快 10 倍 30%。我使用了 Rprof 和 profr 并以简单的方式重新编码了一些慢位，例如不传递命名列表对，只是来自您的一个函数的匿名对。包含 genesets.length.null.stat 值对的数字命名列表效率非常低。我用两个数字向量替换了它。您还多次调用“V”函数，这是一个很大的时间消耗:如您所见，您可以调用它一次，然后根据需要查询结果。

# node2treePath is a function to retrieve the shortest path with the highest node weights
node2treePath_jw <- function(G, Tnodes, node){

  tmp.path <- get.all.shortest.paths(G, node, Tnodes)$res
  tmp.l <- vapply(tmp.path, length, integer(1))
  index <- which(tmp.l == min(tmp.l))

  tmp.path = tmp.path[index]
  Vg <- V(G)
  tmp.sum <- vapply(tmp.path, function(x) sum(Vg[x]$weight), numeric(1))
  index <- which(tmp.sum == max(tmp.sum))

  selected.path = tmp.path[index]
  sapply(selected.path, function(x) Vg[x]$name)
}

build_network_jw <- function(net, seed, d= 2){

  score.fun <- function(Vg, k){
    Za <- sum(Vg$weight * Vg$RWRNodeweight) / sqrt(sum(Vg$RWRNodeweight^2))
    (Za - genesets_jack_a[k]) / genesets_jack_b[k]
  }

  best.fun_jw <- function(in.nodes, out.nodes)  {
    score <- (-Inf)
    best <- character()
    for (node in out.nodes) {
      subG.update <- induced.subgraph(net, c(in.nodes,node))
      Vsgu <- V(subG.update)
      Vsgu_count <- vcount(subG.update)
      sf <- score.fun(Vsgu, Vsgu_count)
      if (sf > score) {
        score <- sf
        best <- node
      }
    }
    list(best, score)
  }

  subG <- induced.subgraph(net, seed)
  if (!is.connected(subG)) {          #the seed must be connected
    stop("Input seeds are disjoint")
  }

  while (TRUE) {
    VsubG <- V(subG)
    Vnet <- V(net)
    in.nodes <- VsubG$name
    node_num <- vcount(subG)
    subsum <- score.fun(VsubG, node_num)

    for (rad in 1:d) { # d = 2
      tmp.neigh <- unlist(neighborhood(net, order = rad, nodes = VsubG$name))
      pot.nodes <- Vnet[tmp.neigh]$name
      out.nodes <- setdiff(pot.nodes, in.nodes)
      if (length(out.nodes) == 0) break

      best_node <- best.fun_jw(in.nodes, out.nodes)
      new_score <- best_node[[2]]
      best_node <- best_node[[1]]

      if (new_score > subsum + 0.01) {
        tmp <- sapply(best_node, function(x) node2treePath_jw(net, VsubG$name, x))
        in.nodes <- c(tmp, VsubG$name)
        subG <- induced.subgraph(net, in.nodes)
        break
      }
    }
    if (node_num == vcount(subG)) break
  }
  subG
}

node2treePath <- function (G, Tnodes, node){

  tmp.path <- get.all.shortest.paths(G, node, Tnodes)$res
  tmp.l <- unlist(lapply(tmp.path, length))
  index <- which(tmp.l == min(tmp.l))

  tmp.path = tmp.path[index]
  tmp.sum <- unlist(lapply(tmp.path, function(x)return(sum(V(G)[x]$weight))))
  index <- which(tmp.sum == max(tmp.sum))

  selected.path = tmp.path[index]
  collect <- unlist(lapply(selected.path, function(x)return(V(G)[x]$name)))

  return(collect)
}


build_network <- function (net, seed, d= 2){

  #genesets.length.null.stat <- structure(list(`1` = c(1.01397367504035, 1.18858228819048), `2` = c(1.61970348041337, 1.30189433386605), `3` = c(2.11767222957028, 1.36222065695878), `4` = c(2.47710421934929, 1.36968129959296), `5` = c(2.776011866622, 1.36318885187196), `6` = c(3.16885126246671, 1.42577861995897)), .Names = c("1", "2", "3", "4", "5", "6"))
  genesets.length.null.stat <- lapply(1:500, function(x) c(runif(1)+x, runif(1)+x))
  names(genesets.length.null.stat) <- 1:500

  score.fun<-function(g){
    Za <- sum(V(g)$weight*V(g)$RWRNodeweight)/sqrt(sum(V(g)$RWRNodeweight^2))
    k <- vcount(g)
    tmp <- genesets.length.null.stat[[as.character(k)]] # genesets.length.null.stat is a list with the median of Za and sd of Za calculated for 1000 replicates of networks of size k
    Sa <- (Za-tmp[1])/tmp[2]
  }

  best.fun <- function(in.nodes,out.nodes)  {
    score<-(-Inf); best<-character()
    for (node in out.nodes){
      subG.update<-induced.subgraph(net, c(in.nodes,node))
      if (score.fun(subG.update) > score) {
        score<-score.fun(subG.update)
        best<-node
      }
    }
    list("node"=best,"score"=score)
  }

  subG <- induced.subgraph(net, seed)
  if (!is.connected(subG)) {          #the seed must be connected
    stop("Input seeds are disjoint")
  }

  while (TRUE) {
    in.nodes <- V(subG)$name
    node_num <- vcount(subG)
    subsum <- score.fun(subG)
    #subx <- V(subG)$name
    for (rad in 1:d) {
      tmp.neigh <- unlist(neighborhood(net, order = rad, nodes = V(subG)$name))
      pot.nodes <- V(net)[tmp.neigh]$name
      out.nodes <- setdiff(pot.nodes, in.nodes)
      if (length(out.nodes) == 0) break

      #message("length in.nodes = ", length(in.nodes))
      #message("length out.nodes = ", length(out.nodes))

      best_node<-best.fun(in.nodes, out.nodes)
      new_score<-best_node$score
      best_node<-best_node$node

      if (new_score > subsum + 0.01) {
        tmp <- unlist(lapply(best_node, function(x) node2treePath(net,V(subG)$name, x))) # node2treePath is a function to retrieve the shortest path with the highest node weights
        in.nodes <- c(tmp, V(subG)$name)
        subG <- induced.subgraph(net, in.nodes)
        break
      }
    }
    if (node_num == vcount(subG)) break
  }
  subG
}

library(igraph)
library(profr)



library(igraph)
library(profr)

#genesets.length.null.stat <- lapply(1:500, function(x) c(runif(1)+x, runif(1)+x))
#names(genesets.length.null.stat) <- 1:500

set.seed(1)
genesets_jack_a = runif(500) + 1:500
genesets_jack_b = runif(500) + 1:500

do_it_jw <- function(n = 1000){

  my_graph <- erdos.renyi.game(n, 0.0003)
  V(my_graph)$name <- 1:vcount(my_graph)
  V(my_graph)$weight <- rnorm(n)
  V(my_graph)$RWRNodeweight <- runif(n, min = 0, max = 0.05)

  ### Run the function
  sublist = list()
  Vmg <- V(my_graph)
  for (node in Vmg$name) {
    #message(node)
    subnet <- build_network_jw(my_graph, node, 2)
    sublist[[node]] <- subnet }
}

do_it <- function(n = 1000){

  my_graph <- erdos.renyi.game(n, 0.0003)
  V(my_graph)$name <- 1:vcount(my_graph)
  V(my_graph)$weight <- rnorm(n)
  V(my_graph)$RWRNodeweight <- runif(n, min = 0, max = 0.05)

  ### Run the function
  sublist = list()
  Vmg <- V(my_graph)
  for (node in Vmg$name) {
    #message(node)
    subnet <- build_network(my_graph, node, 2)
    sublist[[node]] <- subnet }
}

library(microbenchmark)
mb <- microbenchmark(do_it(1000), do_it_jw(1000), times = 5)
print(mb)

关于r - 基于节点权重构建图的优化算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/33240240/

上一篇：algorithm - apache spark 上的不相交集

下一篇：algorithm - 谷歌面试算法拼图 : expected size of the largest connected component in a random simple graph (N nodes, N 边)？

相关文章：

r - 使用 ggplot2 的线图中误差线的宽度

java - 在二叉树中查找节点深度而不是 BST

javascript - Heapsort算法，把最小的元素放在最后

java - 回溯算法中的InputMismatchException

r - 带有 R : How to disable forward linking? 的 igraph/visNetwork

r - iGraph + Plotly 创建随机连接

python - 加权斜率一种算法？ (从 Python 移植到 R)

read.xlsx 需要很长的时间和大量的内存

r - 如何将绘图保存在文件夹中？

python - 将 neo4j 查询结果加载到 python 的 `igraph` 图中

©2024 IT工具网  联系我们