Comprender e interpretar los espectros gráficos

Question

Yo no soy un matemático, pero un geógrafo tratando de tener una idea de algunos de análisis de red, estoy experimentando con el. Tengo un par de preguntas relacionadas con el gráfico espectral teoría de que un matemático me podría ayudar con:

Soy de la generación de grafos aleatorios de 50 nodos y la densidad 0.17 que han determinado el promedio de la longitud de la ruta, la modularidad, etc. Cada uno de estos gráficos producir espectros (distribución de autovalor) se asemeja a esto:

A partir de un inexperto punto de vista, estoy tentado a decir que una forma de semicírculo, si es débil, se está formando entre los autovalores de 0.6 y 1.55.

• Qué significaría eso? Es esta relacionado con el típico semi-círculo visto en grafos aleatorios?
• ¿Qué acerca de la cima al autovalor 0.4? Podría ser el segundo autovalor, que a menudo está relacionada con algebraica de conectividad?
• Son los valores cercanos a cero típico de nada?

Para ampliar la pregunta, ¿cuánto se puede concluir, en términos de estructura de grafo, de mirar el espectro de un gráfico (laplaciano o de otro tipo)? Esto puede parecer ingenuo, pero se puede utilizar nunca un gráfico de espectros (tal vez promediada a lo largo de muchos gráficos) como estructurales de la firma?

Answer 1

Se sabe que el espectro de grafos aleatorios obedece a una semicircular de la ley. Ya que sus gráficos son aleatorios, sus observaciones no parecen sorprendentes. La forma de la autovalor función de densidad está controlado en gran parte por el número de cerrado paseos en el gráfico con una longitud de $k$, para valores pequeños de a $k$. Esto significa que las parcelas como la suya a exponer la información acerca de estos paseos, que brinda información sobre el promedio de valencia, la media de huber de triángulos en un vértice, y así sucesivamente. En general, el espectro no determina la gráfica. Por ejemplo, la probabilidad de que un árbol en $n$ vértices está determinado por su espectro va de cero $n\to\infty$. Se cree que la probabilidad de que un azar del gráfico se determina por su espectro va a 1 como el número de vértices aumenta.