Получить пересечения между наборами всех комбинаций наблюдений

У меня есть набор данных, который выглядит так

   target.id source.id connected
          1      1     0
          2      1     0
          3      1     0
          4      1     0
          5      1     0
          6      1     0
          1      2     1
          2      2     0
          3      2     1

В основном у меня есть исходное местоположение, целевое местоположение и связаны ли они. Здесь связи являются направленными, например, точка 1 может быть соединена с точкой 8, а точка 8 не связана с точкой 1 (подумайте о рейсах авиакомпаний, где Atlantis может отправлять рейсы на Марс, а Марс не может отправлять рейсы на Atlantis, что означало бы Атлантида соединяется с Марсом, а Марс не соединяется с Атлантидой).

Мне нужно определить наборы «полностью» связанных местоположений, где все наблюдения являются источниками и целями друг друга. Мне нужно сделать это попарно, 3 на 3, и до тех пор, пока это возможно, учитывая, что у меня есть 75 мест. Пример вывода: для 3 на 3 местоположения 3, 5 и 8 являются как источниками, так и целями друг друга.

То, как я пытался справиться с этим, заключалось в том, чтобы получить все перестановки 1:length(unique(target.id)) 2 на 2, 3 на 3, до 8 на 8 (8 на 8 - это максимальные наборы, на которые я бы посмотрел), а затем intersect все из них.

Однако, очевидно, это слишком медленно. Любые лучшие подходы?


r intersection
person Felipe Alvarenga    schedule 12.05.2017    source источник
comment
Направление имеет значение, значит, цель не может быть ниже источника? Является ли судьба такой же, как цель? Измените вопрос, чтобы включить желаемый результат с последовательной номенклатурой и полностью объяснить ограничения.   -  person manotheshark    schedule 12.05.2017

Ответы (1)


arrow_upward
3
arrow_downward

Похоже, вам нужны все клики размером от 2 до 8 из ориентированного графа, где узлы — это ваши идентификаторы, а ребра существуют, когда источник -> пункт назначения помечен как подключенный в вашем наборе данных. Первым шагом будет фильтрация только связанных ребер, что даст что-то вроде следующего примера данных:

(filtered <- data.frame(source.id = c(1, 1, 2, 2, 3, 3, 3, 4, 4), target.id = c(2, 3, 1, 3, 1, 2, 4, 3, 5), connected = 1))
#   source.id target.id connected
# 1         1         2         1
# 2         1         3         1
# 3         2         1         1
# 4         2         3         1
# 5         3         1         1
# 6         3         2         1
# 7         3         4         1
# 8         4         3         1
# 9         4         5         1

Затем вы можете ограничить свои данные парами идентификаторов, которые связаны в обоих направлениях:

(bidir <- filtered[duplicated(paste(pmin(filtered$source.id, filtered$target.id),
                                    pmax(filtered$source.id, filtered$target.id))),])
#   source.id target.id connected
# 3         2         1         1
# 5         3         1         1
# 6         3         2         1
# 8         4         3         1

В этой выборке клики размера 2 — это (1, 2), (1, 3), (2, 3) и (3, 4), а клика размера 3 — (1, 2, 3). . Пакет igraph вычисляет их за «почти оптимальное время»:

library(igraph)
g <- graph.data.frame(bidir, directed=FALSE)
cliques(g, min=2, max=8)
# [[1]]
# + 2/4 vertices, named:
# [1] 2 3
# 
# [[2]]
# + 2/4 vertices, named:
# [1] 2 1
# 
# [[3]]
# + 2/4 vertices, named:
# [1] 3 4
# 
# [[4]]
# + 2/4 vertices, named:
# [1] 3 1
# 
# [[5]]
# + 3/4 vertices, named:
# [1] 2 3 1
person josliber♦    schedule 12.05.2017