Agglomeration in scale-free random graphs
Carregando...
Arquivos
Data
Autor(es)
Título da Revista
ISSN da Revista
Título de Volume
Editor
Universidade Federal de Minas Gerais
Descrição
Tipo
Tese de doutorado
Título alternativo
Primeiro orientador
Membros da banca
Bernardo Nunes Borges de Lima
Marco Vinicius Bahi Aymone
Daniel Ratton Figueiredo
Roberto Imbuzeiro Felinto de Oliveira
Marco Vinicius Bahi Aymone
Daniel Ratton Figueiredo
Roberto Imbuzeiro Felinto de Oliveira
Resumo
Neste trabalho investigamos três modelos de grafos aleatórios que geram grafos livres de escala. Nosso interesse reside na formação de subgrafos completos, coeficientes de aglomeração, distribuição dos graus e diâmetro. Nossos principais resultados mostram a existência assintoticamente quase certamente de um subgrafo completo cuja ordem vai para infinito, além de cota superior para o diâmetro em um dos modelos. Mostramos também que em um dos modelos, conhecido como Holme-Kim, os coeficientes de aglomeração local e global possuem comportamentos bastante diferentes. Enquanto o primeiro permanece longe do zero, o segundo tende a zero à medida que o tempo vai para infinito.
Abstract
In this work we investigate three random graph models capable of generating scale-free graphs. Our main interest relies on formation of cliques, calculating clustering coefficients, the degree distribution anddiameters. The main results we have proven show the existence asymptotically almost surely the existence of a clique whose order goes to infinity as the graphs order goes to infinity, concentration inequalities for the degrees and upper bound for the diameter in one of theses models. We also show that in the model known as Holme-Kims model the clustering coefficients local and global present quite distinct behavior.Whereas the former is bounded away from zero a.a.s, the latter goes to zero as the time goes to infinity.
Assunto
Matemática, Leis de escala (Fisica estatistica), Aglomeração, Teoria dos grafos, Graficos aleatorios
Palavras-chave
Livres de escala, Lei de potência, Aglomeração, Grafos, Diâmetro, Cliques