Avaliação distribuída de centralidade em redes complexas

Detalhes bibliográficos
Ano de defesa: 2012
Autor(a) principal: Wehmuth, Klaus
Orientador(a): Não Informado pela instituição
Banca de defesa: Não Informado pela instituição
Tipo de documento: Dissertação
Tipo de acesso: Acesso aberto
Idioma: por
Instituição de defesa: Laboratório Nacional de Computação Científica
Serviço de Análise e Apoio a Formação de Recursos Humanos
BR
LNCC
Programa de Pós-Graduação em Modelagem Computacional
Programa de Pós-Graduação: Não Informado pela instituição
Departamento: Não Informado pela instituição
País: Não Informado pela instituição
Palavras-chave em Português:
Link de acesso: https://tede.lncc.br/handle/tede/144
Resumo: Os últimos anos tem mostrado um crescimento contínuo no estudo de redes complexas de grande porte relacionadas com diversas áreas de conhecimento, tais como Biologia, Sociologia, Economia, Internet, entre outras. Nesse contexto, o conceito de centralidade oferece uma medida da importância relativa dos nós que compõem uma rede complexa, sendo portanto de fundamental importância para a análise e estudo destas redes. Existem várias definições diferentes para centralidade em redes segundo a aplicação que pretendem, usando critérios distintos para ordenar a importância dos nós. Entre essas diferentes definições de centralidade, Closeness Centrality é uma das mais tradicionais e afere a importância de cada nó pela sua proximidade com todos os demais nós da rede. Dessa maneira, essa forma de centralidade avalia os nós melhor posicionados para realizar processos de difusão de forma eficiente na rede, sendo portanto de grande valia para análise de redes complexas com aplicações em diversas áreas. Entretanto, o cálculo deste tipo de centralidade apresenta um alto custo computacional, uma vez que é necessário que se calcule a distância entre todos os pares de nós da rede. Isso faz ainda que seja necessário conhecer completamente a topologia da rede para que seja possível calcular as distâncias entre os nós. Em virtude disso, o uso de Closeness Centrality se torna impraticável para redes de grande porte, comumente encontradas em diversas áreas do conhecimento. No entanto, em termos práticos, a ordem dos nós em função de sua centralidade é mais relevante do que os valores de centralidade em si. Assim, este trabalho apresenta um método distribuído que pode ser utilizado para calcular vários tipos de centralidades, entre elas uma cuja ordenação dos nós tem um alto grau de correlação com a ordenação obtida pelo uso de Closeness Centrality. O método proposto funciona de maneira totalmente distribuída, baseando-se em conhecimento local não necessitando do conhecimento completo da topologia da rede, e é computacionalmente menos custoso que o método tradicional. Estas características fazem com que o método proposto seja aplicável a redes complexas scale-free de grande porte, possibilitando uma aproximação eficiente da ordenação de Closeness Centrality a estas redes, como analisado nos resultados da dissertação.