Эффективный способ получить сообщества графов
У меня есть данные следующего типа, и я знаю, что будет много несвязанных сообществ (хорошее разделение). Я хочу эффективно (быстро и желательно с минимальными / отсутствующими зависимостями) разделять данные на их сообщества. Я знаю, что могу использовать граф для выполнения этой задачи, но надеялся, что существует быстрый базовый R-способ извлечения этих сообществ. Я показываю, как я разделяю сообщества, используя график ниже.
Есть ли быстрый базовый R-способ извлечения сообществ? Совместное использование небазовых подходов R тоже хорошо, так что этот вопрос будет более полезен для будущих искателей.
dat <- data.frame(
x = c('A', 'A', 'B', 'C', 'D', 'F', 'E', 'W', 'X', 'R', 'W'),
y = c('A', 'B', 'C', 'C', 'F', 'F', 'E', 'Y', 'P', 'P', 'P')
)
mat <- xtabs(~ x + y, data = dat)
library(igraph)
g <- graph.data.frame(dat)
plot(g)
clust <- cluster_walktrap(g)
data.frame(
val = clust$names,
group = clust$membership
)
Желаемый результат
## val group
## 1 A 2
## 2 B 2
## 3 C 2
## 4 D 3
## 5 F 3
## 6 E 4
## 7 W 1
## 8 X 1
## 9 R 1
## 10 Y 1
## 11 P 1
@Roland Я хотел избежать зависимости, но если это лучшее решение, то меня это устраивает. Это похоже на проблему кластеризации / взаимодействия, и я подумал, что, вероятно, есть решение матричной алгебры, которое я упускаю. Быстро было бы относительно igraph. Если он близок / похож по скорости или быстрее. Но быстро в моем понимании не является точным, тем более относительным. Конечно, я мог бы использовать цикл for / while и вручную искать индикаторы в строках и столбцах, но это было бы медленно.
Если бы существовал другой внешний пакет, который был бы быстрее, чем igraph, я был бы открыт для этого, и если бы мне все равно пришлось иметь зависимость, мне бы потребовался самый быстрый подход.
Это было бы не по теме. Я не ожидаю, что будет что-то быстрее, чем igraph. Но это могло быть возможно ...
@TylerRinker Я согласен с Роландом в том, что вряд ли будет что-то быстрее, чем igraph, и, вероятно, не что-то такое же быстрое, как igraph. Насколько сильно снизится производительность, чтобы избежать зависимости?
@TylerRinker, как сказано в ?clusters, для слабосвязанных компонентов использует поиск в ширину. Тогда, как говорится, например, в cs.stackexchange.com/questions/56504/…, нет лучшего асимптотического алгоритма (возможно, для отдельного графа). Также обратите внимание: «любой правильный алгоритм должен будет проверять каждую вершину и каждое ребро хотя бы один раз». Итак, все сводится к реализациям, и строки 89--162 в github.com/cran/igraph/blob/master/src/components.c выглядят довольно лаконично.
... Тем не менее, я также не думаю, что можно придумать что-то заметно лучше.
Вы не можете работать с графами в базе R так быстро, как с igraph. Почему вы против igraph? Из-за зависимостей? Определите, пожалуйста, «быстро».