Metaheurísticas para o problema de agrupamento de dados em grafo / Metaheuristics for the graph clustering problem

AUTOR(ES)

Mariá Cristina Vasconcelos Nascimento

DATA DE PUBLICAÇÃO

2010

RESUMO

Graph clustering aims at identifying highly connected groups or clusters of nodes of a graph. This problem can assume others nomenclatures, such as: graph partitioning problem and community detection problem. There are many mathematical formulations to model this problem, each one with advantages and disadvantages. Most of these formulations have the disadvantage of requiring the definition of the number of clusters in the final partition. Nevertheless, this type of information is not found in graphs for clustering, i.e., whose data are unlabeled. This is one of the reasons for the popularization in the last decades of the measure known as modularity, which is being maximized to find graph partitions. This formulation does not require the definition of the number of clusters of the partitions to be produced, and produces high quality partitions. In this Thesis, Greedy Randomized Search Procedures metaheuristics for two existing graph clustering mathematical formulations are proposed: one for the maximization of the partition modularity and the other for the maximization of the intra-cluster similarity. The results obtained by these proposed metaheuristics outperformed the results from other heuristics found in the literature. However, their computational cost was high, mainly for the metaheuristic for the maximization of modularity model. Along the years, researches revealed that the formulation that maximizes the modularity of the partitions has some limitations. In order to promote a good alternative for the maximization of the partition modularity model, this Thesis proposed new mathematical formulations for graph clustering for weighted and unweighted graphs, aiming at finding partitions with high connectivity clusters. Furthermore, the proposed formulations are able to provide partitions without a previous definition of the true number of clusters. Computational tests with hundreds of weighted graphs confirmed the efficiency of the proposed models. Comparing the partitions from all studied formulations in this Thesis, it was possible to observe that the proposed formulations presented better results, even better than the maximization of partition modularity. These results are characterized by satisfactory partitions with high correlation with the true classification for the simulated and real data (mostly biological)

ASSUNTO(S)

clustering coefficient community detection graph clustering grasp grasp clustering coefficient modularidade agrupamento de dados em grafos detecção de comunidades modularity

Documentos Relacionados

• Análise de técnicas baseadas em metaheurísticas e dominação de grafos para clustering em redes ad hoc
• Metaheurísticas para o problema de Flowshop flexível com penalidades de adiantamento e atraso
• Heuristica e metaheuristicas para o problema de agrupamento capacitado
• Metaheurísticas evolutivas para o problema de roteamento de unidades móveis de pistoneio
• Algoritmos quânticos para o problema do isomorfismo de grafos