Estratégia multinível para detecção de comunidades em redes k-partidas (2025)
- Authors:
- Autor USP: MENDES, RENATA SARMET SMIDERLE - ICMC
- Unidade: ICMC
- Sigla do Departamento: SCC
- DOI: 10.11606/D.55.2025.tde-25092025-170612
- Subjects: REDES COMPLEXAS; RECONHECIMENTO DE PADRÕES; TEORIA DOS GRAFOS; APRENDIZADO COMPUTACIONAL
- Keywords: Aprendizado baseado em grafos; Community detection; Complex networks; Contração de rede; Detecção de comunidades; Grafos k-partidos; Graph-based learning; k-partite graphs; Método multinível; Multilevel method; Network coarsening
- Language: Português
- Abstract: Algoritmos baseados em grafos têm despertado interesses consideráveis nos últimos anos, facilitando o reconhecimento de padrões e o aprendizado por meio do processo de propagação de informações através do grafo. Porém, com um grande volume de dados, torna-se computacionalmente inviável executar certos algoritmos. A estratégia multinível visa reduzir recursivamente o grafo, realizando sucessivas compactações da rede inicial com base em contrações de arestas e fusões de vértices, a fim de torná-lo tão pequeno quanto desejado, permitindo, assim, a utilização de algoritmos custosos. A estratégia multinível pode ser dividida em três fases: fase de coarsening, composta por combinação e contração, a fase de encontrar a solução, composta pela aplicação do algoritmo desejado na rede mais compacta, e a fase de uncoarsening, composta por projeção e refinamento. Neste trabalho é realizado uma generalização do algoritmo de coarsening para redes bipartidas com base na propagação de rótulos com restrição de peso, tornando possível seu uso em redes k-partidas. Além disso, o coarsening é utilizado diretamente como um algoritmo de detecção de comunidades, no qual cada supervértice obtido no grafo mais reduzido (último nível de coarsening) representa uma comunidade.
- Imprenta:
- Publisher place: São Carlos
- Date published: 2025
- Data da defesa: 03.07.2025
- Este periódico é de acesso aberto
- Este artigo é de acesso aberto
- URL de acesso aberto
- Cor do Acesso Aberto: gold
- Licença: cc-by-nc-sa
-
ABNT
MENDES, Renata Sarmet Smiderle. Estratégia multinível para detecção de comunidades em redes k-partidas. 2025. Dissertação (Mestrado) – Universidade de São Paulo, São Carlos, 2025. Disponível em: https://www.teses.usp.br/teses/disponiveis/55/55134/tde-25092025-170612/. Acesso em: 01 jan. 2026. -
APA
Mendes, R. S. S. (2025). Estratégia multinível para detecção de comunidades em redes k-partidas (Dissertação (Mestrado). Universidade de São Paulo, São Carlos. Recuperado de https://www.teses.usp.br/teses/disponiveis/55/55134/tde-25092025-170612/ -
NLM
Mendes RSS. Estratégia multinível para detecção de comunidades em redes k-partidas [Internet]. 2025 ;[citado 2026 jan. 01 ] Available from: https://www.teses.usp.br/teses/disponiveis/55/55134/tde-25092025-170612/ -
Vancouver
Mendes RSS. Estratégia multinível para detecção de comunidades em redes k-partidas [Internet]. 2025 ;[citado 2026 jan. 01 ] Available from: https://www.teses.usp.br/teses/disponiveis/55/55134/tde-25092025-170612/
Informações sobre o DOI: 10.11606/D.55.2025.tde-25092025-170612 (Fonte: oaDOI API)
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
