| Texto completo | |
| Autor(es): |
Tautenhain, Camila P. S.
[1]
;
Nascimento, V, Maria C.
Número total de Autores: 2
|
| Afiliação do(s) autor(es): | [1] V, Univ Fed Sao Paulo, Inst Ciencia & Tecnol, Sao Jose Dos Campos - Brazil
Número total de Afiliações: 1
|
| Tipo de documento: | Artigo Científico |
| Fonte: | EXPERT SYSTEMS WITH APPLICATIONS; v. 141, MAR 1 2020. |
| Citações Web of Science: | 0 |
| Resumo | |
Graph clustering is a challenging pattern recognition problem whose goal is to identify vertex partitions with high intra-group connectivity. This paper investigates a bi-objective problem that maximizes the number of intra-cluster edges of a graph and minimizes the expected number of inter-cluster edges in a random graph with the same degree sequence as the original one. The difference between the two investigated objectives is the definition of the well-known measure of graph clustering quality: the modularity. We introduce a spectral decomposition hybridized with an evolutionary heuristic, called MOSpecG, to approach this bi-objective problem and an ensemble strategy to consolidate the solutions found by MOSpecG into a final robust partition. The results of computational experiments with real and artificial LFR networks demonstrated a significant improvement in the results and performance of the introduced method in regard to another bi-objective algorithm found in the literature. The crossover operator based on the geometric interpretation of the modularity maximization problem to match the communities of a pair of individuals was of utmost importance for the good performance of MOSpecG. Hybridizing spectral graph theory and intelligent systems allowed us to define significantly high-quality community structures. (C) 2019 Elsevier Ltd. All rights reserved. (AU) | |
| Processo FAPESP: | 16/22688-2 - Teoria Espectral para a Análise de Agrupamento em Grafos |
| Beneficiário: | Camila Pereira dos Santos Tautenhain |
| Modalidade de apoio: | Bolsas no Brasil - Doutorado |
| Processo FAPESP: | 15/21660-4 - Hibridização de métodos heurísticos e exatos para abordar problemas de otimização combinatória |
| Beneficiário: | Mariá Cristina Vasconcelos Nascimento Rosset |
| Modalidade de apoio: | Auxílio à Pesquisa - Regular |