Grafo aleatório: diferenças entre revisões
| Linha 22: | Linha 22: | ||
Percolação está relacionada com a robustez do grafo (também chamado de [[rede]]). Dado um grafo aleatório com n nós e um grau médio '''<k>'''. Em seguida, retire aleatoriamente uma fração '''1 - p''' de nós e deixar apenas uma fração '''p'''. Existe um limiar de percolação crítico '''pc = 1/<k>''' abaixo do qual a rede torna-se fragmentada enquanto acima '''pc''' de um componente ligado gigante existe. <ref name="refname1"></ref> <ref name="refname3"></ref> <ref name="refname4"></ref> <ref name="refname5"></ref> <ref name="refname6"></ref> <ref name="refname7"></ref> |
Percolação está relacionada com a robustez do grafo (também chamado de [[rede]]). Dado um grafo aleatório com n nós e um grau médio '''<k>'''. Em seguida, retire aleatoriamente uma fração '''1 - p''' de nós e deixar apenas uma fração '''p'''. Existe um limiar de percolação crítico '''pc = 1/<k>''' abaixo do qual a rede torna-se fragmentada enquanto acima '''pc''' de um componente ligado gigante existe. <ref name="refname1"></ref> <ref name="refname3"></ref> <ref name="refname4"></ref> <ref name="refname5"></ref> <ref name="refname6"></ref> <ref name="refname7"></ref> |
||
ola<ref name="refname8"></ref> |
|||
{{referências|refs= |
{{referências|refs= |
||
Revisão das 13h50min de 24 de fevereiro de 2013
Definição
Na matemática, o grafo aleatório é um grafo que foi gerado por um processo aleatório. A teoria dos grafos aleatórios está na intersecção entre a teoria dos grafos e teoria da probabilidade, e estuda as propriedades típicas de grafos aleatórios.[1]
Modelos de Grafos Aleatórios
Um grafo aleatório é obtido a partir de um conjunto de n vértices e adicionando bordas entre elas de forma aleatória. Diferentes modelos de grafos aleatórios produzem diferentes distribuições de probabilidade nos grafos. Mais comummente estudada é o proposto de Edgar Gilbert, denotado G (n, p), em que cada aresta possível ocorre de forma independente com probabilidade p. Um modelo relacionado, o modelo Erdős-Rényi denotado G (n, F), atribui probabilidade igual a todos os grafos de arestas exactamente M. O mais rápido algoritmo conhecido por gerar a ex-modelo é proposto por Nobari et al.[2] O último modelo pode ser visto como uma imagem num determinado momento (M) do processo gráfico aleatório ɞ̃(n) o que é um processo estocástico que começa com n vértices e sem arestas, e em cada etapa adiciona uma nova aresta escolhida de modo uniforme a partir do conjunto de bordas desaparecidas.
Se em vez de começar com um conjunto infinito de vértices, e novamente vamos cada borda possível ocorrer independentemente com probabilidade p, então temos um objeto chamado G um grafo infinitamente aleatório. Salvo nos casos triviais quando p é 0 ou 1, como um G quase certamente tem a seguinte propriedade: Dados quaisquer n+m elementos a1,..., an, b1,...,bm Є V, há um vértice c Є V que é adjacente a a1,...,an cada uma e não é adjacente a qualquer um dos b1,...,bm.
Acontece que se o conjunto de vértices é contável, até ao isomorfismo, apenas um único grafo com esta propriedade é chamado de grafo Rado. Assim, qualquer grafo aleatório contável infinitamente é quase certamente um grafo Rado. Analogamente esta grafo pode ser chamado de grafo aleatório. No entanto, o resultado análogo não é verdadeiro para os grafos incontáveis, dos quais há muitos grafos (não isomórficos) que satisfaz a propriedade acima.
Um outro modelo, que generaliza o modelo dos grafos aleatórios de Gilbert, é o modelo de produto escalar aleatório. O grafo de produto escalar aleatório associa a cada vetor um vértice real. A probabilidade de uma aresta uv entre quaisquer vértices u e v é uma função do produto escalar u • v dos seus respectivos vectores.
Os modelos de matriz de probabilidade dos grafos aleatórios através da probabilidade das pontas, que representam a probabilidade p i,j de que a ponta e i,j existe durante um período de tempo especificado. Este modelo é extensível para os grafos direta e indiretamente; ponderado e não ponderado; e estático ou dinâmico.
Para M ≈ pn os dois modelos mais amplamente utilizados, G (n, F) e G (n, p), são quase intercambiáveis.[3]
Propriedades dos Grafos Aleatórios
A teoria dos grafos aleatórios estuda propriedades típicas de grafos aleatórios, aqueles que possuem uma alta probabilidade são grafos desenhados a partir de uma distribuição específica. Por exemplo, podemos pedir para um dado valor de n e p que a probabilidade é de estar conectado é G(n,p). Ao estudar estas questões, os pesquisadores concentram-se no comportamento assintótico dos grafos aleatórios, isto é os valores que várias probabilidades convergem para na mediada em que n cresce muito grande. A teoria de percolação caracteriza a conectividade de grafos aleatórios, especialmente os infinitamente grandes.
Percolação está relacionada com a robustez do grafo (também chamado de rede). Dado um grafo aleatório com n nós e um grau médio <k>. Em seguida, retire aleatoriamente uma fração 1 - p de nós e deixar apenas uma fração p. Existe um limiar de percolação crítico pc = 1/<k> abaixo do qual a rede torna-se fragmentada enquanto acima pc de um componente ligado gigante existe. [1] [3] [4] [5] [6] [7]
ola[8]
Referências
- ↑ a b Béla Bollobás, Random Graphs, 2nd Edition, 2001, Cambridge University Press.
- ↑ Nobari, Sadegh; Lu, Xuesong; Karras, Panagiotis; Bressan, Stéphane (2011), Fast random graph generation, Proceedings of the 14th International Conference on Extending Database Technology (Uppsala, Sweden: ACM).
- ↑ a b Bollobas, B. and Riordan, O.M. "Mathematical results on scale-free random graphs" in "Handbook of Graphs and Networks" (S. Bornholdt and H.G. Schuster (eds)), Wiley VCH, Weinheim, 1st ed., 2003.
- ↑ Newman, M. E. J. (2010). Networks: An Introduction. Oxford.
- ↑ Reuven Cohen and Shlomo Havlin (2010). Complex Networks: Structure, Robustness and Function. Cambridge University Press.
- ↑ Erdős, P. Rényi, A (1959) "On Random Graphs I" in Publ. Math. Debrecen 6, p. 290–297
- ↑ Gilbert, E. N. (1959), "Random graphs", Annals of Mathematical Statistics 30: 1141–1144
- ↑ S.V. Buldyrev, R. Parshani, G. Paul, H.E. Stanley and S. Havlin (2010). "Catastrophic cascade of failures in interdependent network". Nature 464: 1025–8.
