FenixEdu™

Dissertação

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

Detalhes: 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.
Keywords: Betweenness Centrality, Redes Complexas, Medidas de Centralidade, Estimação de Valores

Discussão: novembro 23, 2015, 15:0