igraph двудольная сетевая проекция игнорирует направление - PullRequest
Новая
       42

igraph двудольная сетевая проекция игнорирует направление

0 голосов
/ 27 ноября 2018

Пример: 

require(igraph)
require(tidygraph)
require(ggraph)
require(data.table)

nodes <- data.table(id = 1:6, 
                    label = c("a1", "b1", "a2", "a3", "b2", "a4"), 
                    type = c("A", "B", "A", "A", "B", "A"))

edges <- data.table(from = c(1, 2, 2, 3, 5),
                    to = c(2, 3, 4, 5, 6))

network <- graph_from_data_frame(d = edges, vertices = nodes, directed = TRUE)

ggraph(network) + 
  geom_edge_link(arrow = arrow(length = unit(4, 'mm')), 
                 start_cap = circle(3, 'mm'), 
                 end_cap = circle(3, 'mm')) + 
  geom_node_point(aes(color = type), size = 7) +
  geom_node_text(aes(label = label)) +
  theme_graph()

Вот что мы получаем:

enter image description here

Затем мы создаем проекции: 

V(network)$type <- bipartite_mapping(network)$type
network_projections <- bipartite_projection(network)

ggraph(network_projections$proj1) + 
  geom_edge_link(arrow = arrow(length = unit(4, 'mm')), 
                 start_cap = circle(3, 'mm'), 
                 end_cap = circle(3, 'mm')) + 
  geom_node_point(size = 7, color = 2, alpha = .6) +
  geom_node_text(aes(label = label)) +
  theme_graph()

И вот что мы получаем:

enter image description here

Проекция показывает ссылку a2 -> a3, которая должна не будь там.Что явно означает, что направленность не была принята во внимание.

Насколько я выяснил, базовая матрица инцидентности, вычисленная библиотекой igraph, рассчитывается таким образом, что не учитывает направленность.Есть ли какая-то функция, которую я пропустил, или другие библиотеки R, которые позволяют направленно проецировать двудольные сети?

1 Ответ

0 голосов
/ 27 ноября 2018

Это ни в коем случае не оптимальное решение, больше похоже на обходной путь:

(продолжить с кода в исходном вопросе) 

# get a list of adjacent vertices from perspective of projections to validate directional connection
adj_vert <- adjacent_vertices(network_projections$proj1, v = nodes[type == "A", .I])

# container
projection_edges <- data.table(from = character(),
                               to = character())

for(i in names(adj_vert)){

  # find simplest path, from iterated vertice to vector of shortlisted names
  orig_paths <- all_simple_paths(network, from = as.numeric(i), to = as.numeric(names(adj_vert[[i]])), mode = "out")

  if(length(orig_paths) > 0){
    for(j in 1:length(orig_paths)){

      # for each path, take first and last element to skip "B" nodes in between
      projection_edges <- rbind(projection_edges,
                                data.table(from = names(orig_paths[[j]])[1],
                                           to = rev(names(orig_paths[[j]]))[1]))
    }
  }
}

# corrected projection

network_projection_corrected <- graph_from_data_frame(d = projection_edges, vertices = nodes[type == "A"], directed = TRUE)

ggraph(network_projection_corrected) + 
  geom_edge_link(arrow = arrow(length = unit(4, 'mm')), 
                 start_cap = circle(3, 'mm'), 
                 end_cap = circle(3, 'mm')) + 
  geom_node_point(aes(color = type), size = 7) +
  geom_node_text(aes(label = label)) +
  theme_graph()

Мы получаем это:

enter image description here

Это не выглядит ОЧЕНЬ ужасно, даже если это вложенный цикл.Потому что для каждого цикла все смежные вершины типа «А» известны, и мы просто эффективно проверяем направленное соединение.Тем не менее, я думаю, что это должна быть встроенная функциональность.

Кроме того, я не знаю о возможных ошибках, которые мой предложенный подход принесет для «реальных» сетей.Так что это ни в коем случае не твердо.

...