FenixEdu™

Dissertação

Spanning edge betweenness for large graphs and percolation EVALUATED

Detalhes: 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.
Keywords: SEB, Centralidade aproximada, Remoção de arestas.

Discussão: novembro 14, 2022, 10:30