Detecção de comunidades em redes por algori tmos ensemble

Detecção de comunidades em redes por algori tmos ensemble

Author Mathias, Stefano Bacciuylis Bluyus Rodrigues Pansardis 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 elements in people’s everyday life can be represented by a graph or network. Such a system can possess thousands of elements, many of which can be related to one another. Finding communities or clusters within these systems to evaluate groups of related vertices, as opposed to the entire network, or each individual vertex, appears as a viable alternative for the analysis of these graphs. Due to its applications in various scientific fields, such as Biology, Medicine and Sociology, among others, clustering nodes becomes a viable alternative for these graphs, which may contain a large amount of nodes and edges. For data analysis, and more specifically, data clustering, a common strategy is consensus clustering, which combines two or more computational models to improve the quality of solutions, as compared to those found by only one model. Despite the good results obtained for data clustering, this strategy has not been frequently applied to finding communities in networks. For this reason, this dissertation proposes a genetic algorithm that applies consensus clustering techniques to identify communities in networks. Considering as the objective function a measure here called ”adjusted modularity”, our algorithm performed better than classic algorithms within the scientific literature in experiments performed with artificial and real-world graphs.

Diversos elementos presentes no cotidiano das pessoas podem ser representados por meio de um grafo ou rede. Um sistema que assume tal representação pode possuir milhares de elementos, alguns deles relacionados entre si. Encontrar comunidades ou clusters nesses sistemas para avaliação dos grupos de vértices relacionados ao invés da investigação do grafo como um todo ou dos vértices individualmente surge como uma alternativa viável para a análise desses grafos. Devido à existência de aplicações em diversas áreas do conhecimento, tais como biologia, medicina, sociologia, entre outras, agrupar vértices torna-se como uma alternativa atraente para esses grafos que podem possuir uma grande quantidade de vértices e arestas. Para a análise de dados, mais especificamente, em agrupamento de dados, uma estratégia bastante utilizada é a de agrupamento consensual, que consiste em combinar dois ou mais modelos computacionais para obter maior robustez nas soluções em comparação às encontradas por um único modelo. Apesar dos bons resultados encontrados para agrupamento de dados, essa estratégia não tem sido muito empregada para encontrar comunidades em redes. Por esse motivo, nesta Dissertação propomos um algoritmo genético que aplica técnicas de agrupamento consensual para encontrar comunidades em redes. Considerando como função objetivo uma medida chamada aqui de modularidade ajustada, nosso algoritmo superou o resultado de algoritmos clássicos da literatura em experimentos realizados usando grafos artificiais e reais.
Keywords graph clustering
modularity
directed graphs
cluster ensemble
hungarian method
community detection in networks
genetic algorithms
agrupamento em grafos
modularidade
grafos direcionados
cluster ensemble
método hungáro
detecção de comunidades em redes
algoritmos genéticos
Language Portuguese
Date 2014-01-12
Published in MATHIAS, Stefano Bacciuylis Bluyus Rodrigues Pansardis. Detecção de comunidades em redes por algori tmos ensemble. 2014. 93 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 93 p.
Origin https://sucupira.capes.gov.br/sucupira/public/consultas/coleta/trabalhoConclusao/viewTrabalhoConclusao.jsf?popup=true&id_trabalho=1352671
Access rights Closed access
Type Dissertation
URI http://repositorio.unifesp.br/handle/11600/46903

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