Dissertação

{en_GB=Spanning edge betweenness for large graphs and percolation} {} EVALUATED

{pt=As medidas de centralidade são uma ferramenta vital para estudar redes. Após a introdução de uma nova medida de centralidade, é importante que esta faça parte de estudos, para se tornar relevante na comunidade. Spanning Edge Betweenness foi introduzida recentemente, e este é um desses estudos. Uma visão geral dos conceitos de ciência das redes e medidas de centralidade é fornecida. Uma breve explicação dos conceitos teóricos da Spanning Edge Betweenness também pode ser vista neste trabalho. As opções de implementação podem ser consultadas juntamente com experiências práticas para tentar minimizar o custo computacional do tempo de cálculo desta mesma medida. Essas experinências consistem em aproveitar o algoritmo de computação paralelizável ou algoritmos de pré-processamento que podem ter um impacto positivo no tempo de cálculo. Alcançámos resultados promissores para ambas as alternativas. Outro método para reduzir o tempo de computação poderia ser o cálculo dos valores de centralidade aproximados. Isso foi feito anteriormente para Spanning Edge Betweenness em redes não pesadas. Neste trabalho, propomos uma implementação desta aproximação para redes pesadas. Este método também alcança resultados promissores em relação às melhorias no tempo de computação. Por fim, realizamos a percolação de arestas, comparando Spanning Edge Betweenness com Edge Betweenness em relação a cinco métricas. Este trabalho disponibiliza a Spanning Edge Betweenness para uso em grafos de grande escala, além de contribuir para um maior entendimento desta medida, no que diz respeito à conectividade de uma rede., en=Centrality measures are a vital tool to study networks. After a new centrality measure is introduced, it is important to be part of studies, to become relevant in the community. Spanning Edge Betweenness was recently introduced, and this is one of those studies. An overview of network science concepts and centrality measures is provided. A brief explanation of Spanning Edge Betweenness' theoretical concepts can also be seen in this work. The implementation options can also be consulted along with practical experimentations to try to minimize the computational time cost of calculating such centrality measure. These experimentations consist of either taking advantage of the parallelizable computation algorithm, or preprocessing algorithms that could positively impact the calculation time. We achieved promising results for both alternatives. Another method to reduce the computation time could be the calculation of the approximated centrality values. This has been previously done for Spanning Edge Betweenness in unweighted networks. In this work, we propose an implementation for this approximation for weighted networks. This method also achieves promising results regarding the improvements in computation time. Finally, we perform edge percolation, comparing Spanning Edge Betweenness to Edge Betweenness regarding five metrics. This work makes Spanning Edge Betweenness available to be used for large-scale graphs, while also contributing to a bigger understanding of said measure, regarding the connectivity of a network.}
{pt=SEB, Centralidade aproximada, Remoção de arestas., en=SEB, Approximate centrality values, Edge percolation.}

novembro 14, 2022, 10:30

Publicação

Obra sujeita a Direitos de Autor

Orientação

ORIENTADOR

Pedro Tiago Gonçalves Monteiro

Departamento de Engenharia Informática (DEI)

Professor Associado

ORIENTADOR

Andreia Sofia Monteiro Teixeira

Faculdade de Ciências da Universidade de Lisboa (FCUL)

Professor Auxiliar