Grafo aleatório

Ciência da Rede
Teoria
Grafo Rede complexa Contágio Redes de pequeno mundo Scale-free Estrutura comunitária Percolação Evolução Difusão de inovações (redes sociais) Controlabilidade Desenho grafo Capital social Análise de links Otimização Reciprocidade Transitividade Ligação preferencial Teoria do equilíbrio Efeito de rede Influência social
Tipos de Rede
Rede de computadores Telecomunicação Rede social Neural Artificial Interdependente Semântico Dependência Fluxo
Grafos
Caraterísticas Clique Componente Corte Ciclo Estrutura de dados Aresta Laço Vizinhança Caminho Vértice Lista de adjacência / matriz Incidência Lista / matrix Tipos Grafo bipartido Grafo completo Grafo orientado Hipergrafo Multigrafo Aleatórios Ponderado
Métricas & Algoritmos
Centralidade Grau Betweenness Proximidade PageRank Clustering Centralidades Baseadas na Dissimilaridades Distribuição de Graus Correlação de Graus Assortatividade Distância Modularidade
Modelos
Grafo Aleatório Erdös–Rényi Barabási–Albert Watts–Strogatz Exponencial Aleatório (ERGM) Epidemia Hierárquica
Categorias
Teoria dos grafos Teoria das redes complexas

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. Do ponto de vista matemático, grafos aleatórios são usados para responder a perguntas sobre as propriedades dos grafos típicos. As suas aplicações práticas são encontradas em todas as áreas em que as redes complexas precisam ser modeladas - um grande número de modelos de grafos aleatórios são conhecidos, refletindo os diversos tipos de redes complexas encontradas em diferentes áreas. Num contexto matemático, grafo aleatório refere-se quase exclusivamente ao modelo de grafo aleatório Erdös-Rényi. Em outros contextos, qualquer modelo gráfico pode ser referido como um grafo aleatório.

Modelos de Grafos Aleatórios

Um grafo aleatório é obtido a partir de um conjunto de n vértices e adicionando arestas entre elas de forma aleatória. O objetivo do estudo nesta área é determinar em que fase, uma propriedade particular do grafo, poderá ocorrer. Diferentes modelos de grafos aleatórios produzem diferentes distribuições de probabilidade nos grafos. Mais comumente estudada é o proposto de Edgar Gilbert, denotado G (n, p), em que cada aresta possível ocorre de forma independente com probabilidade p. A probabilidade de um grafo aleatório com m arestas é $p^{m}(1-p)^{N-m},$. Um modelo relacionado, o modelo de Erdős-Rényi denotado G (n, F), atribui a probabilidade igual a todos os grafos de arestas exatamente M. Com a notação $N={\begin{bmatrix}n\\2\end{bmatrix}},$ com 0 ≤ M ≤ N, G(n,p) tem ${\begin{bmatrix}N\\M\end{bmatrix}}$ e cada elemento ocorre com probabilidade ${\begin{bmatrix}N\\M\\\end{bmatrix}}^{-1}.$.

O mais rápido algoritmo conhecido por gerar a ex-modelo é proposto por Nobari et al. 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.

Grafos regulares aleatórias formam um caso especial, com propriedades que podem diferir dos grafos aleatórios em geral.

Uma vez que temos um modelo de grafos aleatórios, cada função de grafos, torna-se uma variável aleatória. O estudo deste modelo é o de determinar, ou pelo menos estimar a probabilidade de uma propriedade poder ocorrer.

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.

Grafos aleatórios são amplamente utilizados nos métodos probabilísticos, onde se tenta provar a existência de grafos com certas propriedades. A existência de uma propriedade num grafo aleatório muitas vezes pode implicar, através do lema famoso regularidade de Szemerédi, a existência de que a propriedade em quase todos os grafos.

Nos grafos aleatórios regulares, G (n, r-reg) são o conjunto de grafos de r-regular com r=r(n) tal que n e m são números naturais, 3 ≤ r <n, e rn = 2m, é mesmo.

Os graus de sequência de um grafo G em Gn dependem apenas do número de arestas de conjuntos $V_{n}^{(2)}=\left\{ij\ :\ 1\leq j\leq n,i\neq j\right\}\subset V^{(2)},\qquad i=1,\cdots ,n.$.

Se as arestas, M num grafo aleatório, GM é suficientemente grande para garantir que quase todos os GM têm um grau mínimo de pelo menos 1, em seguida, quase todos os GM estão ligados e, se n é o mesmo, quase todos os GM têm uma correspondência perfeita. Em particular, o momento em que o último vértice isolado desaparece, em quase todos os de grafos aleatórios, o grafo fica ligado.

Quase todos os processos de grafo com um número par de vértices com a aresta aumentando o grau mínimo de 1 ou um grafo aleatório com um pouco mais de (n/4)log(n) e arestas com probabilidades perto de 1 garante que o grafo tem uma completa correspondência, com exceção de no máximo um vértice.

Por alguma constante c, quase todos os grafo rotulados com n vértices e pelo menos cnlog(n) arestas é Hamiltonian. Com a probabilidade tendendo para 1, em particular a aresta que aumenta o grau mínimo de 2 torna-o grafo Hamiltonian.

Vértices

O grau de um vértice em um grafo é o número de arestas que incidem no vértice. Esse número é igual ao grau de entrada do vértice e também ao grau de saída do vértice. A soma dos graus de todos os vértices de um grafo vale 2E, sendo E o número de arestas. O grau médio do grafo é o número 2E/V, sendo V o número de vértices. Um vértice é isolado se o seu grau é nulo.

Número máximo de arestas

Um grafo é completo se todo par não ordenado de vértices distintos é uma aresta. Um grafo completo com V vértices tem exatamente V (V – 1) / 2 arestas.

Coloração de Grafos Aleatórios

Dado um grafo aleatório G de ordem n, com o vértice V(G)= {1, ..., n}, pelo algoritmo greedy do número de cores, os vértices podem ser coloridos com cores 1, 2, ... (vértice 1 é colorido com 1, vértice 2 é colorido com 1, se não é adjacente ao vértice 1, caso contrário, é colorido com 2, etc.)

Árvores Aleatórias

Uma árvore aleatória é uma árvore ou arborescência que é formada por um processo estocástico. Numa grande variedade de grafos aleatórios de ordem n e o tamanho M(n) a distribuição do número de componentes da árvore de ordem k é assintoticamente de Poisson. Tipos de árvores aleatórias incluem árvore uniforme spanning, árvore aleatória spanning mínima, árvore binária aleatória, treap, explorando rapidamente a árvore aleatória, árvore de Brownian, e floresta aleatória.

Gerador de grafos aleatórios

A primeira função gera grafos aleatórios com exatamente E arestas.

Graph GRAPHrand1 (int V, int E) {
   Graph G = GRAPHinit(V);
   while (G->A < 2*E) {
      Vertex v = randV(G);
      Vertex w = randV(G);
      GRAPHinsertE(G, v, w);
   }
   return G;
}

A função acima gera grafo aleatório com vértices 0..V-1 e exatamente E arestas. A função GRAPHrand1 só deve ser invocada com E bem menor que V * (V – 1) / 2. À medida que E se aproxima desse limite, a execução da função consumirá cada vez mais tempo.

A função abaixo devolve um vértice aleatório do grafo G.

Vertex randV(Graph G) {
   return G->V * (rand()/(RAND_MAX + 1.0));
}

O código pode ser substituído para G->V <= RAND_MAX+1.

Modelo Barabási-Albert

O modelo Barabási-Albert modelo é um algoritmo para gerar aleatórios redes de escala livre, utilizando um mecanismo de fixação preferencial. Redes de escala livre são amplamente observadas em sistemas naturais e artificiais, incluindo a Internet, redes de citação, e em algumas redes sociais.

Modelo Erdõs-Rényi

Na teoria dos grafos, o modelo de Erdös-Rényi é um dos dois modelos estreitamente relacionados para a geração de grafos aleatórios, incluindo um que define uma aresta entre cada par de nós com igual probabilidade, independentemente das outras arestas. Eles são nomeados para Paul Erdos e Rényi Alfred, que primeiro introduziu um dos dois modelos em 1959, o outro modelo foi introduzido de forma independente e contemporaneamente por Edgar Gilbert. Estes modelos podem ser utilizados no método probabilístico para demonstrar a existência de grafos que satisfazem propriedades de vários, ou para proporcionar uma definição rigorosa do que significa para uma propriedade de manter a quase todos os grafos.

Para gerar um modelo de Erdös-Rényi dois parâmetros devem ser especificados: o número de nós no gráfico gerado como e a probabilidade de que um link deve ser formado entre dois nós como p. A constante <k> pode derivada a partir destes dois componentes com a fórmula <k>=2E/N=p(N-1).