一千萬個為什麽

搜索

圖表中的最大不平衡?

讓$ G $成為連通圖$ G =(V,E)$,節點$ V = 1 \ dots n $和edge $ 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 \ le 1 \; \ foall(i,j)\ in E. $$

Question: What is the largest possible imbalance the network can have, in terms of $n$ and $m$? To be more precise, picture the vector $\vec{e} = (e_1, \dots, e_n)$. I'd be equally content with results concerning $||\vec{e}||_1$ or $||\vec{e}||_2$.

對於$ || \ vec {e} || _ \ infty $,可以找到圖直徑的簡單界限:由於所有$ e_i $必須總和為零,如果有一個大的正$ e_i $,那麽必須在某處負$ e_j $。因此他們的差異$ | e_i - e_j | $至少是$ | e_i | $,但是這個差異最多可以是節點$ i $和$ j $之間的最短距離,而這最多可以是圖表直徑。

我對更強的界限感興趣,最好是$ 1 $ - 或$ 2 $ -norm。我想它應該涉及一些光譜圖理論來反映圖的連通性。我嘗試將其表達為最大流量問題,但無濟於事。

編輯:更多解釋。 我對$ 1 $ - 或$ 2 $ -norm感興趣,因為它們更準確地反映了總體不平衡。可以從$ || \ vec {e} || _1 \ leq n ||| \ vec {e} || _ \ infty $和$ || \ vec {e} || _2 \ leq獲得一個簡單的關系\開方{N} || \ VEC {E} || _ \ infty $。然而,我期望由於圖形的連通性和我在相鄰節點之間的負載差異中的約束,$ 1 $和$ 2 $ -norms應該小得多。

示例:Dimension d的超立方體,$ n = 2 ^ d $。它的直徑為$ d = \ log_2(n)$。最大的不平衡最多是$ d $。這建議作為$ 1 $ -norm $ nd = n \ log_2(n)$的上限。到目前為止,我一直無法構建實際獲得的情況,我能做的最好的事情就是$ || \ vec {e} || _1 = n/2 $,其中我嵌入了一個循環進入Hypercube並讓節點有不平衡$ 0 $,$ 1 $,$ 0 $,$ -1 $等等。所以,這裏的界限是因為$ \ log(n)$,我認為已經太多了,因為我正在尋找(漸近)緊張的界限。

最佳答案

由於$ | e_i | $受到直徑$ d $的限制,因此除了$ \ sqrt {n} d外,$ \ ell_1 $規範將以$ nd $為界,同樣適用於$ \ ell_2 $範數。 $(實際上$ \ ell_p $範圍受$ n ^ {1/p} d $限制。

$ \ ell_1 $案例的結果非常容易分析。

對於一個路徑,很容易看出$ \ | \ vec e \ | _1 $是$ O(n ^ 2)$,所以你不能做得比$ O(nd)$更好。

對於一個完整的$ k $ -ary樹,你可以將它在根部分成兩半,設置$ 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 $ norm,只要您可以在[-d/2,d/2] $中均勻地在權重範圍內任意分配權重$ e_i \,該界限將為$ O(nd)$。

改變這種狀況的唯一方法就是玩大眾遊戲。例如,如果你在必須平衡的點上有幾個巨大的派系,就像一個巨大的集團,有兩條等長的路徑突出它,那麽你可以指望只有(例如)$ O(d ^ 2) )$。

對於擴展器來說,這在某種程度上也是如此,但我不確定。我可以想象一種情況,你在常規圖中設置$ w_1 = 0 $然後讓值隨後從每一跳增加。似乎平均值可能具有最大質量,但我不知道它是否足以影響界限。

我認為你可以推理$ \ ell_2 $。

編輯:

在評論中,我們使用問題的約束和一些基本的譜圖理論計算了$ O(| E |/\ lambda_2(L))$的(松散)$ \ ell_2 $界限。

轉載註明原文: 圖表中的最大不平衡?