Максимальный дисбаланс в графике?

Пусть $G$ связный граф $G = (V,E)$ с узлами $V = 1 \dots n$ и ребер $E$ . Обозначим через $w_i$ (целочисленный) вес графа $G$ , где $\sum_i w_i = m$ - общий вес графа. Средний вес каждого узла тогда $\bar w = m/n$ . Пусть $e_i = w_i - \bar w$ обозначает отклонение узла $i$ из среднего. Мы звонимдисбалансв узле . $|e_i|$ $i$

Предположим, что вес между любыми двумя соседними узлами может отличаться не более чем на $1$ , т.

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

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

Вопрос : Каков максимально возможный дисбаланс, который может иметь сеть, с точки зрения $n$ и $m$ ? Чтобы быть более точным, представьте себе вектор $\vec{e} = (e_1, \dots, e_n)$ . Я был бы одинаково доволен результатами, касающимися $||\vec{e}||_1$ или $||\vec{e}||_2$ .

Для $||\vec{e}||_\infty$ найти простую оценку в терминах диаметра графа: поскольку все $e_i$ должны суммироваться до нуля, если существует большое положительное значение $e_i$ , где-то должен быть отрицательный $e_j$ . Отсюда их разница $|e_i - e_j|$ по крайней мере $|e_i|$ , но эта разница может составлять самое короткое расстояние между узлами $i$ и $j$ , которое, в свою очередь, может составлять самое большее диаметр графика.

Я заинтересован в более сильных границах, предпочтительно для или нормы. Я предполагаю, что это должно включать некоторую спектральную теорию графов, чтобы отразить связность графа. Я пытался выразить это как проблему максимального потока, но безрезультатно. $1$ $2$

РЕДАКТИРОВАТЬ: больше объяснений. Я заинтересован в или норме, так как они более точно отражают общий дисбаланс. Тривиальное отношение будет получено из и $1$ $2$ $||\vec{e}||_1 \leq n|||\vec{e}||_\infty$ . Я ожидаю, однако, что из-за связности графика и моего ограничения в разнице нагрузок между соседними узлами, чтоинормы должны быть намного меньше. $||\vec{e}||_2 \leq \sqrt{n}||\vec{e}||_\infty$ $1$ $2$

Пример: Гиперкуб измерения d, с . Он имеет диаметр . Максимальный дисбаланс не более . Это предлагает в качестве верхней оценки для нормы . До сих пор мне не удавалось построить ситуацию, когда это на самом деле получается, лучшее, что я могу сделать, это что-то вроде $n = 2^d$ $d = \log_2(n)$ $d$ $1$ $nd = n\log_2(n)$ $||\vec{e}||_1 = n/2$ где я встраиваю цикл в Гиперкуб и у узлов есть дисбалансы , , , и т. д. Таким образом, здесь граница отключена с коэффициентом , который я считаю слишком большим, так как я ищу (асимптотически) жесткие границы. $0$ $1$ $0$ $-1$ $\log(n)$

graph-theory co.combinatorics spectral-graph-theory Lagerbaer
источник

интересный вопрос. есть ли конкретное приложение?

Суреш Венкат

@ Андрас Саламон: Спасибо за редактирование. @Suresh Venkat: Предположим, что веса представляют количество агентов одинакового размера, которые хотят минимизировать свою опытную нагрузку. Они захотят перейти от

если

. Если никто не хочет двигаться, мы называем это равновесием по Нэшу. Вопрос: Какой самый большой суммарный дисбаланс мы можем иметь в равновесии по Нэшу?

i

$i$

j

$j$

w_{i} > w_{i}

$w_i > w_i$

Лагербаер

У вас есть пример графика, где ваша простая граница диаметра слишком свободна?

mhum

Ну, я могу тривиально связать две другие нормы, используя

. Я заинтересован в

или

норме, так как они более точно отражают "полный" дисбаланс. Я добавил пример к своему вопросу.

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

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

1

$1$

2

$2$

Лагербаер

Для гиперкуба, что если мы взвесим вершины по весу Хэмминга? Я получаю что-то вроде

для

, и я думаю, что

будет порядка

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

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

l_{2}

$l_2$

l_{1}

$l_1$

n d

$nd$

Артем Казнатчеев

Ответы:

Так как ограничен диаметром , норма будет тривиально ограничена , аналогично для нормы , кроме $|e_i|$ $d$ $\ell_1$ $nd$ $\ell_2$ (фактическинорма ограничена). $\sqrt{n}d$ $\ell_p$ $n^{1/p}d$

случай оказывается на удивление легко анализировать. $\ell_1$

Для пути легко увидеть, что - это , поэтому вы не можете сделать лучше, чем . $\|\vec e\|_1$ $O(n^2)$ $O(nd)$

Для полного -ого дерева вы можете разделить его пополам в корне, установив , поднимаясь с одной стороны и опуская другую, пока листья не получат , производя снова. $k$ $w_{\text{root}} = 0$ $|e_i| = |w_i| = \log_k n$ $O(n\log_k n) = O(nd)$

Для клики не имеет значения, как вы распределяете веса, так как все они будут в пределах друг от друга, и это снова приведет к . $1$ $O(n) = O(nd)$

Когда вы понимаете, что мы говорим здесь о функции , и тогда мы берем ее норму , если вы можете произвольно распределить веса равномерно по всему диапазону, граница будет . $e : \mathbb{Z} \to [-d/2,d/2] \subset \mathbb{R}$ $\ell_1$ $e_i \in [-d/2,d/2]$ $O(nd)$

Единственный способ изменить это - играть в игры с массой. Например, если у вас есть несколько гигантских клик в точках, которые обязательно сбалансированы, например, гигантская клика с двумя путями равной длины, выступающими из нее, то вы можете рассчитывать только на оценку (например) . $O(d^2)$

Это может быть верно и для расширителей в некоторой степени, но я не уверен. Я мог бы представить себе случай, когда вы устанавливаете в регулярном графе, а затем позволяете значениям увеличиваться впоследствии с каждым прыжком. Кажется вероятным, что среднее может иметь наибольшую массу, но я не знаю, будет ли этого достаточно, чтобы повлиять на границы. $w_1 = 0$

Я думаю, что вы могли бы так же рассуждать о . $\ell_2$

РЕДАКТИРОВАТЬ:

В комментариях мы выяснили (свободную) оценку используя ограничения задачи и некоторую базовую теорию спектральных графов. $\ell_2$ $O(|E|/\lambda_2(L))$

Жозефина Меллер
источник

Мне нравится твой ответ. Однако у меня есть проблема с « до тех пор, пока вы можете произвольно распределить веса равномерно по всему диапазону ». Не могу ли я представить себе ситуацию, когда граница диаметра позволила бы мне разместить вес

но тогда структура графика такова, что я не могу компенсировать этот большой положительный вес? Итак, хотя

конечно, является верхней границей, возможно ли получить более жесткие границы? В конечном счете, используя второе наименьшее собственное значение лапласиана или второе по величине собственное значение смежности (как они кодируют информацию о связности)?

e_{i} = d / 2

$e_i = d/2$

O (n d)

$\mathcal{O}(nd)$

Лагербаер

Ну вы не размещая

, вы размещения

. Таким образом, если у вас есть перекос

, должно быть большое количество небольших весов, которые компенсируют его по другую сторону от среднего значения, или некоторый другой большой вес, диаметрально противоположный этому. Единственный способ получить оценку меньше

- это как-то рассчитывать на структуру. И, как я уже сказал, я не уверен, что это будет означать, скажем, для экспандера. Я не думаю, что вы могли бы сделать это исключительно на основе проводимости, из-за случаев, которые я изложил в своем ответе.

e_{i}

$e_i$

w_{i}

$w_i$

e_{i}

$e_i$

O (n d)

$O(nd)$

Жозефина Мёллер

Позвольте мне предложить другой пример. Граф Дамбелла с двумя кликами имеет очень низкую проводимость, но его дисбаланс ограничен 2.

Джозефина Мёллер,

Граница, связанная со структурой, была бы тем, чем я был бы совершенно доволен. Вот почему я упомянул собственные значения, так как они относятся к свойствам соединения. Например, существуют ограничения на диаметр, средний путь, изопериметрическое число и т. Д. В терминах второго наименьшего собственного вектора матрицы Лапласа графа.

Лагербаер

Читайте ваш другой пример только сейчас. Я ожидаю, что такой граф также будет иметь очень маленькое собственное значение Лапласа второго наименьшего размера, так как изопериметрическое число будет около

2 / n

$2/n$

Лагербаер

Для связанных графов дисбаланс ограничен сверху диаметром графа. Для того, чтобы связать дисбаланс , мы можем переписать каждое как где $|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$ - кратчайший путь от до . Определим . Мы можем написать $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}|$

$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$

$k$ $D+1$ $k$ $n$ $m$ $D+1$ $D$

Николас Руоцци
источник

D < \infty

$D<\infty$

0

$0$

0

$0$

k

$k$

k (n - 1) / n

$k(n-1)/n$

k

$k$

n

$n$

k

$k$ можно сделать настолько большим, насколько это необходимо.

Андрас Саламон,

G

$G$

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

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