Centralidade de Tempo em Grafos Variantes no Tempo

• Ano de defesa: 2015
• Autor(a) principal: Costa, Eduardo Chinelate
• Orientador(a): Vieira, Alex Borges
• Banca de defesa: Ziviani, Artur , Neto, Raul Fonseca
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Federal de Juiz de Fora
• Programa de Pós-Graduação: Programa de Pós-graduação em Ciência da Computação
• Departamento: ICE – Instituto de Ciências Exatas
• País: Brasil
• Palavras-chave em Português: Grafos Variantes no Tempo. Processo de Difusão de Informação. Centralidade de Tempo.
• Área do conhecimento CNPq: Redes de Computadores
• Link de acesso: https://repositorio.ufjf.br/jspui/handle/ufjf/70

Atualmente, há um grande interesse em investigar a dinâmica em Grafos Variantes no Tempo (GVTs). Esses grafos contemplam a evolução temporal, tanto de nós, quanto de arestas. Nesse cenário, de maneira similar a grafos estáticos, o conceito de centralidade geralmente se refere a métricas que avaliam a importância relativa dos vértices. Entretanto, GVTs possibilitam a avaliação da importância dos instantes de tempo (ou estados) de um grafo ao longo de sua existência. Determinar instantes de tempo importantes nesse contexto pode ter aplicações práticas fortes, sendo particularmente úteis para definir melhores momentos para difusão, gerar modelos e prever o comportamento de GVTs. Neste trabalho, nós definimos Centralidade de Tempo em Grafos Variantes no Tempo. A centralidade de tempo avalia a importância relativa dos instantes de tempo. São apresentadas duas métricas de centralidade de tempo voltadas a processos de difusão de informação e uma métrica baseada na disposição das conexões da rede. As métricas foram avaliadas em um conjunto de dados real. Os resultados mostram que os instantes de tempo melhor classificados, de acordo com as métricas criadas, podem tornar o processo de difusão mais rápido e eficiente. Comparado com uma escolha aleatória, o processo de difusão iniciado nos instantes de tempo mais bem classificados pode ser até 2,5 vezes mais rápido, e também pode atingir praticamente o dobro do número de nós na rede em alguns casos.