@MastersThesis{Soares:2022:AnNeVu,
author = "Soares, Giovanni Guarnieri",
title = "Beyond the shortest path: an analysis of networks'
vulnerabilities",
school = "Instituto Nacional de Pesquisas Espaciais (INPE)",
year = "2022",
address = "S{\~a}o Jos{\'e} dos Campos",
month = "2022-02-11",
keywords = "complex networks, random walks, vulnerability, communicability,
eficiency, redes complexas, random walks, vulnerabilidade,
comunicabilidade, efici{\^e}ncia.",
abstract = "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{\'e}nyi model,
the linear correlation is also present between the Passaging Index
and the Vulnerability with Efficiency in all cases, while in
Barab{\'a}si-Albert presents more complex correlations between
metrics. RESUMO: Transporte, redes de energia,
comunica{\c{c}}{\~a}o e sistemas de distribui{\c{c}}{\~a}o de
{\'a}gua, {\'o}leo e g{\'a}s influenciam fortemente nosso
bem-estar. Estudar a estrutura dessas infraestruturas
cr{\'{\i}}ticas {\'e} extremamente importante para a qualidade
de vida das pessoas. Modelamos esses sistemas como uma rede usando
a teoria dos grafos. Este trabalho explora m{\'e}tricas
topol{\'o}gicas j{\'a} definidas como Efici{\^e}ncia,
Comunicabilidade e Vulnerabilidade, mas seguindo uma abordagem
inovadora: considerando n{\~a}o apenas os caminhos mais curtos
entre pares de n{\'o}s nas redes. Definimos vulnerabilidade como
uma queda na performance da rede, e performance {\'e} um termo
geral, pass{\'{\i}}vel de ser quantificado por diferentes
m{\'e}tricas. Propomos uma reviravolta no {\'{\i}}ndice de
vulnerabilidade j{\'a} definido usando comunicabilidade como um
desempenho em vez de efici{\^e}ncia. Em primeiro lugar,
comparamos a vulnerabilidade tradicional baseada na
efici{\^e}ncia com a nossa proposta baseada na comunicabilidade.
Desta forma, mostramos como as diferentes m{\'e}tricas destacam
diferentes pontos vulner{\'a}veis e como testar v{\'a}rios
caminhos em vez de apenas o mais curto pode impactar os
resultados. Depois disso, realizamos v{\'a}rias regress{\~o}es
lineares entre as vulnerabilidades e m{\'e}tricas conhecidas (por
exemplo, grau, comprimento do caminho mais curto e
intermedia{\c{c}}{\~a}o). Nossos resultados mostram diferentes
padr{\~o}es de rela{\c{c}}{\~o}es para diferentes topologias de
rede, como Aleat{\'o}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{\'{\i}}cula browniana passa por cada n{\'o}:
{\'{\I}}ndice de Passagem. Comparamos, para cada n{\'o}, tal
{\'{\i}}ndice com outras m{\'e}tricas de rede e encontramos uma
forte correla{\c{c}}{\~a}o linear entre o {\'{\I}}ndice de
Passagem e o grau associado a cada n{\'o}, formando uma
rela{\c{c}}{\~a}o direta, com R2 = 1 para todos os casos de
grafos distintos. Dentre estes c{\'a}lculos, tamb{\'e}m foi
encontradas outras rela{\c{c}}{\~o}es lineares, entre o
{\'{\I}}ndice de Passagem e a Vulnerabilidade com
Eficic{\^e}ncia, na rela{\c{c}}{\~a}o com o modelo de
Erd\ősR{\'e}nyi. Esta linearidade n{\~a}o se mant{\'e}m
t{\~a}o forte no modelo de Barab{\'a}si-Albert, apresentando
outras rela{\c{c}}{\~o}es mais complexas.",
committee = "Quiles, Marcos Gon{\c{c}}alves (presidente) and Santos, Leonardo
Bacelar Lima (orientador) and Macau, Elbert Einstein Nehrer and
Penna, Thadeu Josino Pereira",
englishtitle = "Al{\'e}m do caminho mais curto: uma an{\'a}lise da
vulnerabilidade de redes",
language = "en",
pages = "82",
ibi = "8JMKD3MGP3W34T/46DSFMP",
url = "http://urlib.net/ibi/8JMKD3MGP3W34T/46DSFMP",
targetfile = "publicacao.pdf",
urlaccessdate = "24 abr. 2024"
}