Gráficos naturales que no están libres de escala.

8

Ahora es una observación bien conocida que muchas estructuras gráficas que surgen en entornos naturales tienden a obedecer propiedades libres de escala, como la ley de poder de la distribución de grados.

¿Hay algún buen ejemplo de gráficos naturales que sean bastante aleatorios y que no obedezcan necesariamente a propiedades libres de escala?

Arnab
fuente

Respuestas:

7

La topología de red de las redes inalámbricas ad hoc y las redes inalámbricas de sensores a menudo se capturan mediante un gráfico geométrico aleatorio. Esto significa, elegir puntos aleatorios en un dominio plano y conectar cualquiera de los dos que están dentro de un cierto umbral de distancia. Estas gráficas tienen distribuciones de grados de Poisson, a pesar de que son bastante diferentes de las gráficas aleatorias de Erdos-Renyi, y surgen naturalmente como un modelo de red.

Andras Farago
fuente
3

Aunque no estoy seguro de lo que quiere decir con "aleatorio", los gráficos obvios naturales sin escala son las redes de carreteras.

Snowie
fuente
Bueno, al azar en el sentido de que los vértices vendrían al azar y se unirían a otros siguiendo alguna distribución de probabilidad (posiblemente oculta).
Arnab
66
En realidad, las redes de carreteras no tienen escala, cuando se ven de manera adecuada. Obviamente, la representación natural no lo es, ya que la mayoría de las intersecciones tienen un grado máximo de 4 o, a veces, 5 o rara vez 6. Pero si toma la representación dual, un nodo para cada carretera, y el borde entre ellas si las carreteras alguna vez se encuentran, se obtiene una red sin escala: cs.unm.edu/~treport/tr/05-10/RoadNetworks.pdf .
Joshua Grochow