Use este identificador para citar ou linkar para este item: https://repositorio.ufjf.br/jspui/handle/ufjf/10115
Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
anaclaudiamartinsdesouza.pdf20.08 MBAdobe PDFThumbnail
Visualizar/Abrir
Tipo: Dissertação
Título: Centralidade de tempo baseada em conectividade em grafos variantes no tempo
Autor(es): Souza, Ana Cláudia Martins de
Primeiro Orientador: Vieira, Alex Borges
Co-orientador: Wehmuth, Klaus
Membro da banca: Bernardino, Heder Soares
Membro da banca: Ziviani, Artur
Resumo: Os Grafos Variantes no Tempo (GVTs) nos permitem estudar e entender melhor a dinâmica dos sistemas do mundo real, pois conseguem expressar as variações de suas conexões ao longo do tempo. A noção de centralidade em cenários de GVT, geralmente, se referem a métricas que avaliam a importância relativa dos nós ao longo do tempo na evolução da rede dinâmica complexa. A noção de Centralidade do Tempo, que avalia a importância relativa de instantes de tempo em redes complexas dinâmicas, ainda é pouco explorada. De fato, os poucos trabalhos sobre a centralidade do tempo baseiam suas descobertas no processo de difusão, por exemplo, identificando o melhor momento para receber uma mensagem ou o instante crucial para aplicar uma vacina em determinada população. Em contraste, neste trabalho, estudamos a Centralidade do Tempo sob a ótica da conectividade de rede. Nós propomos duas métricas para identificar o instante de tempo mais importante na rede. A primeira é a Centralidade de Grau do Tempo, que possui a ideia tradicional, mas calcula o número de ligações que cada instante de tempo possui. Já a segunda, Centralidade de PageRank do Tempo, classifica os instantes de tempo de acordo com o número de arestas entrantes e do peso carregado por cada aresta. Esta segue o princípio da métrica tradicional de PageRank. Modelamos uma rede de transporte público por meio de um GVT, no qual avaliamos as métricas propostas. Nos resultados obtidos validamos que as centralidades calculadas são eficazes para identificar e classificar os instantes de tempo mais importantes do sistema. Vimos também que é fundamental aplicar as métricas no conjunto de dados que representa a rede como um todo, pois assim será identificado o instante de tempo mais importante da rede completa. No cenário avaliado, visualizamos horários que se destacam em cada dia, como por exemplo, pelo número de partidas e chegadas.
Abstract: Time-varying Graphs (GVTs) allow us to study and better understand the dynamics of real-world systems because they can express the variations of their connections over time. The notion of centrality in GVT scenarios generally refers to metrics that assess the relative importance of nodes over time in the evolution of the complex dynamic network. The notion of the time centrality, which evaluates the relative importance of time instants in dynamic complex networks, is still little explored. Indeed, the few works on the time centrality base their findings on the diffusion process, for example by identifying the best time to receive a message or the crucial time to apply a vaccine in a particular population. In contrast, in this work, we study the Centrality of Time from the point of view of network connectivity. We propose two metrics to identify the most important time in the network. The first is the Time Degree Centrality, which has the traditional idea but calculates the number of connections that each instant of time has. The second, Time PageRank Centrality, classifies the time instants according to the number of incoming edges and the weight loaded by each edge. This follows the principle of traditional PageRank metrics. We model a Public Transport Network through a GVT, in which we evaluate the proposed metrics. In the obtained results we validate that the calculated centralities are effective to identify and classify the most important instants of time of the system. We have also seen that it is fundamental to apply the metrics in the data set that represents the network as a whole because this will identify the most important time instant of the complete network. In the scenario evaluated, we visualize times that stand out each day, such as the number of departures and arrivals.
Palavras-chave: Centralidade de tempo
Grafos variantes no tempo
Conectividade
Time centrality
Time-varyng graphs
Connectivity
CNPq: CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
Idioma: por
País: Brasil
Editor: Universidade Federal de Juiz de Fora (UFJF)
Sigla da Instituição: UFJF
Departamento: ICE – Instituto de Ciências Exatas
Programa: Programa de Pós-graduação em Ciência da Computação
Tipo de Acesso: Acesso Aberto
URI: https://repositorio.ufjf.br/jspui/handle/ufjf/10115
Data do documento: 29-Mar-2019
Aparece nas coleções:Mestrado em Ciência da Computação (Dissertações)



Os itens no repositório estão protegidos por licenças Creative Commons, com todos os direitos reservados, salvo quando é indicado o contrário.