Limite do fluído para o grafo aleatório de Erdos-Rényi / Fluid limit for the Erdos-Rényi random graph

AUTOR(ES)

Fabio Marcellus Lima Sá Makiyama Lopes

DATA DE PUBLICAÇÃO

2010

RESUMO

Neste trabalho, aplicamos o algoritmo Breadth-First Search para encontrar o tamanho de uma componente conectada no grafo aleatório de Erdos-Rényi. Uma cadeia de Markov é obtida deste procedimento. Apresentamos alguns resultados bem conhecidos sobre o comportamento dessa cadeia de Markov. Combinamos alguns destes resultados para obter uma proposição sobre a probabilidade da componente atingir um determinado tamanho e um resultado de convergência do estado da cadeia neste instante. Posteriormente, aplicamos o teorema de convergência de Darling (2002) a sequência de cadeias de Markov reescaladas e indexadas por N, o número de vértices do grafo, para mostrar que as trajetórias dessas cadeias convergem uniformemente em probabilidade para a solução de uma equação diferencial ordinária. Deste resultado segue a bem conhecida lei fraca dos grandes números para a componente gigante do grafo aleatório de Erdos-Rényi, no caso supercrítico. Além disso, obtemos o limite do fluído para um modelo epidêmico que é uma extensão daquele proposto em Kurtz et al. (2008).

ASSUNTO(S)

cadeias de markov markov chains convergência random graphs convergence grafos aleatórios.

Documentos Relacionados

• Metaheurísticas para o problema de agrupamento de dados em grafo
• Orientações pfaffianas e o furtivo grafo de Heawood
• Teorema Central do Limite para o modelo O(N) de Heisenberg hierárquico na criticalidade e o papel do limite N ->infinito na dinâmica dos zeros de Lee-Yang
• Limit theorems for random trees.
• Experimental research of the random fuse model