Centralidade de Tempo em Grafos Variantes no Tempo

• Eduardo Chinelate Costa UFJF
• Alex Borges Vieira UFJF
• Ana Paula Couto da Silva UFMG

DOI: https://doi.org/10.5753/ctd.2016.9130

Resumo

O conceito de centralidade geralmente se refere a métricas que avaliam a importância relativa dos vértices. Entretanto, Grafos Variantes no Tempo (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 pode ser útil para definir melhores momentos para difusão, gerar modelos e prever o comportamento de GVTs. Neste trabalho, é definido o conceito de Centralidade de Tempo em GVTs. A centralidade de tempo avalia a importância relativa dos instantes de tempo. São apresentadas e avaliadas duas métricas de centralidade de tempo voltadas a processos de difusão de informação. Os resultados mostram que os instantes de tempo melhor classificados, de acordo com as métricas criadas, podem tornar o processo de difusão até 2,5 vezes mais rápido e atingir o dobro do número de nós em certos casos.

Referências

Lucet, J. C., Laouenan, C., Chelius, G., Veziris, N., Lepelletier, D., Friggeri, A., Abiteboul, D., Bouvet, E., Mentre, F., and Fleury, E. (2012). Electronic Sensors for Assessing Interactions between Healthcare Workers and Patients under Airborne Precautions. PLoS ONE, 7(5):e37893.

Spasojevic, N., Li, Z., Rao, A., and Bhattacharyya, P. (2015). When-to-post on social networks. In Prof. of the ACM SIGKDD Conference on Knowledge Discovery and Data Mining (ACM KDD).

Wehmuth, K., Ziviani, A., and Fleury, E. (2014). A Unifying Model for Representing Time-Varying Graphs. ArXiv e-prints.