Gráficos con fractal propiedades?

Question

Para los fines de un proyecto de investigación, me pregunto si hay recursos en los gráficos con fractal propiedades, por lo que significa la auto-similitud en particular. Por ejemplo, imagine que un grafo donde los nodos se podría transformarse en subdiagramas que eran los mismos que el gráfico de mayor tamaño, y sus nodos podría ser transformado asimismo, etc. No me refiero a un gráfico que es, literalmente, exactamente igual que - pero debe de tener la auto-similitud en los diferentes niveles como si hubiera sido creado de esa manera, tal vez con un poco de aleatoriedad tirado después.

Me dijeron que los gráficos de expansión eran algo así como lo que yo estaba buscando, pero de lo poco que entiendo de su definición, parecen más relacionadas con el mundo de la teoría de que lo que estoy buscando.

Edit: estoy, porque estoy tratando de ot encontrar una manera en la que las representaciones de lo social y geográfica de las redes de personas que podrían estar comprimidos, probablemente con la pérdida significativa, pero manteniendo las propiedades básicas.

Answer 1

Su idea de la transformación de los nodos en conjuntos de nodos que se parece mucho a la gráfica de gramáticas - ver, por ejemplo, este artículo de la Wikipedia.

Answer 2

Usted podría estar interesado en un objeto llamado el Azar Gráfico http://en.wikipedia.org/wiki/Rado_graph, que "es el único (hasta el isomorfismo) contables gráfico de R tal que para cualquier finito grafo G y cualquier vértice v de G, cualquier incrustación de G − v como un subgrafo inducido de R puede ser extendida a una incrustación de G en R. Como resultado, el Rado gráfico contiene todos finito y countably infinito gráficos como la inducida subdiagramas."

Actualmente hay una muy buena discusión sobre la n-categoría de café en conexión con Fraisse límites de un modelo teórico de acercamiento a la construcción de tales objetos): http://golem.ph.utexas.edu/category/2009/11/fraisse_limits.html#more

Answer 3

Bueno, por lo de Steven derecho -- hay una (countably infinito) gráfico que es totalmente auto-similar, llamado el Rado gráfico. Es auto-similar de la siguiente manera: Si la partición de su vértice establece en dos (o en general de un número finito de partes, y considerar el subgrafo inducido en cada una de esas partes, uno de los subdiagramas va a ser isomorfo a todo el gráfico.

Hay otros dos gráficos con esta propiedad: el grafo completo en countably infinitamente muchos vértices, y el vacío de la gráfica en la countably muchos vértices. Hasta el isomorfismo, estos son los únicos contables de tales gráficos. (o por lo Diestel me dice, y la prueba de realidad no es tan difícil.)

Si usted está buscando formas más débiles de la auto-similitud... no estoy seguro de qué es exactamente lo que usted desea, entonces. De decir algo sobre "la transformación de los nodos en subdiagramas que son los mismos que el gráfico de mayor tamaño," pero no hay ninguna razón usted no puede hacer algo así, con un genérico gráfico. Hay una noción de gráfico de producto a lo largo de estas líneas, donde se reemplaza los vértices de una gráfica copias de otro gráfico y, a continuación, conecte los nuevos gráficos de acuerdo a la antigua. De manera que a partir de un grafo G, seguramente se podría construir $G \cdot G$, e $G \cdot G \cdot G$, y así sucesivamente y así sucesivamente... pero no sé si esta secuencia tiene un límite (o incluso en qué categoría que tendría sentido -- presumiblemente la categoría de gráficos e incrustaciones, pero...)

Si desea que "se ve de la misma a determinados gráfico invariantes", a continuación, los gráficos de expansión son bien vale la pena mirar.

Answer 4

Así, las redes sociales, en particular, tienen algunas propiedades diferentes de genéricos gráficos. En particular, tienden a ser libre de escala, que un azar del gráfico (en el modelo habitual) probablemente no lo es.

Libre de escala de los gráficos ¿ tienen algún tipo de auto-similitud, y me gustaría recomendar la lectura de la literatura sobre ellos. No sé la parte superior de mi cabeza, aunque, si la escala libertad es suficiente para dar una buena (probablemente con pérdida) algoritmo de compresión -- es de suponer que usted sabe, por supuesto, que en general no se puede almacenar una gráfica con menos de O(n^2) bits. (Algunos de origen natural de redes también son escasos, a pesar de, que significa que usted puede hacer asintóticamente mejor, con una incidencia de la lista.)

Answer 5

En ciencias de la computación, una manera de proporcionar una semántica de los programas es mediante el uso de infinito árboles modelo de los bucles en las finito de flujo gráficos. Dana Scott y Marshall Hall son los primeros que recuerdo. Arbib y Melenas más tarde.

Una gran cantidad de nudo de la teoría pueden ser abordados por una posición semejante.

Anexos

Para una introducción a la asintótica de la enumeración y grafos aleatorios (mencionado varias veces más adelante), vea:

• Edgar M. Palmer (1985), la Gráfica de la Evolución : Una Introducción a la Teoría de Grafos Aleatorios, John Wiley and Sons, Nueva York, NY. http://portal.acm.org/citation.cfm?id=4050

Para uno de los inaugural de las aplicaciones de la teoría de grafos a las redes sociales, ver:

• Frank Harary, Robert Z. Norman, y Dorwin Cartwright (1965), los Modelos Estructurales : Una Introducción a la Teoría de Gráficos, Wiley, Nueva York, NY. http://www.ams.org/featurecolumn/archive/networks7.html

Para aplicaciones a la geografía, no hay en este eBook:

• Arlinghaus, Sandra L.; Arlinghaus, William C.; Harary, Frank (2002), la Teoría de grafos y la Geografía : Una Visión Interactiva, Wiley, Nueva York, NY. http://deepblue.lib.umich.edu/handle/2027.42/58623

Para recursiva y auto-gráficos similares en el nudo de la teoría, un buen trampolín es:

• Louis H. Kauffman página de inicio : http://www.math.uic.edu/~kauffman/