Show simple item record

dc.contributor.advisorComba, Joao Luiz Dihlpt_BR
dc.contributor.authorBolivar, Alexander Pinarespt_BR
dc.date.accessioned2020-11-21T04:26:05Zpt_BR
dc.date.issued2020pt_BR
dc.identifier.urihttp://hdl.handle.net/10183/215361pt_BR
dc.description.abstractGraphs are at the essence of many data representations. The visual analytics over graphs is usually difficult due to their size, which makes their visual display challenging, and their fundamental algorithms, which are often classified as NP-hard problems. The Power Graph Analysis (PGA) is a method that simplifies networks using reduced representations for complete subgraphs (cliques) and complete bipartite subgraphs (bicliques), in both cases with edge reductions. The benefits of a power graph are the preservation of information and its capacity to show essential information about the original network. However, finding an optimal representation (maximum edges reduction) is also an NPhard problem. In this work, we propose BCD, a greedy algorithm that uses a Bitwise Clique Detection approach to finding power graphs. BCD is faster than competing strategies and allows the analysis of bigger graphs. For the display of larger power graphs, we propose an orthogonal layout to prevent overlapping of edges and vertices. Finally, we describe how the structure induced by the power graph is used for clustering analysis of dense graphs. We demonstrate with several datasets the results obtained by our proposal and compare against competing strategies.en
dc.description.abstractOs grafos são essenciais para muitas representações de dados. A análise visual de grafos é usualmente difícil devido ao tamanho, o que representa um desafio para sua visualização. Além de isso, seus algoritmos fundamentais são frequentemente classificados como NP-difícil. Análises dos grafos de potência (PGA em inglês) é um método que simplifica redes usando representações reduzidas para subgrafos completos chamados cliques e subgrafos bipartidos chamados bicliques, em ambos casos com una redução de arestas. Os benefícios da representação de grafo de potência são a preservação de informação e a capacidade de mostrar a informação essencial sobre a rede original. Entretanto, encontrar uma representação ótima (a máxima redução de arestas possível) é também um problema NP-difícil. Neste trabalho, propomos BCD, um algoritmo guloso que usa um abordagem de detecção de bicliques baseado em operações binarias para encontrar representações de grafos de potencia. O BCD é mas rápido que as estratégias atuais da literatura. Finalmente, descrevemos como a estrutura induzida pelo grafo de potência é utilizado para as análises dos grafos densos na detecção de agrupamentos de nodos.pt_BR
dc.format.mimetypeapplication/pdfpt_BR
dc.language.isoengpt_BR
dc.rightsOpen Accessen
dc.subjectPower Graph Analysisen
dc.subjectInformáticapt_BR
dc.subjectEdges reductionen
dc.subjectBiclique detectionen
dc.subjectClustering analysisen
dc.subjectBinary operationen
dc.titleA bitwise clique detection approach for accelerating power graph computation and clustering dense graphspt_BR
dc.typeDissertaçãopt_BR
dc.identifier.nrb001119843pt_BR
dc.degree.grantorUniversidade Federal do Rio Grande do Sulpt_BR
dc.degree.departmentInstituto de Informáticapt_BR
dc.degree.programPrograma de Pós-Graduação em Computaçãopt_BR
dc.degree.localPorto Alegre, BR-RSpt_BR
dc.degree.date2020pt_BR
dc.degree.levelmestradopt_BR


Files in this item

Thumbnail
   

This item is licensed under a Creative Commons License

Show simple item record