83867

A hybrid heuristic for the overlapping cluster editing problem

Favorite this paper

Problemas de agrupamento são oriundos de várias áreas da ciência. No contexto
de teoria de grafos, pode-se gerar um agrupamento por meio de adições e
remoções de arestas de um grafo de modo que esse grafo seja composto de
subgrafos (clusters) completos disjuntos. Esse problema é conhecido
como o problema de edição de clusters. Entretanto, há casos em que
esses clusters podem se sobrepor. Há poucos trabalhos práticos na
literatura que consideram o problema de edição de clusters com
sobreposição. Com isso, neste trabalho, é proposta uma heurística híbrida para
esse problema. Essa heurística híbrida é composta por duas meta-heurísticas,
para gerar soluções do problema de edição de clusters, e de um modelo
por programação linear inteira mista, também proposto neste
trabalho, que é resolvido utilizando os clusters oriundos das
meta-heurísticas. Com os resultados obtidos nos testes realizados, pode-se
observar que a heurística híbrida pode gerar bons agrupamentos com
sobreposição.