Gráficos naturais que não são livres de escala

8

É agora uma observação bem conhecida que muitas estruturas gráficas que surgem em ambientes naturais tendem a obedecer a propriedades sem escala, como a lei de potência da distribuição de graus.

Existe algum bom exemplo de gráficos naturais bastante aleatórios e que não necessariamente obedeçam às propriedades sem escala?

Arnab
fonte

Respostas:

7

A topologia de rede de redes sem fio ad hoc e redes de sensores sem fio é frequentemente capturada por um gráfico geométrico aleatório. Isso significa escolher pontos aleatórios em um domínio plano e conectar dois que estejam dentro de um determinado limite de distância. Esses gráficos têm distribuições de graus de Poisson, embora sejam bastante diferentes dos gráficos aleatórios Erdos-Renyi, e surgem naturalmente como um modelo de rede.

Andras Farago
fonte
3

Embora eu não tenha certeza do que você quer dizer com "aleatório", gráficos naturais óbvios e sem escala são as redes rodoviárias.

Snowie
fonte
Bem, aleatório no sentido de que os vértices viriam aleatoriamente e se ligariam a outros após alguma distribuição de probabilidade (possivelmente oculta).
Arnab
6
Na verdade, as redes rodoviárias são livres de escala, quando visualizadas adequadamente. Obviamente, a representação natural não é, já que a maioria das interseções tem grau no máximo 4 ou às vezes 5 ou raramente 6. Mas se você pegar a representação dupla - um nó para cada estrada, e passar uma margem entre elas se as estradas se encontrarem - você obtém uma rede sem escala: cs.unm.edu/~treport/tr/05-10/RoadNetworks.pdf .
Joshua Grochow 6/12/12