Modelos de gráficos aleatorios, para redes informáticas reales.

19

Estoy interesado en modelos de gráficos aleatorios que son similares a los gráficos de redes informáticas reales. No estoy seguro de si el modelo común bien estudiado ( vértices, cada borde posible se selecciona con probabilidad ) es bueno para estudiar redes informáticas reales (¿verdad?).sol(norte,pag)nortepag

¿Qué modelos de gráficos aleatorios son útiles para comprender las redes informáticas que surgen en la práctica?

En términos más generales, ¿qué otros modelos de gráficos aleatorios finitos (distintos de los equivalentes al modelo ) se han estudiado en la literatura? (Una respuesta ideal sería un puntero a una encuesta para modelos estudiados de gráficos aleatorios finitos).sol(norte,pag)

Kaveh
fuente
2
¿Dónde necesita esos modelos? ¿Es solo para generar algunas entradas de prueba para algoritmos, o desea analizar los modelos para aprender algo sobre las redes de computadoras? En qué tipo de redes informáticas está interesado; ¿Cuál es su escala (LAN vs. internet)? ¿Por qué supone que las redes informáticas reales son generadas por un proceso aleatorio ? Sorprendentemente, las redes del mundo real en realidad están diseñadas por un ingeniero, con bastante poco lanzamiento de monedas.
Jukka Suomela
@ Jukka, estoy tratando de ver si puedo aplicar las técnicas desarrolladas para a esos modelos aleatorios para obtener información sobre las redes reales, no me gusta ser más específico en este momento porque podría dar lejos el problema en el que estoy pensando :). Estoy principalmente interesado en la capa de IP de Internet. He visto a personas usar gráficos aleatorios para analizar los gráficos que surgen de las redes sociales. No estoy seguro de por qué estas redes reales comparten propiedades con gráficos aleatorios, podría haber un proceso aleatorio oculto detrás de la superficie en el trabajo (parece una pregunta interesante que hacer :). sol(norte,pag)
Kaveh
Supongo que parte del interés en usar los modelos aleatorios es que analizarlos es más fácil que analizar redes reales, por lo que es razonable considerarlos si son una aproximación suficientemente buena a la real.
Kaveh
Gracias a todos por buenas respuestas. (Ahora tengo que pasar algún tiempo leyendo estos documentos. :)
Kaveh

Respuestas:

10

En los últimos años, el estudio de gráficos aleatorios con restricciones estructurales "naturales" ha ganado fuerza. Por ejemplo, uno puede considerar una gráfica plana dibujada de la clase de todas las gráficas planas con vértices y estudiar cómo se comporta como . A diferencia de los gráficos aleatorios de Erdős-Rényi u otros modelos similares, los bordes en estos gráficos son altamente dependientes, por lo que una de las pseudo motivaciones para estudiar tales distribuciones es analizar modelos de red con independencia muy limitada entre los bordes.n nortenorte

Sin embargo, tal vez en la actualidad este objetivo parece bastante lejano ya que la independencia limitada hace que sea mucho más difícil analizar las propiedades de tales gráficos. De hecho, varias preguntas básicas que se responden muy fácilmente para , como la distribución de la secuencia de grados, solo se han resuelto recientemente para gráficos planos aleatorios.sol(norte,pag)

Para una referencia definitiva, vea los documentos de Konstantinos Panagiotou y las citas contenidas en ellos. Por conveniencia, aquí hay una pequeña muestra de algunos documentos relevantes:

  • Sobre la distribución de grados de gráficos planos aleatorios . Konstantinos Panagiotou y Angelika Steger . Para aparecer en las Actas del 22º Simposio Anual ACM-SIAM sobre Algoritmos Discretos (SODA '11).
  • Sobre las propiedades de disecciones aleatorias y triangulaciones . Nicla Bernasconi, Konstantinos Panagiotou y Angelika Steger . En Actas del XIX Simposio anual ACM-SIAM sobre Algoritmos discretos (SODA '08), p. 132-141. [http://www.mpi-inf.mpg.de/~kpanagio/Dissections.pdf]
  • Sobre las secuencias de grados de los gráficos aleatorios de plano exterior y de serie en paralelo . Nicla Bernasconi, Konstantinos Panagiotou y Angelika Steger . En Actas del 12º Taller Internacional sobre Técnicas Aleatorias en Computación (RANDOM'08), p. 303-316. [http://www.mpi-inf.mpg.de/~kpanagio/OPSP.pdf]
Max
fuente
1
Un comentario adicional: esta línea de investigación en realidad se remonta a unos 15 años, al menos a un artículo de Denise, Vasconcellos y Welsh (1996), y una de las razones por las que ha "ganado tracción" ahora es el gran éxito de la aplicación de La combinatoria analítica y la enumeración asintótica aquí, por ejemplo, por Giménez y Noy (2009).
RJK
10

Esta encuesta, La estructura y función de redes complejas de Newman, revisa técnicas y modelos para redes complejas reales, incluidos conceptos tales como efecto de mundo pequeño, distribuciones de grados y modelos de gráficos aleatorios. Además, el mismo autor tiene un buen artículo, Gráficos aleatorios como modelos de redes , sobre adaptaciones de gráficos aleatorios para modelar redes reales.

Referencias

1) Gráficos aleatorios como modelos de redes, MEJ Newman, en Handbook of Graphs and Networks, S. Bornholdt y HG Schuster (eds.), Wiley-VCH, Berlín (2003)

2) La estructura y función de redes complejas, MEJ Newman, SIAM Review 45, 167-256 (2003)

Mohammad Al-Turkistany
fuente
1
Es curioso: ¿es esto para las redes "sociales" frente a Internet?
Suresh Venkat
Segundo: los enfoques de las redes sociales deberían ser muy útiles, dado que gran parte del estudio de estas redes se centró originalmente en las propiedades "universales" de las redes, e incluyó la topología neural, la red eléctrica y las redes de carreteras. Además, las redes Barabasi-Albert y Watts-Strogatz, cada una con propiedades que tienen las redes reales y que Erdos-renyi descuida, están muy, muy bien estudiadas
Elliot JJ
1
@Suresh, esas redes complejas cubiertas en ambas referencias incluyen redes informáticas como Internet y redes sociales.
Mohammad Al-Turkistany
8

¿Redes informáticas reales en qué capa? Internet es, en el nivel AS (posiblemente el nivel más alto), una red de mundo pequeño con algunos nodos de grado extremadamente alto. A medida que las capas se acercan a los cables reales, el gráfico se vuelve más vinculado a la geografía y menos vinculado a la capa social (social es una especie de palabra equivocada, ¿es realmente una red social cuando las entidades que son "amigos" son corporaciones multinacionales?) . En el caso extremo, un ethernet local es un árbol lógico que es (probablemente) un subgrafo del patrón físico de las conexiones de cables, y ese patrón de conexiones de cables probablemente no sea demasiados cables más que un árbol.

Las "redes informáticas reales" vienen en muchos sabores y capas. Algunos de ellos parecen redes sociales, otros no. Para obtener más información al respecto, lo remito al capítulo 2 de mi disertación: http://home.manhattan.edu/~peter.boothe/thesis.pdf

Peter Boothe
fuente
Estoy principalmente interesado en las redes físicas (por ejemplo, la capa IP). Gracias por el enlace, lo comprobaré.
Kaveh
2
La capa IP no es la capa física. MPLS y otras tecnologías de conmutación de circuitos rompen esta suposición. La capa física son los cables. ¡Incluso tenemos enlaces de varios cables que parecen ser saltos de ethernet individuales! Esta pregunta de "qué capa" es más profunda de lo que podría sugerir la primera inspección, y requiere una cuidadosa reflexión. Le sugiero que piense en las propiedades que puede desear que tenga una red, busque la capa donde el análisis de topología lo ayudará a analizar esa propiedad y espere que haya datos disponibles.
Peter Boothe
7

nortetuvβmi-re/ /(Lα)reL

Waxman, enrutamiento de conexiones multipunto , IEEE J. Select. Áreas Comun. 6 (9), 1617-1622, 1988. Zegura, Calvert, Bhattacharjee, Cómo modelar una red interna , Proc. IEEE INFOCOM '96, 1996.

Marcus Ritt
fuente
5

Walter Willinger ha desarrollado una carrera en el uso de gráficos sin escala para modelar redes. Hay mucho que citar, así que te señalaré su entrada DBLP . El punto clave en estos modelos es que tienen propiedades similares a las redes "reales" que no son capturadas por G (n, p).

Suresh Venkat
fuente
5

En lugar de buscar laboriosamente, justificar y analizar un modelo específico, es posible que desee utilizar los datos de la vida real que tiene (si tiene alguno). Eso significa definir un modelo probabilístico genérico y entrenar sus parámetros dados sus datos (por ejemplo, por estimación de máxima verosimilitud).

Spag1:(S)Spag2:εpag1,pag2

Obviamente, la gramática específica puede (y debería) usar el conocimiento del dominio. Considere, por ejemplo, diferentes gramáticas utilizadas para la predicción de la estructura secundaria de ARN en Dowell, Eddy (2004) para probar.

Encuentre algunos detalles sobre esta técnica en Weinberg, Nebel (2010) . Sin embargo, no sé cómo (bueno) se puede aplicar a los gráficos generales.

Si necesita más potencia, puede pasar a cosas como CFG multidimensional (S) (por ejemplo , Seki, Kato (2008) ) o SCFG dependiente de la longitud / posición ( Weinberg, Nebel (2010) ).

Rafael
fuente
1
esto es genial, pero ¿la naturaleza libre de contexto de SCFG obliga a su alumno a descuidar cierta estructura global que podrían tener las redes en su conjunto de capacitación?
Artem Kaznatcheev
Bueno, sí, se pierden las funciones sin contexto. Pero tenga en cuenta que se pueden capturar propiedades como los grados de nodo (promedio). Para más información, vea mi edición.
Raphael
¡Gracias! Echaré un vistazo más de cerca. ¿Los MDP ocultos también pueden capturar propiedades como el grado promedio? Eso parece algo que un lenguaje normal debería poder capturar, ¿o estoy confundido? (Además, un punto menor: el enlace Weinberg, Nebel tiene un carácter final que mata el enlace, es obvio qué enlace pretendía, pero si realiza más ediciones, podría valer la pena corregirlo).
Artem Kaznatcheev
Claro, solo quería señalar que puedes cubrir algunas características globales usando ese modelo. REG también puede cubrir algunos, pero no podrá modelar estructuras inherentemente no regulares. (gracias, arreglado)
Raphael
3

sol(norte,pag)sol(norte,metro)

Como probablemente sepa, parece haber una diferencia entre el gráfico de conectividad para la World Wide Web y el gráfico de conectividad para la infraestructura de Internet. Ciertamente no pretendo ser un experto, pero he visto el artículo de Li, Alderson, Tanaka, Doyle y Willinger "Hacia una teoría de gráficos sin escala: definición, propiedades e implicaciones" que introducen una métrica 'para medir la' escala libre 'de un gráfico (con la definición de gráficos libres de escala aún en debate hasta donde yo sé) que afirman tener un modelo de gráfico que crea gráficos similares a la conectividad a Internet en un enrutador nivel.

Aquí hay algunos modelos generativos más que podrían ser de interés:

El documento de Berger, Borgs, Chayes, D'Souza y Kleinberg "Adjunto preferencial inducido por la competencia"

Tolerancia altamente optimizada de Carlson y Doyle : un mecanismo para las leyes de potencia en sistemas diseñados

Un punto crítico de Molloy y Reed para gráficos aleatorios con una secuencia de grados dada que introduce el "Modelo de configuración borrado"

Clustering de Newman y apego preferencial en redes en crecimiento (que ya se ha mencionado)

También se podría generar explícitamente una distribución de grados y crear un gráfico de esta manera, pero no está claro para mí qué tan cerca esto modela el gráfico de Internet a nivel de enrutador.

Por supuesto, hay mucha más literatura sobre el tema y solo he dado algunos de los aspectos más destacados (lo que considero que son).

sol(norte,pag)sol(norte,metro)) no funcionan precisamente porque el grado de ley de potencia o sin escala distribuyó gráficos aleatorios que divergieron en el segundo momento en la distribución de grados. No pretendo saber lo suficiente sobre el tema para hacer afirmaciones categóricas sobre "la mayoría" de las pruebas, pero por lo que he visto, una de las primeras líneas de pruebas para propiedades en gráficos aleatorios de Erdos-Renyi asume explícitamente un finito segundo momento en la distribución de grados. Desde mi punto de vista, esto tiene sentido ya que un segundo momento finito hace que los gráficos de Erdos-Renyi sean mucho más parecidos a un árbol localmente (ver Información, física y computación de Mertens y Montanari).) que efectivamente otorga independencia a las propiedades / caminos / estructuras. Dado que los gráficos aleatorios distribuidos de grado de ley de potencia tienen un segundo momento divergente, esta estructura local en forma de árbol se destruye (y por lo tanto requiere diferentes técnicas de prueba). Me encantaría invalidar esta intuición si alguien con más conocimiento o perspicacia mostrara por qué esto no es así.

Espero que ayude.

usuario834
fuente
3

Aunque es un tema antiguo, estoy respondiendo ya que hay muchas personas que aún visitan tales publicaciones. Estoy motivado por un comentario en otra respuesta.

El modelo Barabasi-Albert y otros modelos que producen gráficos sin escala se han propuesto para modelar Internet a nivel de enrutador y a nivel de sistema autónomo. Aunque inicialmente dichos modelos se consideraron precisos, resultó que no tenemos una imagen completa de la topología de Internet debido a las dificultades para descubrir todos los enlaces. Aunque se cree que es una cola pesada, es prácticamente un trabajo en progreso.

Para su referencia, puede leer: RG Clegg, C Di Cairano-Gilfedder, S Zhou, Una mirada crítica al modelado de la ley de poder de Internet

Vasilis
fuente
2

Hay varios libros sobre gráficos aleatorios, como el Libro de Bollobás, y hay varios modelos de gráficos aleatorios como el enlace de wikipedia del mundo pequeño o el enlace de wikipedia adjunto preferencial , para modelar redes con pequeñas distancias entre computadoras o aquellas con distribución de grados siguiendo una ley de potencia. , respectivamente.

Creo que no hay una manera fácil de modelar una red informática real, pero estoy bastante seguro de que G (n, p) no la modelaría muy bien. A menos que esté trabajando con una red organizada muy específica.

dpufrj
fuente