Detalhes do Documento

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.

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.