%0 Thesis
%4 sid.inpe.br/mtc-m21d/2022/02.25.14.41
%2 sid.inpe.br/mtc-m21d/2022/02.25.14.41.01
%T Beyond the shortest path: an analysis of networks' vulnerabilities
%J Além do caminho mais curto: uma análise da vulnerabilidade de redes
%D 2022
%8 2022-02-11
%9 Dissertação (Mestrado em Computação Aplicada)
%P 82
%A Soares, Giovanni Guarnieri,
%E Quiles, Marcos Gonçalves (presidente) ,
%E Santos, Leonardo Bacelar Lima (orientador) ,
%E Macau, Elbert Einstein Nehrer ,
%E Penna, Thadeu Josino Pereira,
%I Instituto Nacional de Pesquisas Espaciais (INPE)
%C São José dos Campos
%K complex networks, random walks, vulnerability, communicability, eficiency, redes complexas, random walks, vulnerabilidade, comunicabilidade, eficiência.
%X Transportation, power grids, communication, water, oil, and gas distribution systems heavily influence our well-being. Studying the structure of those critical infrastructures is extremely important for peoples quality of life. We model those systems as a network using the graph theory. This work explores already defined topological metrics such as Efficiency, Communicability, and Vulnerability, but following an innovative approach: considering not only the shortest paths between pairs of nodes in the networks. We define vulnerability as a drop in the networks performance, and performance is a general term, able to be quantified by different metrics. We propose a twist in the already defined vulnerability index using communicability as a performance instead of efficiency. Firstly, we compare the traditional efficiency-based vulnerability with our proposed communicability-based one. This way, we show how the different metrics highlight different vulnerable points and how testing multiple paths instead of only the shortest can impact the results. After that, we perform several linear regressions between the vulnerabilities and well-known metrics (e.g., degree, shortest path length, and betweenness). Our findings show different patterns of relations for different network topologies, such as Random and Scale Free. Finally, we explore RandomWalks on networks by walking on them.We run a RandomWalk on the network and count how many times the Brownian particle goes through each node: Passaging Index. We compare, for each node, the Passaging Index with other metrics and find linear correlations between the Passaging Index and Degree, resulting in a strong linear correlation, with a R2 = 1. To the ErdősRényi model, the linear correlation is also present between the Passaging Index and the Vulnerability with Efficiency in all cases, while in Barabási-Albert presents more complex correlations between metrics. RESUMO: Transporte, redes de energia, comunicação e sistemas de distribuição de água, óleo e gás influenciam fortemente nosso bem-estar. Estudar a estrutura dessas infraestruturas críticas é extremamente importante para a qualidade de vida das pessoas. Modelamos esses sistemas como uma rede usando a teoria dos grafos. Este trabalho explora métricas topológicas já definidas como Eficiência, Comunicabilidade e Vulnerabilidade, mas seguindo uma abordagem inovadora: considerando não apenas os caminhos mais curtos entre pares de nós nas redes. Definimos vulnerabilidade como uma queda na performance da rede, e performance é um termo geral, passível de ser quantificado por diferentes métricas. Propomos uma reviravolta no índice de vulnerabilidade já definido usando comunicabilidade como um desempenho em vez de eficiência. Em primeiro lugar, comparamos a vulnerabilidade tradicional baseada na eficiência com a nossa proposta baseada na comunicabilidade. Desta forma, mostramos como as diferentes métricas destacam diferentes pontos vulneráveis e como testar vários caminhos em vez de apenas o mais curto pode impactar os resultados. Depois disso, realizamos várias regressões lineares entre as vulnerabilidades e métricas conhecidas (por exemplo, grau, comprimento do caminho mais curto e intermediação). Nossos resultados mostram diferentes padrões de relações para diferentes topologias de rede, como Aleatória e Livre de Escala. Finalmente, exploramos Random Walks em redes caminhando sobre elas. Executamos uma Random Walk na rede e contamos quantas vezes a partícula browniana passa por cada nó: Índice de Passagem. Comparamos, para cada nó, tal índice com outras métricas de rede e encontramos uma forte correlação linear entre o Índice de Passagem e o grau associado a cada nó, formando uma relação direta, com R2 = 1 para todos os casos de grafos distintos. Dentre estes cálculos, também foi encontradas outras relações lineares, entre o Índice de Passagem e a Vulnerabilidade com Eficicência, na relação com o modelo de ErdősRényi. Esta linearidade não se mantém tão forte no modelo de Barabási-Albert, apresentando outras relações mais complexas.
%@language en
%3 publicacao.pdf