Maximales Ungleichgewicht in einem Diagramm?

Lassen $G$ ein zusammenhängender Graph $G = (V,E)$ mit Knoten $V = 1 \dots n$ und die Kanten $E$ . Sei $w_i$ das (ganzzahlige) Gewicht des Graphen $G$ , wobei $\sum_i w_i = m$ das Gesamtgewicht im Graphen ist. Das durchschnittliche Gewicht pro Knoten beträgt dann $\bar w = m/n$ . Sei $e_i = w_i - \bar w$ die Abweichung des Knotens $i$ aus dem Mittel. Wir nennen $|e_i|$ dasUngleichgewichtdes Knotens $i$ .

Angenommen, das Gewicht zwischen zwei benachbarten Knoten kann sich um höchstens $1$ , dh

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

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

Frage : Was ist das größtmögliche Ungleichgewicht, das das Netzwerk in Bezug auf $n$ und $m$ ? Um genauer zu sein, stellen Sie sich den Vektor $\vec{e} = (e_1, \dots, e_n)$ . Ich wäre gleichermaßen zufrieden mit den Ergebnissen bezüglich $||\vec{e}||_1$ oder $||\vec{e}||_2$ .

Für $||\vec{e}||_\infty$ kann eine einfache Grenze in Bezug auf den Graphendurchmesser gefunden werden: Da alle $e_i$ zu Null summieren müssen , muss es irgendwo ein negatives , wenn es ein großes positives $e_i$ gibt . Daher ihre Differenz ist mindestens Dieser Unterschied kann jedoch höchstens der kürzeste Abstand zwischen den Knoten und , der wiederum höchstens der Graphendurchmesser sein kann. $e_j$ $|e_i - e_j|$ $|e_i|$ $i$ $j$

Ich interessiere mich für stärkere Grenzen, vorzugsweise für die $1$ - oder $2$ Norm. Ich nehme an, es sollte eine Spektralgraphentheorie beinhalten, um die Konnektivität des Graphen widerzuspiegeln. Ich habe versucht, es als Max-Flow-Problem auszudrücken, ohne Erfolg.

EDIT: Weitere Erklärung. Ich interessiere mich für die $1$ - oder $2$ Norm, da sie das gesamte Ungleichgewicht genauer widerspiegeln. Eine triviale Beziehung würde sich aus $||\vec{e}||_1 \leq n|||\vec{e}||_\infty$ und . Ich erwarte jedoch, dass aufgrund der Verbundenheit des Graphen und meiner Einschränkung derLastdifferenzzwischen benachbarten Knoten dieundNorm viel kleiner sein sollten. $||\vec{e}||_2 \leq \sqrt{n}||\vec{e}||_\infty$ $1$ $2$

Beispiel: Hypercube der Dimension d mit . Es hat einen Durchmesser . Das maximale Ungleichgewicht beträgt dann höchstens . Dies legt als Obergrenze für die Norm . Bisher war ich nicht in der Lage, eine Situation zu konstruieren, in der dies tatsächlich erreicht wird. Das Beste, was ich tun kann, ist etwas in der Art von $n = 2^d$ $d = \log_2(n)$ $d$ $1$ $nd = n\log_2(n)$ $||\vec{e}||_1 = n/2$ , wo ich einen Zyklus in den Hypercube einbette und die Knoten Ungleichgewichte , , , usw. haben. Hier ist die Grenze also um einen Faktor von , den ich bereits als zu viel betrachte, wie ich Ich suche (asymptotisch) enge Grenzen. $0$ $1$ $0$ $-1$ $\log(n)$

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

interessante Frage. Gibt es eine bestimmte Anwendung?

Suresh Venkat

@ András Salamon: Danke für die Bearbeitung. @Suresh Venkat: Angenommen, die Gewichte stellen die Anzahl der Agenten mit einheitlicher Größe dar, die ihre erfahrene Belastung minimieren möchten. Sie werden von

nach

wechseln wollen, wenn

. Wenn sich niemand bewegen will, nennen wir es ein Nash-Gleichgewicht. Frage: Was ist das größte Ungleichgewicht, das wir in einem Nash-Gleichgewicht haben könnten?

i

$i$

j

$j$

w_{i} > w_{i}

$w_i > w_i$

Lagerbaer

Haben Sie zufällig ein Beispiel für ein Diagramm, bei dem Ihre einfache Durchmessergrenze viel zu locker ist?

mhum

Nun, ich kann die beiden anderen Normen mit

trivial binden

. Ich interessiere mich für die

- oder

Norm, da sie das "totale" Ungleichgewicht genauer erfassen. Ich habe meiner Frage ein Beispiel hinzugefügt.

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

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

1

$1$

2

$2$

Lagerbaer

Was ist, wenn wir für den Hyperwürfel die Scheitelpunkte mit ihrem Hamming-Gewicht abwägen? Ich bekomme so etwas wie

für das

, und ich denke, das

wird in der Ordnung

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

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

l_{2}

$l_2$

l_{1}

$l_1$

n d

$nd$

Artem Kaznatcheev

Antworten:

Da wird durch den Durchmesser , wird die Norm trivial durch , ebenso für die Norm, außer durch $|e_i|$ $d$ $\ell_1$ $nd$ $\ell_2$ (tatsächlich ist dieNorm durch). $\sqrt{n}d$ $\ell_p$ $n^{1/p}d$

Der Fall ist überraschend einfach zu analysieren. $\ell_1$

$\|\vec e\|_1$ $O(n^2)$ $O(nd)$

Für einen vollständigen -ary-Baum können Sie ihn an der Wurzel in zwei Hälften teilen, indem Sie , eine Seite aufsteigen und die andere absteigen, bis die Blätter , wodurch wieder wird. $k$ $w_{\text{root}} = 0$ $|e_i| = |w_i| = \log_k n$ $O(n\log_k n) = O(nd)$

Für eine Clique spielt es keine Rolle, wie Sie die Gewichte verteilen, da sie alle innerhalb von voneinander liegen und dies wiederum ergibt . $1$ $O(n) = O(nd)$

Wenn Sie erkennen, dass es sich hier um eine Funktion , nehmen wir ihre Norm: Solange Sie die Gewichte beliebig gleichmäßig über den Bereich verteilen können, ist die Grenze . $e : \mathbb{Z} \to [-d/2,d/2] \subset \mathbb{R}$ $\ell_1$ $e_i \in [-d/2,d/2]$ $O(nd)$

Die einzige Möglichkeit, dies zu ändern, besteht darin, Spiele mit der Masse zu spielen. Wenn Sie beispielsweise mehrere Riesencliquen an Punkten haben, die notwendigerweise ausgeglichen sind, wie eine Riesenclique, aus der zwei Pfade gleicher Länge herausragen, können Sie auf eine Grenze von nur (zum Beispiel) . $O(d^2)$

Dies mag bis zu einem gewissen Grad auch für Expander zutreffen, aber ich bin mir nicht sicher. Ich könnte mir einen Fall vorstellen, in dem Sie in einem regulären Graphen und die Werte anschließend von jedem Sprung an ansteigen lassen. Es scheint wahrscheinlich, dass der Mittelwert möglicherweise die größte Masse haben könnte, aber ich weiß nicht, ob es ausreichen würde, um die Grenze zu beeinflussen. $w_1 = 0$

Ich denke, dass Sie ähnlich über könnten . $\ell_2$

BEARBEITEN:

In den Kommentaren haben wir eine (lose) Grenze von Verwendung der Einschränkungen des Problems und einiger grundlegender Spektralgraphentheorie herausgefunden. $\ell_2$ $O(|E|/\lambda_2(L))$

Josephine Moeller
quelle

Ich mag deine Antwort. Ich habe jedoch ein Problem mit " solange Sie die Gewichte willkürlich gleichmäßig über den Bereich verteilen können ". Könnte ich mir nicht eine Situation vorstellen, in der der gebundene Durchmesser es mir ermöglichen würde, irgendwo ein Gewicht aber dann ist die Struktur des Diagramms so, dass ich dieses große positive Gewicht unmöglich kompensieren kann? Also, während natürlich ist eine obere Grenze, wäre es möglich, engere Grenzen zu erhalten? Verwenden Sie schließlich den zweitkleinsten Laplace-Eigenwert oder den zweitgrößten Adjazenz-Eigenwert (da sie Konnektivitätsinformationen codieren)?

e_{i} = d / 2

$e_i = d/2$

O (n d)

$\mathcal{O}(nd)$

Lagerbaer

Nun, Sie platzieren nicht , Sie platzieren . Wenn Sie also ein schiefes , muss es eine große Anzahl kleiner Gewichte geben, die es auf der anderen Seite des Mittelwerts kompensieren, oder ein anderes großes Gewicht, das ihm diametral entgegengesetzt ist. Die einzige Möglichkeit, eine Grenze kleiner als besteht darin, sich irgendwie auf die Struktur zu verlassen. Und wie gesagt, ich bin mir nicht sicher, was dies beispielsweise für einen Expander bedeuten würde. Ich glaube nicht, dass Sie es aufgrund der Leitfähigkeit tun könnten, aufgrund der Fälle, die ich in meiner Antwort dargelegt habe.

e_{i}

$e_i$

w_{i}

$w_i$

e_{i}

$e_i$

O (n d)

$O(nd)$

Josephine Moeller

Lassen Sie mich ein weiteres Beispiel geben. Ein Hantelgraph mit zwei Cliquen hat eine sehr geringe Leitfähigkeit, aber sein Ungleichgewicht ist durch 2 begrenzt.

Josephine Moeller

Eine Bindung, die sich auf die Struktur bezieht, wäre etwas, mit dem ich vollkommen zufrieden wäre. Deshalb habe ich die Eigenwerte erwähnt, da sie sich auf die Verbindungseigenschaften beziehen. Es gibt z. B. Grenzen für den Durchmesser, den mittleren Pfad, die isoperimetrische Zahl usw. in Bezug auf den zweitkleinsten Eigenvektor der Laplace-Matrix des Graphen.

Lagerbaer

Lesen Sie gerade Ihr anderes Beispiel. Ich gehe davon aus, dass ein solcher Graph auch einen sehr kleinen zweitkleinsten Laplace-Eigenwert haben würde, da die isoperimetrische Zahl bei etwa .

2 / n

$2/n$

Lagerbaer

Bei verbundenen Graphen wird das Ungleichgewicht durch den Durchmesser des Graphen begrenzt. Um das Ungleichgewicht können wir jedes als wobei der kürzeste Weg von nach . Definiere . Wir können $|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}|$

Jedes ist durch die Länge des kürzesten Weges von nach durch Ihre Annahme begrenzt, dass für jedes . Daher erhalten wir die triviale Grenze: $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$

Dies ist möglicherweise nicht allzu weit vom Optimum entfernt. Ich denke an einen vollständigen -ary-Baum, bei dem die Knoten auf jeder Ebene ein um eins höheres Gewicht haben als das Gewicht der vorherigen Ebene. Ein großer Teil des Diagramms hat das höchste Gewicht, . Der Durchschnitt sollte also nach oben geneigt sein. Wenn und größer werden, erwarte ich, dass immer näher an was bedeutet, dass das Ungleichgewicht immer näher an heranrücken sollte . $k$ $D+1$ $k$ $n$ $m$ $D+1$ $D$

Nicholas Ruozzi
quelle

Soweit ich die Konstruktion hier skizzierte sagen kann , streng gemacht werden, erreichen Ungleichgewicht so nah an wie gewünscht. Da die Frage jedoch nicht spezifiziert, was passiert, wenn Scheitelpunkte nicht benachbart sind, ist eine einfachere Konstruktion ein vollständig getrennter Graph mit Scheitelpunkt mit Gewicht und allen anderen Scheitelpunkten mit Gewicht . Dies hat ein Durchschnittsgewicht was auch sein maximales Ungleichgewicht ist. Dies kann eindeutig beliebig nahe an gebracht werden, indem ein ausreichend großes , und kann so groß gemacht werden, wie es gewünscht wird.

D < \infty

$D<\infty$

0

$0$

0

$0$

k

$k$

k (n - 1) / n

$k(n-1)/n$

k

$k$

n

$n$

k

$k$

András Salamon

G

$G$

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

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