Orientador: Prof. Dr. Fabrício Olivetti de França / Dissertação (mestrado) - Universidade Federal do ABC, Programa de Pós-Graduação em Ciência da Computação, 2017. / Um dos tópicos estudados em Ciência das Redes é o de detecção de comunidades, que são sub-redes com características que se destacam dentro de seu conjunto. Diversos algoritmos de detecção de comunidades foram criados, se diferenciando na natureza da comunidade estimada. Esta dissertação tem como objetivo principal analisar diferentes algoritmos de detecção de comunidades da literatura para criação de um modelo de escolha de algoritmos de detecção de comunidade a partir das características da rede. Para isso, três hipóteses.
Foram testadas: i) os melhores algoritmos de detecção de comunidade se complementam em relação à redes em que obtém seu melhor desempenho; ii) o desempenho de cada algoritmo de detecção de comunidade esta ligada diretamente _a propriedade da rede. iii) uma vez que as propriedades da rede são mensuradas, é possível fazer uma escolha dos
melhores algoritmos de detecção de comunidade para essa rede. Para a primeira hipótese foram testados sete algoritmos do estado da arte e avaliados seus desempenhos individuais sobre redes artifiais, em termos da métrica de Informação Mutua Normalizada (NMI). Veríamos a existência de um conjunto de algoritmos que obtiveram o maior NMI para
determinados tipos de redes e nenhum outro algoritmo obteve esse mesmo valor, concluindo que a escolha adequada do algoritmo de acordo com as características da rede é importante. Para a segunda hipótese foram testados modelos de regressão com o objetivo de verificar a possibilidade de estimar o desempenho de cada algoritmo baseado nas caracteristicas da rede. Verifcamos que a maioria dos modelos foram superiores aos da base de referencia utilizados, principalmente ao remover as redes infectaveis. Para a terceira hipótese foram testados algoritmos de classicação com o objetivo de escolher um ou mais
algoritmos de acordo com a características da rede. Verificamos que o desempenho dos modelos obtidos pelos algoritmos foram superiores aos da base de referencia, com algumas ressalvas. / One of the topics studied in Network Science is the community detection, that are subnetworks with features that stand out as a whole. Many algorithms were developed for
the detection of communities, difering in the nature of the estimated community. This dissertation has as its main objective, the analysis of diferent community detection algorithms
from the literature to create models to help choosing the best algorithms given the features from the network. For this purpose, three hypotheses were tested: i) whether
the best algorithms for detecting communities complement each other in relation to the networks in which they obtain better performance; ii) whether the performance of each
community detection algorithm is directly associated with the network property, and iii) once the network properties are measured, whether it is possible to choose the best
community detection algorithms for this network. For the first hypothesis, seven stateof- the-art algorithms were tested and their individual performances in articial networks
were evaluated in terms of the NMI metric. We verifed the existence of a set of algorithms that obtained the highest NMI for certain types of networks and no other algorithm obtained that same value, concluding that the proper choice of the algorithm according to the network features is important. For the second hypothesis, regression models were tested to verify the possibility of estimate the performance of each algorithm based on the features of the network. We verifed that most of the models were superior to the baseline used, mainly in the removal of infeasible networks. For the third hypothesis, the classifcation algorithms were tested to choose one or more algorithms according to the network features. We veried that the performance of the models obtained by the
algorithms was higher than those of the baseline, with some caveats.
| Identifer | oai:union.ndltd.org:IBICT/oai:BDTD:105677 |
| Date | January 2017 |
| Creators | Oliveira, Eric Tadeu Camacho de |
| Contributors | França. Fabrício Olivetti de, Mena-Chalco, Jesús Pascual, Silva, Leandro Nunes de Castro |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | application/pdf, 125 f. : il. |
| Source | reponame:Repositório Institucional da UFABC, instname:Universidade Federal do ABC, instacron:UFABC |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | http://biblioteca.ufabc.edu.br/index.php?codigo_sophia=105677&midiaext=74092, http://biblioteca.ufabc.edu.br/index.php?codigo_sophia=105677&midiaext=74093, Cover: http://biblioteca.ufabc.edu.brphp/capa.php?obra=105677 |
Page generated in 0.0021 seconds