Registro fonte: Métodos espectrais de partição de grafos

Métodos espectrais de partição de grafos

The Theory of Graphs has great potential for the description and mathematical modeling of phenomena associated to networks. In problems of this nature a recurring difficulty is the size of the network, i.e. the number of vertices and edges. To overcome these difficulties, an alternative is to decomp...

ver descrição completa

Autor principal:	Santos, Guilherme Barbosa dos
Formato:	Trabalho de Conclusão de Curso (Graduação)
Idioma:	Português
Publicado em:	Universidade Tecnológica Federal do Paraná 2020
Assuntos:	Teoria dos grafos Comunidades Representações dos grafos Teoria de redes Matemática Graph theory Communities Representations of graphs Network theory Mathematics CNPQ::CIENCIAS EXATAS E DA TERRA::MATEMATICA
Acesso em linha:	http://repositorio.utfpr.edu.br/jspui/handle/1/9039
Tags:	Adicionar Tag Sem tags, seja o primeiro a adicionar uma tag!

id	riut-1-9039
recordtype	dspace
spelling	riut-1-90392020-11-11T18:55:18Z Métodos espectrais de partição de grafos Spectral methods of graph partitioning Santos, Guilherme Barbosa dos Gonçalves, João Luis Gonçalves, João Luis Ganacim, Francisco Itamarati Secolo Probst, Roy Wilhelm Teoria dos grafos Comunidades Representações dos grafos Teoria de redes Matemática Graph theory Communities Representations of graphs Network theory Mathematics CNPQ::CIENCIAS EXATAS E DA TERRA::MATEMATICA The Theory of Graphs has great potential for the description and mathematical modeling of phenomena associated to networks. In problems of this nature a recurring difficulty is the size of the network, i.e. the number of vertices and edges. To overcome these difficulties, an alternative is to decompose the graph associated with the problem by grouping the vertices with similar properties, thus generating a new graph with fewer vertices but still representing the same phenomenon. These groupings of vertices will be called communities. Another aspect, that cannot be overlooked, is the good presentation of data that graphs offer. In this context, the detection of communities has the role of synthesizing this information even further. However, community detection can rarely be done empirically, especially for large graphs. Therefore, an analytical treatment of the graph is made necessary , with mathematical rigor. This mathematically rigorous treatment is a positive point because it will require the use of more developed theories, such as linear algebra. Thus, we will have a greater amount of tools to approach a theme that might not be familiar to us. This work aims to present the maximization of modularity and the minimization of the cutting function, using spectral analysis of the graph as an alternative to partitioning or decomposition of graphs. A Teoria de Grafos tem grande potencial para a descrição e modelagem matemática de fenômenos associados a redes. Em problemas dessa natureza uma dificuldade recorrente é o tamanho da rede, ou seja, o número de vértices e arestas. Para contornar essas dificuldades, uma alternativa é decompor o grafo associado ao problema, ou ainda agrupar os vértices com propriedades semelhantes, gerando assim um novo grafo com menos vértices mas que mantém uma representação adequada do fenômeno. Esses agrupamentos de vértices serão denominados de comunidades. Outro aspecto, que não pode ser negligenciado, é a boa apresentação dos dados que os grafos oferecem. Nesse sentido a detecção de comunidades tem papel de sintetizar ainda mais essas informações. Contudo a detecção de comunidades raramente pode ser feita empiricamente, principalmente para grafos grandes. Portanto, faz-se necessário um tratamento analítico do grafo, com rigor matemático. Um tratamento matematicamente rigoroso é um ponto positivo pois exigirá o uso de teorias mais desenvolvidas, como a álgebra linear por exemplo. Assim, existirá uma quantidade maior de ferramentas para abordar um tema que não nos é tão familiar. Este trabalho tem como objetivo apresentar a maximização da modularidade e a minimização da função Corte, usando análise espectral do grafo, como uma alternativa à partição ou decomposição de grafos. 2020-11-11T18:55:18Z 2020-11-11T18:55:18Z 2018-12-11 bachelorThesis SANTOS, Guilherme Barbosa dos. Métodos espectrais de partição de grafos. 2018. 43 f. Trabalho de Conclusão de Curso (Licenciatura em Matemática) - Universidade Tecnológica Federal do Paraná, Curitiba, 2018. http://repositorio.utfpr.edu.br/jspui/handle/1/9039 por openAccess application/pdf Universidade Tecnológica Federal do Paraná Curitiba Brasil Licenciatura em Matemática UTFPR
institution	Universidade Tecnológica Federal do Paraná
collection	RIUT
language	Português
topic	Teoria dos grafos Comunidades Representações dos grafos Teoria de redes Matemática Graph theory Communities Representations of graphs Network theory Mathematics CNPQ::CIENCIAS EXATAS E DA TERRA::MATEMATICA
spellingShingle	Teoria dos grafos Comunidades Representações dos grafos Teoria de redes Matemática Graph theory Communities Representations of graphs Network theory Mathematics CNPQ::CIENCIAS EXATAS E DA TERRA::MATEMATICA Santos, Guilherme Barbosa dos Métodos espectrais de partição de grafos
description	The Theory of Graphs has great potential for the description and mathematical modeling of phenomena associated to networks. In problems of this nature a recurring difficulty is the size of the network, i.e. the number of vertices and edges. To overcome these difficulties, an alternative is to decompose the graph associated with the problem by grouping the vertices with similar properties, thus generating a new graph with fewer vertices but still representing the same phenomenon. These groupings of vertices will be called communities. Another aspect, that cannot be overlooked, is the good presentation of data that graphs offer. In this context, the detection of communities has the role of synthesizing this information even further. However, community detection can rarely be done empirically, especially for large graphs. Therefore, an analytical treatment of the graph is made necessary , with mathematical rigor. This mathematically rigorous treatment is a positive point because it will require the use of more developed theories, such as linear algebra. Thus, we will have a greater amount of tools to approach a theme that might not be familiar to us. This work aims to present the maximization of modularity and the minimization of the cutting function, using spectral analysis of the graph as an alternative to partitioning or decomposition of graphs.
format	Trabalho de Conclusão de Curso (Graduação)
author	Santos, Guilherme Barbosa dos
author_sort	Santos, Guilherme Barbosa dos
title	Métodos espectrais de partição de grafos
title_short	Métodos espectrais de partição de grafos
title_full	Métodos espectrais de partição de grafos
title_fullStr	Métodos espectrais de partição de grafos
title_full_unstemmed	Métodos espectrais de partição de grafos
title_sort	métodos espectrais de partição de grafos
publisher	Universidade Tecnológica Federal do Paraná
publishDate	2020
citation	SANTOS, Guilherme Barbosa dos. Métodos espectrais de partição de grafos. 2018. 43 f. Trabalho de Conclusão de Curso (Licenciatura em Matemática) - Universidade Tecnológica Federal do Paraná, Curitiba, 2018.
url	http://repositorio.utfpr.edu.br/jspui/handle/1/9039
_version_	1805309446109265920
score	10,814766

Métodos espectrais de partição de grafos

Registros relacionados