É 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?
As conexões entre neurônios não formam redes sem escala, eu acho. Veja, por exemplo, a Figura 1 na p.181 de http://www.indiana.edu/~cortex/Koetter_chapter_modified.pdf e observe que os graus dos vértices abrangem apenas uma única ordem de magnitude.
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.
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.