¿Desequilibrio máximo en un gráfico?

Deje $G$ un grafo conectado $G = (V,E)$ con nodos $V = 1 \dots n$ y los bordes $E$ . Deje $w_i$ denota el peso (número entero) de la gráfica $G$ , con $\sum_i w_i = m$ el peso total en el gráfico. El peso promedio por nodo es $\bar w = m/n$ . Sea $e_i = w_i - \bar w$ denote la desviación del nodo $i$ de la media. Llamamos $|e_i|$ Eldesequilibriodel nodo $i$ .

Suponga que el peso entre dos nodos adyacentes puede diferir como máximo en $1$ , es decir,

w_{i} - w_{j} \leq 1 \forall (i, j) \in E .

$w_i - w_j \le 1\; \forall (i,j) \in E.$

Pregunta : ¿Cuál es el mayor desequilibrio posible que puede tener la red, en términos de y ? Para ser más precisos, imagine el vector . Estaría igualmente contento con los resultados relativos a o . $n$ $m$ $\vec{e} = (e_1, \dots, e_n)$ $||\vec{e}||_1$ $||\vec{e}||_2$

Para , se puede encontrar un límite simple en términos del diámetro del gráfico: dado que todo debe sumar a cero, si hay un gran positivo , en algún lugar debe haber un negativo . De ahí su diferencia es al menos , pero esta diferencia puede ser como máximo la distancia más corta entre los nodos y , que a su vez puede ser como máximo el diámetro del gráfico. $||\vec{e}||_\infty$ $e_i$ $e_i$ $e_j$ $|e_i - e_j|$ $|e_i|$ $i$ $j$

Estoy interesado en límites más fuertes, preferiblemente para la forma o . Supongo que debería involucrar cierta teoría del gráfico espectral para reflejar la conectividad del gráfico. Traté de expresarlo como un problema de flujo máximo, sin éxito. $1$ $2$

EDITAR: Más explicación. Estoy interesado en la forma o ya que reflejan con mayor precisión el desequilibrio total. Se obtendría una relación trivial de $1$ $2$ y $||\vec{e}||_1 \leq n|||\vec{e}||_\infty$ . Sin embargo, espero que debido a la conexión del gráfico y mi restricción en la diferencia de cargas entre los nodos adyacentes, que lasnormas y sean mucho más pequeñas. $||\vec{e}||_2 \leq \sqrt{n}||\vec{e}||_\infty$ $1$ $2$

Ejemplo: hipercubo de dimensión d, con . Tiene diámetro . El desequilibrio máximo es, como máximo, . Esto sugiere como límite superior para el norm , donde incrusto un ciclo en el hipercubo y hago que los nodos tengan desequilibrios $n = 2^d$ $d = \log_2(n)$ $d$ $1$ . Hasta ahora, no he podido construir una situación en la que esto realmente se obtenga, lo mejor que puedo hacer es algo similar a $nd = n\log_2(n)$ $||\vec{e}||_1 = n/2$ , , , etc. Entonces, aquí el límite está desactivado por un factor de , que considero demasiado, ya que Estoy buscando (asintóticamente) límites estrechos. $0$ $1$ $0$ $-1$ $\log(n)$

graph-theory co.combinatorics spectral-graph-theory Lagerbaer
fuente

interesante pregunta. ¿hay alguna aplicación en particular?

Suresh Venkat

@ András Salamon: Gracias por la edición. @Suresh Venkat: Suponga que los pesos representan la cantidad de agentes de tamaño uniforme que desean minimizar su carga experimentada. Querrán pasar de

. Si nadie quiere moverse, lo llamamos equilibrio de Nash. Pregunta: ¿Cuál es el mayor desequilibrio total que podríamos tener en un equilibrio de Nash?

i

$i$

j

$j$

w_{i} > w_{i}

$w_i > w_i$

Lagerbaer

¿Tiene un ejemplo de un gráfico en el que su diámetro simple es demasiado flojo?

mhum

Bueno, puedo trivialmente atar las otras dos normas usando

. Estoy interesado en la forma

ya que capturan con mayor precisión el desequilibrio "total". He agregado un ejemplo a mi pregunta.

| | \vec{e} | |_{1} \leq n | | \vec{e} | |_{\infty}

$||\vec{e}||_1 \leq n||\vec{e}||_\infty$

1

$1$

2

$2$

Lagerbaer

Para el hipercubo, ¿qué pasa si sopesamos los vértices por su peso de Hamming? Me sale algo como

para el

, y creo que el

será de orden

\sqrt{d (n - 2)} / 2

$\sqrt{d(n - 2)}/2$

l_{2}

$l_2$

l_{1}

$l_1$

n d

$nd$

Artem Kaznatcheev

Respuestas:

Desde está limitado por el diámetro , la norma va a estar trivialmente limitada por , del mismo modo para la norma , excepto por $|e_i|$ $d$ $\ell_1$ $nd$ $\ell_2$ (de hecho, lanormaestá limitada por). $\sqrt{n}d$ $\ell_p$ $n^{1/p}d$

El caso resulta ser sorprendentemente fácil de analizar. $\ell_1$

Para una ruta, es fácil ver que es $\|\vec e\|_1$ $O(n^2)$ , por lo que no puede hacer nada mejor que . $O(nd)$

Para una completa árbol ary, se puede dividir por la mitad en la raíz, el establecimiento de , ascendente y descendente de un lado al otro hasta que las hojas tienen , produciendo $k$ $w_{\text{root}} = 0$ $|e_i| = |w_i| = \log_k n$ nuevamente. $O(n\log_k n) = O(nd)$

Para una camarilla, realmente no importa cómo distribuya los pesos, ya que todos estarán dentro de uno del otro, y eso producirá nuevamente. $1$ $O(n) = O(nd)$

Cuando te das cuenta de que de lo que estamos hablando aquí es de una función , y luego tomamos su norma , siempre que puedas distribuir pesos arbitrariamente uniformemente en todo el rango, el límite será . $e : \mathbb{Z} \to [-d/2,d/2] \subset \mathbb{R}$ $\ell_1$ $e_i \in [-d/2,d/2]$ $O(nd)$

La única forma de cambiar esto es jugar juegos con la masa. Por ejemplo, si tiene varias camarillas gigantes en puntos que están necesariamente equilibradas, como una camarilla gigante con dos caminos de igual longitud que sobresalen, entonces puede contar con un límite de solo (por ejemplo) . $O(d^2)$

Esto también puede ser cierto para los expansores, pero no estoy seguro. Me imagino un caso donde pones en un gráfico regular y luego deje que los valores aumenten posteriormente de cada salto. Parece probable que la media pueda tener la mayor masa, pero no sé si sería suficiente para afectar el límite. $w_1 = 0$

Creo que podrías razonar de manera similar sobre . $\ell_2$

EDITAR:

En los comentarios descubrimos un límite (suelto) de $\ell_2$ $O(|E|/\lambda_2(L))$ usando las restricciones del problema y algo de teoría básica de grafos espectrales.

Josephine Moeller
fuente

Me gusta tu respuesta. Sin embargo, tengo un problema con " siempre que pueda distribuir arbitrariamente los pesos de manera uniforme en todo el rango ". ¿No podría imaginar una situación en la que el límite de diámetro me permitiera colocar un peso

algún lugar, pero la estructura del gráfico es tal que no puedo compensar este gran peso positivo? Entonces, si bien

es, por supuesto, un límite superior, ¿sería posible obtener límites más estrechos? ¿Finalmente usando el segundo valor propio de Laplacian más pequeño o el segundo valor propio de adyacencia más grande (ya que codifican la información de conectividad)?

e_{i} = d / 2

$e_i = d/2$

O (n d)

$\mathcal{O}(nd)$

Lagerbaer

Bueno, no estás colocando

, estás colocando

. Por lo tanto, si tiene un

sesgado , debe haber una gran cantidad de pesos pequeños que lo compensen en el otro lado de la media, o algún otro peso grande diametralmente opuesto a él. La única forma de obtener un límite más pequeño que

es contar con la estructura de alguna manera. Y como dije, no estoy seguro de lo que esto significaría para, por ejemplo, un expansor. No creo que pueda hacerlo basándose únicamente en la conductancia, debido a los casos que expuse en mi respuesta.

e_{i}

$e_i$

w_{i}

$w_i$

e_{i}

$e_i$

O (n d)

$O(nd)$

Josephine Moeller

Déjame ofrecerte otro ejemplo. Un gráfico de dumbell con dos camarillas tiene una conductancia muy baja, pero su desequilibrio está limitado por 2.

Josephine Moeller

Un límite relacionado con la estructura sería algo con lo que estaría perfectamente feliz. Es por eso que mencioné los valores propios, ya que se relacionan con las propiedades de conexión. Existen, por ejemplo, límites en el diámetro, la trayectoria media, el número isoperimétrico, etc. en términos del segundo vector propio más pequeño de la matriz laplaciana del gráfico.

Lagerbaer

Lee tu otro ejemplo justo ahora. Supongo que un gráfico de este tipo también tendría un valor propio de Laplacian muy pequeño, el segundo más pequeño, ya que el número isoperimétrico sería de alrededor de

2 / n

$2/n$

Lagerbaer

Para los gráficos conectados, el desequilibrio es superior limitado por el diámetro del gráfico. Para atar el desequilibrio , podemos reescribir cada como donde $|w_i - 1/n\sum_k w_k|$ $w_k$ $w_k - v_1 + v_1 - v_2 + v_2 - ... - v_k + v_k - w_i + w_i$ es el camino más corto de a . Defina . Podemos escribir $w_k, v_1,...,v_k, w_i$ $w_i$ $w_k$ $w_{ki} = w_k - v_1 + v_1 - v_2 + v_2 - ... - v_k + v_k - w_i$

| w_{i} - 1 / n \sum_{k} w_{k} | = | w_{i} - 1 / n \sum_{k} (w_{k i} + w_{i}) | = | \sum_{k \neq i} \frac{w_{k i}}{n} |

$|w_i - 1/n\sum_k w_k| = |w_i - 1/n\sum_k (w_{ki} + w_i)| = |\sum_{k\neq i} \frac{w_{ki}}{n}|$

Cada está delimitada superior por la longitud de la trayectoria más corta desde a por su suposición de que para cada . Por lo tanto, obtenemos el límite trivial: $w_{ki}$ $i$ $k$ $w_i - w_j \leq 1$ $i,j\in E$

| w_{i} - 1 / n \sum_{k} w_{k} | \leq \frac{(n - 1)}{n} D

$|w_i - 1/n\sum_k w_k| \leq \frac{(n-1)}{n} D$

Esto podría no estar muy lejos de ser óptimo. Estoy pensando en una completa árbol ary donde los nodos en cada nivel tienen un peso mayor que el peso del nivel anterior. Una gran fracción del gráfico tiene el mayor peso, . Entonces, el promedio debe estar sesgado hacia la cima. Como y se hacen más grandes, espero para obtener más y más a que significa que el desequilibrio debe recibir más y más a . $k$ $D+1$ $k$ $n$ $m$ $D+1$ $D$

Nicholas Ruozzi
fuente

Hasta donde puedo decir, la construcción esbozada aquí puede hacerse rigurosa, para lograr un desequilibrio tan cercano a

como se desee. Sin embargo, dado que la pregunta no especifica qué sucede cuando los vértices no son adyacentes, una construcción más fácil es un gráfico completamente desconectado con vértice

con peso

y todos los demás vértices con peso

. Esto tiene un peso promedio

que también es su desequilibrio máximo. Esto claramente se puede hacer arbitrariamente cerca de

eligiendo un

suficientemente grande , y

D < \infty

$D<\infty$

0

$0$

0

$0$

k

$k$

k (n - 1) / n

$k(n-1)/n$

k

$k$

n

$n$

k

$k$ puede hacerse tan grande como se desee.

András Salamon

@ András Salamon: Buen punto. La respuesta anterior supone que el gráfico

dado está conectado. Lo editaré para que quede claro.

G

$G$

Nicholas Ruozzi

He agregado la restricción "conectado" a mi pregunta, ya que esto era lo que tenía en mente. La respuesta aquí presenta un límite en

. Además, cuando pregunté por el "peor" caso, tuve en cuenta que el gráfico sería reparado, y trataría de encontrar el peor caso para ese gráfico en particular.

| | \vec{e} | |_{\infty}

$||\vec{e}||_\infty$

Lagerbaer