Чтобы найти количество шаблонов

Question

Для набора данных, как:

21 79 
78 245 
21 186 
65 522 
4 21 
3 4 
4 212 
4 881 
124 303 
28 653 
28 1231 
7 464 
7 52 
17 102 
16 292 
65 837 
28 203 
28 1689 
136 2216 
7 1342 
56 412 

Мне нужно найти количество связанных моделей. Например, 21-79 и 21-186 имеют 21 общий характер. Таким образом, они образуют 1 шаблон. Также 21 присутствует в 4-21. Этот край также способствует тому же шаблону. Теперь 4-881, 4-212, 3-4 имеют 4 в своем крае. Таким образом, они также способствуют тому же шаблону. Таким образом, края 21-79, 21-186, 4-21, 4-881, 4-212, 3-4 формы 1. Аналогичным образом существуют и другие шаблоны. Таким образом, нам нужно сгруппировать все ребра, которые имеют один общий узел для формирования шаблона (или подграфа). Для данного набора данных имеется всего 4 шаблона. Мне нужно написать код (желательно в R), который найдет такое. моделей.

Просьба помочь. Это очень важно для меня.

Answer 1

Поскольку вы описываете данные как подграфы, почему бы не использовать пакет igraph, который очень хорошо осведомлен о графиках. Так вот ваши данные в виде data.frame

dd <- structure(list(V1 = c(21L, 78L, 21L, 65L, 4L, 3L, 4L, 4L, 124L, 
    28L, 28L, 7L, 7L, 17L, 16L, 65L, 28L, 28L, 136L, 7L, 56L), V2 = c(79L, 
    245L, 186L, 522L, 21L, 4L, 212L, 881L, 303L, 653L, 1231L, 464L, 
    52L, 102L, 292L, 837L, 203L, 1689L, 2216L, 1342L, 412L)), .Names = c("V1", 
    "V2"), class = "data.frame", row.names = c(NA, -21L)) 

Мы можем рассматривать каждое значение как имя вершины так, предоставленные вами данные действительно как список края. Таким образом, мы создаем наш граф с

library(igraph) 
gg <- graph.edgelist(cbind(as.character(dd$V1), as.character(dd$V2)), 
    directed=F) 

Это определяет узлы и вершины в результате на следующем графике (plot(gg))

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

clusters(gg)$no 
# [1] 10 

Какая информация содержит 10 кластеров в данных, которые вы предоставили. Но вам нужны только те, у которых больше двух вершин. Что мы можем получить с

sum(clusters(gg)$csize>2) 
# [1] 4 

Что такое 4, как вы ожидали.