Есть ли у igraph функция, которая генерирует подграфы, ограниченные весами? dfs, random_walk - PullRequest
Новая
       56

Есть ли у igraph функция, которая генерирует подграфы, ограниченные весами? dfs, random_walk

1 голос
/ 10 марта 2020

У меня есть взвешенный граф в среде igraph R.

И мне нужно рекурсивно получать подграфы, начиная с любого случайного узла. Сумма весов в каждом подграфе должна быть меньше их числа.

Кажется, что алгоритм Deep First Search решает эту проблему. Также функция случайного блуждания.

Кто-нибудь знает, какая функция igraph могла бы справиться с этим?

Ответы [ 2 ]

0 голосов
/ 11 марта 2020

Эта итерационная функция находит подграф, выросший из вершины vertex любой неориентированной graph, которая содержит максимально возможную весовую сумму ниже значения, указанного в limit.

Проблема в поиске такой граф является вычислительной нагрузкой оценки весовой суммы любых возможных подграфов. Рассмотрим этот пример, где одна итерация нашла подграф AB с весовой суммой 1.

enter image description here

Кратчайший путь к любой новой вершине равен A- C (с весом 3), подграф ABD имеет весовую сумму 6, в то время как AB- 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)
0 голосов
/ 11 марта 2020

Это сделано ниже, однако, оно не кажется эффективным. 

#######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)
...