igraph 是否具有生成受权重限制的子图的函数？ dfs，random_walk

Question

我在 igraph R 环境中有一个加权图。

并且需要递归地获取子图，从任意一个随机节点开始。每个子图中的权重总和必须减去一个数字。

深度优先搜索算法似乎可以解决这个问题。还有随机游走函数。

有人知道哪个 igraph 函数可以解决这个问题吗？

Answer 1

下面这里做了，不过好像没有效果。

#######Example code
g <- make_tree(10, children = 2, mode = c("undirected"))
s <- seq(1:19)
g <- set_edge_attr(g, "weight", value= s)
plot(g)
is_weighted(g)
E(g)$weight


threshold <- 5 
eval <- function(r){
  #r <- 10
  Vertice_dfs <- dfs(g, root = r)
  Sequencia <- as.numeric(Vertice_dfs$order)
  for (i in 1:length(Sequencia)) {
   #i <- 2
   # function callback by vertice to dfs
   f.in <- function(graph, data, extra) {
    data[1] == Sequencia[i]-1
   }
   # DFS algorithm to the function
   dfs <- dfs(g, root = r,in.callback=f.in) 
   # Vertices resulted from DFS 
   dfs_eges <- na.omit(as.numeric(dfs$order))
   # Rsulted subgraph
   g2 <- induced_subgraph(g, dfs_eges)
   # Total weight subgraph g2
   T_W <- sum(E(g2)$weight)
     if (T_W > threshold) {
      print(T_W) 
      return(T_W)
      break
     }
  }
}

#search by vertice
result <- lapply(1:length(V(g)),eval)

Answer 2

此迭代函数查找从任何无向 graph 的顶点 vertex 生成的子图，其中包含低于 limit 中指定值的最大可能权重和。

寻找这样一个图的一个挑战是评估任何可能子图的权重和的计算量。考虑这个例子，其中一次迭代找到了权重和为 1 的子图 A-B。

到任何新顶点的最短路径是 A-C（权重为 3），A-B-D 的子图的权重和为 6，而 A-B-C 的权重和为 12，因为包含子图中的边 B-C。

下面的函数向前看并通过选择逐渐扩大子图来评估迭代步骤，方法是包括下一个会导致最低子图权重和的顶点，而不是具有最短直接路径的顶点.

在优化方面，这还有待改进，但我认为 id 可以满足您在第一个问题中的要求。

find_maxweight_subgraph_from <- function(graph, vertex, limit=0, sub_graph=c(vertex), current_ws=0){
  # Keep a shortlist of possible edges to go next
  shortlist = data.frame(k=integer(0),ws=numeric(0))
  limit <- min(limit, sum(E(graph)$weight))

  while(current_ws < limit){
    # To find the next possible vertexes to include, a listing of 
    # potential candidates is computed to be able to choose the most
    # efficient one.
    # Each iteration chooses amongst vertecies that are connected to the sub-graph:
    adjacents <- as.vector(adjacent_vertices(graph, vertex, mode="all")[[1]])

    # A shortlist of possible enlargements of the sub-graph is kept to be able
    # to compare each potential enlargement of the sub-graph and always choose
    # the one which results in the smallest increase of sub-graph weight-sum.
    #
    # The shortlist is enlarged by vertecies that are:
    #  1) adjacent to the latest added vertex
    #  2) not alread IN the sub-graph
    new_k <- adjacents[!adjacents %in% sub_graph]
    shortlist <- rbind(shortlist[!is.na(shortlist$k),],
                       data.frame(k = new_k,
                                  ws = rep(Inf, length(new_k)) )
    )

    # The addition to the weight-sum is NOT calculated by the weight on individual
    # edges leading to vertecies on the shortlist BUT on the ACTUAL weight-sum of
    # a sub-graph that would be the result of adding a vertex `k` to the sub-graph.
    shortlist$ws <- sapply(shortlist$k, function(x) sum( E(induced_subgraph(graph, c(sub_graph,x)))$weight ) )

    # We choose the vertex with the lowest impact on weight-sum:
    shortlist <- shortlist[order(shortlist$ws),]

    vertex <- shortlist$k[1]
    current_ws <- shortlist$ws[1]
    shortlist <- shortlist[2:nrow(shortlist),]

    # Each iteration adds a new vertex to the sub-graph
    if(current_ws <= limit){
      sub_graph <- c(sub_graph, vertex)
    }
  }

  (induced_subgraph(graph, sub_graph))
}

# Test function using a random graph
g <- erdos.renyi.game(16, 30, type="gnm", directed=F)
E(g)$weight <- sample(1:1000/100, length(E(g)))
sum(E(g)$weight)
plot(g, edge.width = E(g)$weight, vertex.size=2)

sg <- find_maxweight_subgraph_from(g, vertex=12, limit=60)
sum(E(sg)$weight)
plot(sg, edge.width = E(sg)$weight, vertex.size=2)

# Test function using your example code:
g <- make_tree(10, children = 2, mode = c("undirected"))
s <- seq(1:10)
g <- set_edge_attr(g, "weight", value= s)
plot(g, edge.width = E(g)$weight)

sg <- find_maxweight_subgraph_from(g, 2, 47)
sum(E(sg)$weight)
plot(sg, edge.width = E(g)$weight)

igraph 是否具有生成受权重限制的子图的函数？ dfs，random_walk

Does igraph has a function that generates sub-graphs limited by weights? dfs, random_walk

r

subgraph

igraph

weighted