Déséquilibre maximal dans un graphique?

Soit un graphe connexe avec des noeuds et des bords . Soit le poids (entier) du graphe , avec le poids total du graphe. Le poids moyen par nœud est alors . Soit la déviation du nœud $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$ de la moyenne. Nous appelonsledéséquilibredu nœud . $i$ $|e_i|$ $i$

Supposons que le poids entre deux nœuds adjacents quelconques puisse différer d'au plus , c'est-à-dire $1$

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

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

Question : Quel est le plus grand déséquilibre possible que le réseau puisse avoir, en termes de et ? Pour être plus précis, imaginez le vecteur . Je serais également satisfait des résultats concernant ou . $n$ $m$ $\vec{e} = (e_1, \dots, e_n)$ $||\vec{e}||_1$ $||\vec{e}||_2$

Pour , une borne simple en termes de diamètre du graphe peut être trouvée: Puisque tout doit être égal à zéro, s'il y a un grand positif , il doit y avoir quelque part un négatif . D'où leur différence est au moins , mais cette différence peut être au plus la distance la plus courte entre les nœuds et , qui à son tour peut être au plus le diamètre du graphe. $||\vec{e}||_\infty$ $e_i$ $e_i$ $e_j$ $|e_i - e_j|$ $|e_i|$ $i$ $j$

Je suis intéressé par des limites plus fortes, de préférence pour la norme ou . Je suppose que cela devrait impliquer une théorie du graphe spectral pour refléter la connectivité du graphe. J'ai essayé de l'exprimer comme un problème de débit maximal, en vain. $1$ $2$

EDIT: Plus d'explications. Je m'intéresse à la norme ou car elles reflètent plus précisément le déséquilibre total. Une relation triviale serait obtenue à partir de et $1$ $2$ $||\vec{e}||_1 \leq n|||\vec{e}||_\infty$ . Je m'attends cependant à ce qu'en raison de la connectivité du graphique et de ma contrainte dans la différence de charges entre les nœuds adjacents, lesnormesetdevraient être beaucoup plus petites. $||\vec{e}||_2 \leq \sqrt{n}||\vec{e}||_\infty$ $1$ $2$

Exemple: Hypercube de dimension d, avec . Il a un diamètre . Le déséquilibre maximal est alors au plus . Cela suggère comme limite supérieure pour la -norm . Jusqu'à présent, je n'ai pas été en mesure de construire une situation où cela est réellement obtenu, le mieux que je puisse faire est quelque chose comme $n = 2^d$ $d = \log_2(n)$ $d$ $1$ $nd = n\log_2(n)$ $||\vec{e}||_1 = n/2$ , Où j'intégrer un cycle dans l'hypercube et ont les noeuds ont des déséquilibres , , , etc. Donc, voici la limite est désactivée par un facteur de , que je considère déjà trop, comme je cherche des limites serrées (asymptotiquement). $0$ $1$ $0$ $-1$ $\log(n)$

graph-theory co.combinatorics spectral-graph-theory Lagerbaer
la source

question interessante. y a-t-il une application particulière?

Suresh Venkat

@ András Salamon: Merci pour la modification. @Suresh Venkat: Supposons que les poids représentent le nombre d'agents de taille uniforme qui souhaitent minimiser leur charge expérimentée. Ils voudront passer de

. Si personne ne veut bouger, nous l'appelons un équilibre de Nash. Question: Quel est le plus grand déséquilibre total que nous pourrions avoir dans un équilibre de Nash?

i

$i$

j

$j$

w_{i} > w_{i}

$w_i > w_i$

Lagerbaer

Avez-vous un exemple de graphique où votre simple diamètre lié est beaucoup trop lâche?

mhum

Eh bien, je peux relier trivialement les deux autres normes en utilisant

. Je m'intéresse à la norme

- ou

car ils captent plus précisément le déséquilibre "total". J'ai ajouté un exemple à ma question.

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

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

1

$1$

2

$2$

Lagerbaer

Pour l'hypercube, que se passe-t-il si nous pesons les sommets par leur poids de Hamming? Je reçois quelque chose comme

pour le

, et je pense que le

sera d'ordre

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

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

l_{2}

$l_2$

l_{1}

$l_1$

n d

$nd$

Artem Kaznatcheev

Réponses:

Depuis est borné par le diamètre , la norme va être trivialement bornée par , de même pour la norme , sauf par $|e_i|$ $d$ $\ell_1$ $nd$ $\ell_2$ (en fait lanormeest bornée par). $\sqrt{n}d$ $\ell_p$ $n^{1/p}d$

Le cas s'avère étonnamment facile à analyser. $\ell_1$

Pour un chemin, il est facile de voir que est , donc vous ne pouvez pas faire mieux que . $\|\vec e\|_1$ $O(n^2)$ $O(nd)$

Pour un arbre -ary complet , vous pouvez le diviser en deux à la racine, en définissant , en montant d'un côté et en descendant de l'autre jusqu'à ce que les feuilles aient , produisant de nouveau . $k$ $w_{\text{root}} = 0$ $|e_i| = |w_i| = \log_k n$ $O(n\log_k n) = O(nd)$

Pour une clique, la façon dont vous répartissez les poids n'a pas vraiment d'importance, car ils seront tous à moins de de l'autre, et cela donnera à nouveau . $1$ $O(n) = O(nd)$

Lorsque vous réalisez que ce dont nous parlons ici est une fonction , puis nous prenons sa norme , tant que vous pouvez distribuer arbitrairement des poids uniformément sur toute la plage, la limite sera . $e : \mathbb{Z} \to [-d/2,d/2] \subset \mathbb{R}$ $\ell_1$ $e_i \in [-d/2,d/2]$ $O(nd)$

La seule façon de changer cela est de jouer à des jeux avec la masse. Par exemple, si vous avez plusieurs cliques géantes à des points qui sont nécessairement équilibrés, comme une clique géante avec deux chemins de longueur égale en saillie, alors vous pouvez compter sur une limite de seulement (par exemple) . $O(d^2)$

Cela peut être vrai pour les expandeurs dans une certaine mesure également, mais je ne suis pas sûr. Je pourrais imaginer un cas où vous définissez dans un graphique régulier, puis laissez les valeurs augmenter par la suite à chaque saut. Il semble probable que la moyenne pourrait avoir le plus de masse, mais je ne sais pas si cela suffirait à affecter la limite. $w_1 = 0$

Je pense que vous pourriez raisonner de la même manière sur . $\ell_2$

ÉDITER:

$\ell_2$ $O(|E|/\lambda_2(L))$

Josephine Moeller
la source

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

Permettez-moi de vous donner un autre exemple. Un graphique dumbell avec deux cliques a une conductance très faible, mais son déséquilibre est limité par 2.

Josephine Moeller

Une limite liée à la structure serait quelque chose dont je serais parfaitement satisfait. C'est pourquoi j'ai mentionné les valeurs propres, car elles se rapportent aux propriétés de connexion. Il y a, par exemple, des limites sur le diamètre, le chemin moyen, le nombre isopérimétrique etc. en termes du deuxième plus petit vecteur propre de la matrice laplacienne du graphique.

Lagerbaer

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$

Nicholas Ruozzi
la source

D < \infty

$D<\infty$

0

$0$

0

$0$

k

$k$

k (n - 1) / n

$k(n-1)/n$

k

$k$

n

$n$

k

$k$ peut être rendu aussi grand que souhaité.

András Salamon

G

$G$

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

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