Particionamento de grafo planar com distribuição dos pesos dos nodos seguindo lei de potência

• Ano de defesa: 2013
• Autor(a) principal: Palheta, Rodrigo Matos
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Palavras-chave em Português: Teoria dos grafos; Redes complexas; Algoritmos
• Link de acesso: https://biblioteca.sophia.com.br/terminalri/9575/acervo/detalhe/99093

Há trabalhos que evidenciam que a distribuição de crimes por setores censitários em grandes cidades segue uma lei de potência, a criminalidade é um exemplo de sistema complexo que pode ser mapeado em regiões geográficas. A evidência citada significa que, há poucos lugares que concentram muitos crimes e muitos lugares que concentram poucos crimes. Partindo dessa premissa, se uma região geográfica formada por vários setores censitários possuem uma distribuição que segue lei de potência, seria possível dividir essa região em várias partes de tal forma que essas partes mantenham distribuições semelhantes à distribuição da região? O trabalho proposto nesta dissertação tenta responder essa pergunta utilizando redes complexas e algoritmos evolutivos. A representação de uma rede neste trabalho é um grafo planar onde os nodos são centroides de áreas geográficas, as arestas representam a adjacência entre essas áreas, e cada nodo tem um peso representando um dado da área, que poderia ser o número de crimes registrados nesta área. O problema desta pesquisa reside no contexto de particionar um grafo planar com o intuito de encontrar partições que possuem distribuições dos pesos dos nodos semelhantes à distribuição dos pesos dos nodos do grafo, cada distribuição da partição funcionará como uma amostra da distribuição do grafo, seguindo uma lei de potência, essas distribuições das partições serão úteis para ter um melhor entendimento de sistemas complexos que podem ser mapeados em regiões geográficas. Foram criados dois algoritmos evolutivos objetivando solucionar o problema citado, nas bases de dados testadas foi possível encontrar aproximadamente 90% das partições com distribuições dos pesos dos nodos semelhantes à distribuição do grafo original, e seguindo lei de potência. Palavras-chave: Particionamento de Grafos, Lei de Potência, Grafos Planares, Redes Complexas e Algoritmos Evolutivos.