Redes temporais

Uma rede temporal, também conhecida como rede variável no tempo, é uma rede cujas arestas estão ativas apenas em determinados pontos no tempo. Cada aresta carrega informações sobre quando está ativa, junto com outras características possíveis, como um peso. As redes variáveis ​​no tempo são de particular relevância para os processos de disseminação, como a disseminação de informações e doenças, uma vez que cada aresta é uma oportunidade de contato e a ordem de tempo dos contatos está incluída.

Existem diversas aplicações em grafos dinâmicos, uma delas é na análise de VANET’s (Vehicular Ad Hoc Networks) para análise de tráfego através do tempo. Além disso, esse tipo de rede são utilizadas para analisar todo tipo de dados que estejam indexados no tempo, como redes de comunicação, como telefonemas, emails e até a análise de doenças.

Um conceito crucial em gráficos que variam no tempo é o de jornada que é a extensão temporal da noção de caminho e forma a base dos conceitos temporais mais recentemente introduzidos. Uma sequência de casais $J=\left\{(e_{1},t_{1}),(e_{2},t_{2}),...,(e_{k},t_{k})\right\}$, de tal modo que, $\left\{e_{1},e_{2},...,e_{k}\right\}$ é uma caminhada em G.

Denotamos por $departure(J)$, e $Arrival(J)$, a data de início t₁ e a última data t_k de uma viagem J, respectivamente. As viagens podem ser pensadas como caminhos ao longo do tempo de uma ponto inicial para um destino e, portanto, tem um topológico e um comprimento temporal.

Vamos denotar por $J'$ o conjunto de todas as viagens possíveis em um grafo variante no tempo G e por $J'(u,v)\subseteq J'$ aquelas viagens começando em nó u e terminando no nó v. Em um grafo variante no tempo, há três medidas distintas naturais de distância e, portanto, três tipos diferentes de viagens “mínimas”.

• A distância mais curta de um nó u a um nó v no tempo t é simplesmente:

$d_{t}(u,v)=Min\left\{\left\vert J\right\vert :J\in J'(u,v)\land Departure(J)\geq t\right\}$

• A distância mais importante de u a v no tempo t é:

$\varphi (u,v)=Min\left\{Arrival(J)-t:J\in J'(u,v)\land Departure(J)\geq t\right\}$

• A distância mais rápida de u a v no tempo t é definida como:

$\varphi '(u,v)=Min\left\{\lVert J\rVert -t:J\in J'(u,v)\land Departure(J)\geq t\right\}$

Representação

Para modelagem de TVG’s é necessário incluir como á a conexão das arestas com os vértices. Uma aresta em um grafo estático é representado pelos vértices que ela conecta e o seu peso. Já em um grafo dinâmico as arestas são representadas por uma quádrupla onde E = (u, t_p, v, t_q), onde u e v são os vértices e t_p e t_q são os instantes de tempo da ligação inicial e final.

Exemplo de um grafo variante no tempo

Métricas

No contexto de TVG’s existem métricas atemporais e métricas temporais.

Parâmetros atemporais são definidos em redes estáticas e sua evolução ao longo do tempo pode ser observada medindo-os ao longo sequências de gráficos estáticos, onde cada gráfico da sequência corresponde à agregação de interações que ocorrem em um determinado intervalo de tempo (nós os chamamos de pegadas de um TVG). Indicadores temporais, por outro lado, são definidos apenas em gráficos variáveis ​​no tempo, tendo em conta a sua natureza temporal.

Métricas atemporais

• Densidade: Um indicador importante e amplamente utilizado que visa medir a estrutura da rede é a densidade, que mede o quão perto está de um gráfico completo.A densidade de um gráfico G = (V; E) é definido como:

$D={\frac {\left\vert E\right\vert }{\left\vert V\right\vert *{\bigl (}\left\vert V\right\vert -1{\bigr )}}}$

A evolução da densidade pode ser observada olhando para sua tendência sobre a sequência de pegadas SP = G_t1, G_t2, … , G_ti. a tendência deste valor reflete a formação da topologia da rede durante tempo de uma perspectiva global.

• Coeficiente de Clusterização O coeficiente de clusterização é usado na análise de redes sociais para caracterizar a arquitetura aspectos. Esse coeficiente por nó é mais comumente definido por:

$C(x)={\frac {\left\vert (u,v):u,v\in N(x)\right\vert }{deg(x)(deg(x)-1)}}$

O coeficiente de clusterização médio de um gráfico pode então ser definido como a média de todos os nós:

$AC={\frac {1}{\left\vert V\right\vert }}\sum _{x\in V}C(x)$

Assim como a densidade, pode-se observar a evolução dessas propriedades medindo as pegadas de SP.

• Modularidade: Modularidade mede como a estrutura de uma determinada rede é modular, ou seja, como pode ser decomposta em sub partes.. A modularidade de um par de nós u e v é definida como:

$M(u,v)={\frac {deg(u)*deg(v)}{2\left\vert E\right\vert }}$

O uso mais comum da modularidade é a detecção de estruturas comunitárias. Assim como no Coeficiente de Clusterização e na Densidade, a Modularidade é analisada conforme uma sequência de passos SP.

Métricas temporais

• Distância: O conceito básico desta classe de indicadores é a distância. Em particular, existem três diferentes tipos de distâncias (mais curtas, mais rápidas e mais importantes) que são respectivamente observado D(u; v), φ(u; v) φ'(u; v). A visão temporal (ou simplesmente visão) que um nó v tem de outro nó u no tempo t, denotado Φ_{v; t}(u), é definido como o último (ou seja, o maior) t’ ≤ t em que uma mensagem recebida no tempo t em v poderia foram emitidos em u; ou seja, no formalismo TVG .

$max\left\{departure(J):J\in J'(u,v)\land arrival(J)\leqslant t\right\}$

Este conceito poderia, como o de distância, ser declinado em três versões (o acima é simétrico à distância mais avançada). Estudando a evolução das distâncias temporais ou visualizações ao longo de uma sequência de os subgrafos refletem o quão próximos no tempo, ou em saltos, os nós tendem tornar-se.

• Diâmetro: A excentricidade de um nó u em um TVG G pode ser definido em termos de viagens mais curtas como:

$e(u)=max\left\{d(u,v):v\in V\right\}$

onde d pode ser substituído por φ(u; v) ou φ'(u; v) para obter o primeiro excentricidade ε(u), ou a excentricidade mais rápida έ(u), respectivamente. A excentricidade de um nó reflete diretamente sua capacidade de acessibilidade, e, portanto, o impacto que pode ter na rede .

• Centralidade:

* Temporal Closeness: Em um contexto estático, a proximidade mede a média dos caminhos mais curtos entre um nó e todos os outros nós alcançáveis . Pode ser definido formalmente como:

$TC(u)=\sum _{v\in V\backslash u}{\frac {d(u,v)}{\left\vert \left\{w\in V:\exists J\in J'(u,w)\right\}\right\vert }}$

e, novamente, é possível declinar para um mais curto, mais importante φ'(u; v), ou versões mais rápidas φ'(u; v).

* Temporal Betweenness: A intermediação de um nó em um gráfico estático mede as ocorrências desse nó nos caminhos mais curtos de outros nós . A definição pode ser geralmente formulada como:

$B(q)=\sum _{v\neq u\neq q\in V}{\frac {\left\vert d'(u,v,q)\right\vert }{\left\vert d(u,v)\right\vert }}$

onde |d (u; v)| é o número de viagens mais curtas entre u e v em que o gráfico variável no tempo G_ti e |d’ (u; v; q)| é o número dos mais curtos viagens, entre elas, que passam por q. Podemos definir analogamente a diferença temporal em termos de distância principal ou mais rápida, substituindo d (u; v) por φ(u; v) ou φ'(u; v).