Submitted by Renata Lopes (renatasil82@gmail.com) on 2015-12-02T09:44:19Z
No. of bitstreams: 1
eduardochinelatecosta.pdf: 1021822 bytes, checksum: b72dff6cf071e8de1cb23f6cb7d27245 (MD5) / Made available in DSpace on 2015-12-02T09:44:19Z (GMT). No. of bitstreams: 1
eduardochinelatecosta.pdf: 1021822 bytes, checksum: b72dff6cf071e8de1cb23f6cb7d27245 (MD5)
Previous issue date: 2015-02-23 / FAPEMIG - Fundação de Amparo à Pesquisa do Estado de Minas Gerais / 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. / Currently, there is a great interest in investigating dynamics in Time-Varying Graphs
(TVGs). These graphs contemplate the temporal evolution, both nodes and edges. In
this scenario, similar to static graphs, centrality usually refers to metrics that assess the
relative importance of vertices. However, in TVGs it is possible to assess the importance of
time instants (or states) of a graph throughout its existence. Determining important time
instants in this context may have strong practical applications and is particularly useful for
defining best times to spread, generate models and predict the behavior of TVGs. In this
paper, we define time centrality in Time-Varying Graphs. Time centrality evaluates the
relative importance of time instants. We present two time centrality metrics focused on
information dissemination processes and another based on layout of network connections..
We evaluate metrics we define relying in a real dataset from an hospital environment. Our
results show that the best classified time instants, according to created metrics, can make
a faster and more efficient diffusion process. Compared to a random choice, the diffusion
process starting at best rated time instants can up to 2.5 times faster, and it also can
reach almost double the number of nodes in the network in some cases.
| Identifer | oai:union.ndltd.org:IBICT/oai:hermes.cpd.ufjf.br:ufjf/70 |
| Date | 23 February 2015 |
| Creators | Costa, Eduardo Chinelate |
| Contributors | Vieira, Alex Borges, Silva, Ana Paula Couto da, Ziviani, Artur, Neto, Raul Fonseca |
| Publisher | Universidade Federal de Juiz de Fora, Programa de Pós-graduação em Ciência da Computação, UFJF, Brasil, ICE – Instituto de Ciências Exatas |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Source | reponame:Repositório Institucional da UFJF, instname:Universidade Federal de Juiz de Fora, instacron:UFJF |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0017 seconds