Mezcla de tokens en un gráfico usando intercambios locales

Deje ser un gráfico conectado no regular cuyo grado está acotado. Supongamos que cada nodo contiene un token único. $G= (V, E)$

¿Quiero barajar uniformemente los tokens entre el gráfico usando solo intercambios locales (es decir, el intercambio de tokens entre dos nodos adyacentes)? ¿Existe un límite inferior conocido para este problema?

La única idea que tenía es usar un resultado de caminata aleatoria, para ver cuántos intercambios necesito para "simular" el efecto de caminatas aleatorias que transportan fichas en el gráfico.

ds.algorithms random-walks dc.distributed-comp Sylvain Peyronnet
fuente

¿Qué tipo de límite inferior estás buscando? Número total de permutas? ¿Número de rondas paralelas (es decir, en 1 paso puede intercambiar a lo largo de todos los bordes de una coincidencia en )? Límite inferior en función de, ? ¿Todos los nodos conocen la topología de (y pueden adaptar su comportamiento en consecuencia) o está buscando una estrategia fija que pueda aplicar en cualquier gráfico?

G

$G$

| V |

$|V|$

d i a m (G)

$diam(G)$

G

$G$

Jukka Suomela

Debería haber sido más específico, lo siento. El objetivo es diseñar un método de difusión de datos para redes de sensores que eviten problemas de métodos basados en caminatas aleatorias (esencialmente pérdida de información debido a que varias fichas chocan en el mismo nodo). Por lo tanto, estoy interesado en la cantidad total de intercambios (esto dará la cantidad de mensajes que circulan en la red) y la cantidad de rondas (para tener una estimación aproximada del tiempo de convergencia). un LB en función de está bien y los nodos no son conscientes de la topología (desafortunadamente).

V

$V$

Sylvain Peyronnet

Respuestas:

Supongamos que su gráfico es un camino. Creo que este problema se vuelve equivalente a ordenar una secuencia aleatoria de números en una matriz intercambiando entradas adyacentes. Incluso de todos los nodos son conscientes de la topología, obtienes un límite inferior ^ 2 en el número de intercambios (no se puede hacer mejor que el tipo de burbuja que es n ^ 2 incluso en una entrada aleatoria).

Lev Reyzin
fuente

En el caso de una ruta, el proceso de intercambio con probabilidad 1/2 mezclas en , esto ha sido probado por Benjamini, Berger y Hoffman (esto fue conjeturado por Diaconis y Ram). Así que mi LB es también una función del grado supongo ...

O (n^{2})

$O(n^2)$

Sylvain Peyronnet

Este LB dice que no puede mejorar el algoritmo incluso si puede elegir sus intercambios ... pero, claro, supongo que el problema podría ser más fácil a medida que aumenta el grado (¿promedio?).

Lev Reyzin

Programaré algunas simulaciones para ver cómo van las cosas cuando el grado está creciendo.

Sylvain Peyronnet

En realidad, parece que este LB (con alguna modificación) se mantendrá incluso si los dos extremos de la ruta tienen grandes camarillas, como en 2 camarillas en n / 4 conectadas por una ruta de n / 2 nodos. Ahora el grado promedio es O (n), pero aún no puedes vencer a n ^ 2. ¿Quizás necesitamos imponer un grado mínimo?

Lev Reyzin

Sí, necesitamos un grado mínimo :(

Sylvain Peyronnet

Me gustaría señalar la relación entre este problema y las redes de clasificación. Por ejemplo, si su gráfico es una ruta, la red trivial de clasificación de profundidad lineal también muestra que puede obtener cualquier permutación en un número lineal de rondas. Además, esto es estricto, ya que simplemente intercambiar los elementos en los puntos finales de la ruta requiere un número lineal de rondas.

Las redes de clasificación de AKS muestran que hay gráficos en los que puede obtener cualquier permutación en el número logarítmico de rondas. Para el caso de los gráficos de cuadrícula, consulte, por ejemplo, estas notas de clase .

(Por supuesto, ordenar y barajar son problemas diferentes, pero muchos límites superiores e inferiores están relacionados. Por ejemplo, elija etiquetas aleatorias y ordene por etiquetas).

Jukka Suomela
fuente

Gracias por la anotación. Cavaré en esta dirección, tal vez no sea lo que necesito aquí (no estoy seguro de tener el buen tipo de gráfico), ¡pero ciertamente será algo que usaré tarde o temprano!

Sylvain Peyronnet