Dissertação

Técnicas de Aproximação para a Betweenness em Redes de Grande Dimensão EVALUATED

O estudo e análise de grafos é actualmente uma importante área de investigação com aplicações em diversas áreas. A Betweenness Centrality destaca-se, dentro das medidas de centralidade, pela forma como exprime a importância e influência de um nó na rede sendo o seu cálculo pretendido para muitas redes. No entanto, com o advento da globalização da tecnologia, cada vez surgem redes maiores cuja análise é necessária, como por exemplo as redes sociais. Para redes como essas, tipicamente com tamanho na ordem dos milhões de nós, o cálculo exacto da Betweenness Centrality é proibitivo. Assim sendo, torna-se essencial explorar alternativas que possam eficientemente aproximar esta medida de centralidade. Este trabalho apresenta um estudo de várias técnicas utilizadas actualmente no cálculo aproximado da Betweenness Centrality. Este trabalho propõe também algumas alternativas, utilizando conceitos como Community Finding e k-core como forma de melhorar o desempenho dos métodos de aproximação.
Betweenness Centrality, Redes Complexas, Medidas de Centralidade, Estimação de Valores

Novembro 23, 2015, 15:0

Publicação

Obra sujeita a Direitos de Autor

Orientação

ORIENTADOR

Alexandre Paulo Lourenço Francisco

Departamento de Engenharia Informática (DEI)

Professor Auxiliar

ORIENTADOR

Luís Manuel Silveira Russo

Departamento de Engenharia Informática (DEI)

Professor Auxiliar