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

dc.contributor.advisorNascimento, Maria Cristina Vasconcelos Nascimento [UNIFESP]pt
dc.contributor.authorMathias, Stefano Bacciuylis Bluyus Rodrigues Pansardis [UNIFESP]
dc.contributor.institutionUniversidade Federal de São Paulo (UNIFESP)pt
dc.date.accessioned2018-07-27T15:51:02Z
dc.date.available2018-07-27T15:51:02Z
dc.date.issued2014-01-12
dc.description.abstractMany 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.en
dc.description.abstractDiversos 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.pt
dc.description.sourceDados abertos - Sucupira - Teses e dissertações (2013 a 2016)
dc.format.extent93 p.
dc.identifierhttps://sucupira.capes.gov.br/sucupira/public/consultas/coleta/trabalhoConclusao/viewTrabalhoConclusao.jsf?popup=true&id_trabalho=1352671pt
dc.identifier.citationMATHIAS, 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.
dc.identifier.file2014-0069.pdf
dc.identifier.urihttp://repositorio.unifesp.br/handle/11600/46903
dc.language.isopor
dc.publisherUniversidade Federal de São Paulo (UNIFESP)
dc.rightsAcesso restrito
dc.subjectgraph clusteringen
dc.subjectmodularityen
dc.subjectdirected graphsen
dc.subjectcluster ensembleen
dc.subjecthungarian methoden
dc.subjectcommunity detection in networksen
dc.subjectgenetic algorithmsen
dc.subjectagrupamento em grafospt
dc.subjectmodularidadept
dc.subjectgrafos direcionadospt
dc.subjectcluster ensemblept
dc.subjectmétodo hungáropt
dc.subjectdetecção de comunidades em redespt
dc.subjectalgoritmos genéticospt
dc.titleDetecção de comunidades em redes por algori tmos ensemblept
dc.typeDissertação de mestrado
unifesp.campusSão José dos Campos, Instituto de Ciência e Tecnologia (ICT)pt
unifesp.graduateProgramCiência da Computaçãopt
unifesp.knowledgeAreaCiências exatas e da terrapt
unifesp.researchAreaCiência da computaçãopt
Arquivos