Renan Cavalcanti Filgueiras de Souza
Resumo
O objetivo da presente tese é desenvolver uma metodologia de pré-processamento de grafos, de forma que o grafo resultante seja planar. O que se espera como resultado da pesquisa é a facilitação da interpretação de um grafo real do ponto de vista de link analysis, visto que a planarização envolve redução de vértices e/ou arestas do grafo. Com isto espera-se que o problema de detecção de clusters e posicionamento de vértices dentre outros temas de link analysis possam ser obtidos em um grafo estruturalmente menor do que o original, contudo o mais fidedigno possível em medidas de link analysis, encontrando correspondência entre o original e o planar, estabelecendo uma técnica capaz de tirar conclusões sobre o original analisando o grafo reduzido. Os resultados mostram uma boa perspectiva da metodologia proposta para grafos aleatórios gerados com determinados parâmetros. O estudo também é aplicado a grafos complexos. Todos os estudos de caso são detalhados e o processo para reprodução ou geração de novos resultados é apresentado de forma didática.
Abstract
The objective of the present thesis is to develop a pre-processing methodology, in which the resulting graph is planar. The expected result of this is the capability of interpret a real world graph from link analysis in an easy way, once the planarization involves vertex and/or edge reduction from the original graph. As a consequence, it is expected that problems such as clusters detection and vertex positioning amongst other link analysis tasks can be obtained in a structurally smaller graph, but as similar as possible, in link analysis measures, to the original graph, matching between the original and the planar graphs, establishing a technique capable of taking conclusions of the original graph analyzing its planar counterpart. The results show a good perspective of the proposed methodology for random graphs generated by controlled parameters. The study is also applied to complex graphs. All cases are detailed and the reproduction or generation of newly results is presented.
