Algoritmos paralelos para determinar agrupamentos em grafos com única ou múltiplas camadas

Algoritmos paralelos para determinar agrupamentos em grafos com única ou múltiplas camadas

Author Resende, Hugo Autor UNIFESP Google Scholar
Advisor Nascimento, Maria Cristina Vasconcelos Nascimento Autor UNIFESP Google Scholar
Institution Universidade Federal de São Paulo (UNIFESP)
Graduate program Ciência da Computação
Abstract Many real-world applications are naturally represented by the combinatorial structures known as graphs. The identification of highly related vertices in a graphs suggests the existence of clusters that enable a better data evaluation. Therefore, the graph clustering problem has been extensively studied by several types of researchers. However, for large scale graphs, to identify clusters still remains as a challenge. There are a few algorithms based on the optimization of some quality measure that efficiently perform this task. Bearing this in mind, in this Dissertation, we propose efficient parallel algorithms to solve the graph clustering problem, also known as the detection community problem in netwoks. Relying on an adjusted modularity, these algorithms have proved to be quite efficient, outperforming results from the literature in many case studies. Additionally, this Dissertation presents a study employing multiplex, since one of the proposed algorithms is capable of tackling these graphs.

Várias aplicações são naturalmente representáveis pela estrutura matemática combinatorial grafos. A identificação de vértices altamente relacionados sugere a existência de clusters de vértices que proporcionam uma melhor avaliação dos dados. Por essa razão, o problema de agrupamento em grafos tem sido bastante estudado por pesquisadores de diversas áreas. Entretanto, para grafos de larga escala, a identificação de agrupamentos é ainda considerada um grande desafio. Poucos são os algoritmos baseados na otimização de alguma medida de qualidade que realiza tal tarefa de forma eficiente. Tendo isso em mente que, nesta Dissertação, são propostos algoritmos paralelos e eficientes para a solução do problema de agrupamento em grafos, também conhecido por problema de detecção de comunidades em redes. Baseados em uma medida chamada aqui de modularidade ajustada, esses algoritmos se mostraram bastante eficientes, superando resultados da literatura em diversos estudos de casos. Além disso, esta Dissertação apresenta um estudo de grafos com múltiplas camadas, sendo um dos algoritmos propostos passível de tratar tais grafos.
Keywords graph clustering
modularity
multilayer graphs
parallel programming
louvain method
community detection in networks
agrupamento em grafos
modularidade
grafos multicamadas
programação paralela
método de louvain
detecção de comunidades em redes
Language Portuguese
Date 2014-04-16
Published in RESENDE, Hugo. Algoritmos paralelos para determinar agrupamentos em grafos com única ou múltiplas camadas. 2014. 65 f. Dissertação (Mestrado) - Instituto de Ciência e Tecnologia, Universidade Federal de São Paulo (UNIFESP), São José dos Campos, 2014.
Research area Ciência da computação
Knowledge area Ciências exatas e da terra
Publisher Universidade Federal de São Paulo (UNIFESP)
Extent 65 p.
Origin https://sucupira.capes.gov.br/sucupira/public/consultas/coleta/trabalhoConclusao/viewTrabalhoConclusao.jsf?popup=true&id_trabalho=1324798
Access rights Closed access
Type Dissertation
URI http://repositorio.unifesp.br/handle/11600/46904

Show full item record




File

File Size Format View

There are no files associated with this item.

This item appears in the following Collection(s)

Search


Browse

Statistics

My Account