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

Question

I have a weighted graph in igraph R environment.

And need to obtain sub-graphs recursively, starting from any random node. The sum of weights in each sub-graph has to be less them a number.

The Deep First Search algorithm seems to deal with this problem. Also the random walk function.

Does anybody know which igraph function could tackle this?

Answer 1

This iterative function finds the sub-graph grown from vertex vertex of any undirected graph which contains the biggest possible weight-sum below a value spevified in limit.

A challange in finding such a graph is the computational load of evaluating the weight sum of any possible sub-graphs. Consider this example, where one iteration has found a sub-graph A-B with a weight sum of 1.

The shortest path to any new vertex is A-C (with a weight of 3), a sub-graph of A-B-D has a weight-sum of 6, while A-B-C would have a weight-sum of 12 because of the inclusion of the edge B-C in the sub-graph.

The function below looks ahead and evaluates iterative steps by choosing to gradually enlarge the sub-graph by including the next vertex that would result in the lowest sub-graph weight-sum rather than that vertex which has the shortest direct paths.

In terms of optimisation, this leaves something to be desired, but I think id does what you requested in your first question.

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)