R igraph найти все максимальные клики без перекрытия

Я пытаюсь найти все максимальные клики в графе без перекрытия. функция max_cliques() возвращает все возможные максимальные клики в графе, но я хочу, чтобы каждая вершина входила в только одну клику — в самую большую клику, частью которой она может быть.

например, если выходом max_cliques() являются следующие клики:

{A,B,C}, {A,B,D}, {A,B,J,K}, {E,F,G,H}, {E,F,G,I}

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

{A,B,J,K}, {E,F,G,H}

A и B входят в 3 клики, поэтому я хочу выбрать клики так, чтобы конечный набор включал максимально возможное количество вершин. если есть две возможные клики одинаковой длины, выберите случайную. (Я не возражаю, чтобы не включать все вершины)

Я был бы очень признателен за идею решить эту проблему, даже не вдаваясь в подробности клик - вопрос в основном заключается в том, как удалить самые короткие «списки», содержащие перекрывающиеся элементы.

заранее спасибо


r list overlap igraph clique
person Hodaya Beer    schedule 26.02.2018    source источник
comment
Учитывая ваши критерии и {A,B,C}, {A,D,C}, {B,E}, одним решением будет {A,B,C}, а другим {A,D,C}, {B ,Е}. Тогда что бы вы хотели получить на выходе? Любое решение?   -  person Julius Vainora    schedule 27.02.2018
comment
Я хотел бы {A,D,C} и {B,E}, потому что таким образом в окончательный набор включается больше вершин. хороший комментарий   -  person Hodaya Beer    schedule 27.02.2018
comment
Тогда проблема становится немного сложнее. И если это {A,B,C}, {D,E,F}, то если есть две возможные клики одинаковой длины, выберите случайную, которая предполагает, что {A,B ,C} и {D,E,F} по отдельности являются одинаково хорошими решениями, даже если они не пересекаются. Так ли это?   -  person Julius Vainora    schedule 27.02.2018
comment
если это так, то я хочу их обоих, потому что они не пересекаются.   -  person Hodaya Beer    schedule 27.02.2018

Ответы (1)


arrow_upward
1
arrow_downward

Очевидно, это довольно сложная проблема для решения, поскольку вы спрашиваете о Покрытие и Независимый набор. Это NP-complete. Это означает, что по мере роста вашего графика время вычислений будет увеличиваться в геометрической прогрессии.

Я думаю, это то, к чему вы стремитесь. Мой подход заключается в следующем:

  1. Найдите клики.
  2. Преобразовать в матрицу инцидентности (клики по узлам).
  3. Умножьте матрицу инцидентности на ее транспонирование (%*%), чтобы создать матрицу смежности.
  4. создать граф клик из матрицы смежности (клики связаны с другими кликами, если они имеют общий узел)
  5. Найдите все независимые наборы вершин (это узкое место)
  6. Получить исходные узлы для независимых наборов клик
  7. Найдите набор с большинством узлов.

Код

library(igraph)  
set.seed(8675309)  
g <- graph_from_edgelist(matrix(sample(LETTERS[1:10], 50, replace=T), ncol = 2), directed = FALSE)  
plot(g, edge.arrow.size=0.5)

cliques <- max_cliques(g)

cliqueBP <- matrix(c(rep(paste0("cl", seq_along(cliques)), sapply(cliques, length)), names(unlist(cliques))), ncol=2, )
bp <- graph_from_edgelist(cliqueBP, directed = F)
V(bp)$type <- grepl("cl", V(bp)$name)
# plot(bp, layout=layout_as_bipartite)

bp.ind <- t(as_incidence_matrix(bp))
bp.adj <- bp.ind %*% t(bp.ind)

bp.adj.g <- graph_from_adjacency_matrix(bp.adj, mode = "undirected")
# plot(simplify(bp.adj.g))
bp.adj.mis <- independent.vertex.sets(bp.adj.g)

sets <- lapply(bp.adj.mis, function(x) cliqueBP[cliqueBP[,1] %in% as_ids(x), 2])
sets[which(sapply(sets, length) == max(sapply(sets, length)))]

# [[1]]
# [1] "G" "J" "E" "I" "B" "H" "F" "D"
# 
# [[2]]
# [1] "G" "J" "E" "I" "F" "C" "B" "H"
# 
# [[3]]
# [1] "G" "J" "E" "I" "F" "C" "A" "H"
# 
# [[4]]
# [1] "G" "B" "E" "I" "F" "C" "A" "H"
# 
# [[5]]
# [1] "G" "B" "E" "I" "F" "C" "H" "J"
person emilliman5    schedule 28.02.2018