<p>For connected graphs, the imbalance is upper bounded by the diameter of the graph. In order to bound the imbalance  $|w_i - 1/n\sum_k w_k|$, we can rewrite each $w_k$ as $w_k - v_1 + v_1 - v_2 + v_2 - ... - v_k + v_k - w_i + w_i$  where $w_k, v_1,...,v_k, w_i$ is the shortest path from $w_i$ to $w_k$.  Define $w_{ki} = w_k - v_1 + v_1 - v_2 + v_2 - ... - v_k + v_k - w_i$.  We can write 
$$|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}|$$</p>

<p>Each $w_{ki}$ is upper bounded by the length of the shortest path from $i$ to $k$ by your assumption that $w_i - w_j \leq 1$ for each $i,j\in E$.  Therefore, we get the trivial bound:
$$|w_i - 1/n\sum_k w_k| \leq \frac{(n-1)}{n} D$$</p>

<p>This might not actually be too far from optimal.  I'm thinking of a complete $k$-ary tree where the nodes on each level have weight one higher than the weight of the previous level.  A large fraction of the graph has the highest weight, $D+1$.  So, the average should be skewed towards the top.  As $k$ and $n$ get larger, I expect $m$ to get closer and closer to $D+1$ which means the imbalance should get closer and closer to $D$.</p>

CC BY-SA 3.0
2011-04-09T11:14:12.883Z
As far as I can tell the construction sketched here can be made rigorous, to achieve imbalance as close to $D<\infty$ as is desired.  However, since the question does not specify what happens when vertices are not adjacent, an easier construction is a completely disconnected graph with vertex $0$ having weight $0$ and all other vertices with weight $k$.  This has average weight $k(n-1)/n$ which is also its maximum imbalance.  This clearly can be made arbitrarily close to $k$ by choosing a large enough $n$, and $k$ can be made as large as is desired.
András Salamon
CC BY-SA 3.0
2011-04-09T11:55:10.810Z
@András Salamon: Good point.  The above answer assumes that the given graph $G$ is connected.  I'll edit it to make that clear.
Nicholas Ruozzi
CC BY-SA 3.0
2011-04-09T14:46:48.793Z
I have added the "connected" constraint to my question, as this was what I had in mind. The answer here presents a bound on $||\vec{e}||_\infty$. Also, when I asked for the "worst" case, I had in mind that the graph would be fixed, and I'd try to find the worst case for that particular graph.
Lagerbaer
CC BY-SA 3.0
2011-04-09T09:17:37.953Z
2011-04-09T11:55:41.497Z
2011-04-09T11:55:41.497Z
Nicholas Ruozzi
<p>Since $|e_i|$ is bounded by the diameter $d$, the $\ell_1$ norm is going to be trivially bounded by $nd$, likewise for the $\ell_2$ norm, except by $\sqrt{n}d$ (in fact the $\ell_p$ norm is bounded by $n^{1/p}d$).</p>

<p>The $\ell_1$ case turns out to be surprisingly easy to analyze.</p>

<p>For a path, it's easy to see that $\|\vec e\|_1$ is $O(n^2)$, so you can't do any better than $O(nd)$.</p>

<p>For a complete $k$-ary tree, you can divide it in half at the root, setting $w_{\text{root}} = 0$, ascending one side and descending the other until the leaves have $|e_i| = |w_i| = \log_k n$, producing $O(n\log_k n) = O(nd)$ again.</p>

<p>For a clique it doesn't really matter how you distribute the weights, since they'll all be within $1$ of each other, and that will yield $O(n) = O(nd)$ again.</p>

<p>When you realize that what we're talking about here is a function $e : \mathbb{Z} \to [-d/2,d/2] \subset \mathbb{R}$, and then we're taking its $\ell_1$ norm, as long as you can arbitrarily distribute weights $e_i \in [-d/2,d/2]$ evenly across the range, the bound will be $O(nd)$. </p>

<p>The only way to change this is to play games with the mass. For instance, if you have several giant cliques at points that are necessarily balanced, like a giant clique with two paths of equal length jutting out of it, then you can count on a bound of only (for example) $O(d^2)$. </p>

<p>This may be true for expanders to some degree as well, but I'm not sure. I could imagine a case where you set $w_1 = 0$ in a regular graph and then let the values increase subsequently from every hop. It seems likely that the mean could possibly have the most mass, but I don't know if it would be enough to affect the bound.</p>

<p>I think that you could reason similarly about $\ell_2$.</p>

<p>EDIT:</p>

<p>In the comments we figured out a (loose) $\ell_2$ bound of $O(|E|/\lambda_2(L))$ using the constraints of the problem and some basic spectral graph theory.</p>

CC BY-SA 3.0
2011-04-09T20:51:24.880Z
I like your answer. However, I have a problem with "*as long as you can arbitrarily distribute weights evenly across the range*". Couldn't I envision a situation where the diameter bound would allow me to place a weight $e_i = d/2$ somewhere but then the structure of the graph is such that I cannot possibly compensate this large positive weight? So, while $\mathcal{O}(nd)$ of course *is* an upper bound, would it be possible to obtain tighter bounds? Eventually using the second-smallest Laplacian eigenvalue or the second largest adjacency eigenvalue (as they encode connectivity information)?
Lagerbaer
CC BY-SA 3.0
2011-04-09T20:58:51.717Z
Well you aren't placing $e_i$, you're placing $w_i$. So if you have a skewed $e_i$, there must be a large number of small weights that compensate it on the other side of the mean, or some other large weight diametrically opposed to it. 

The only way that you could get a bound smaller than $O(nd)$ is to count on the structure somehow. And like I said, I'm not sure what this would mean for, say, an expander. I don't think you could do it purely based on the conductance, because of the cases I laid out in my answer.
Josephine Moeller
CC BY-SA 3.0
2011-04-09T21:11:28.770Z
Let me offer another example. A dumbell graph with two cliques has very low conductance, but its imbalance is bounded by 2.
Josephine Moeller
CC BY-SA 3.0
2011-04-09T21:13:39.377Z
A bound that relates to the structure would be something I'd be perfectly happy with. That's why I mentioned the eigenvalues, as they relate to the connection properties. There are, eg., bounds on the diameter, the mean path, the isoperimetric number etc. in terms of the second smallest eigenvector of the graph's Laplacian matrix.
Lagerbaer
CC BY-SA 3.0
2011-04-09T21:15:00.673Z
Read your other example just now. I expect that such a graph would have a very small second-smallest Laplacian eigenvalue as well, as the isoperimetric number would be around $2/n$.
Lagerbaer
CC BY-SA 3.0
2011-04-09T21:23:26.353Z
Right, $\lambda_2(L)$ is proportional to the conductance. I offered this example of something that gives you a necessarily small imbalance, but a conductance similar to a path, which has high imbalance. In the other direction, high conductance improves your bound by reducing the diameter, but my gut tells me that you're still stuck with the $n$ factor.
Josephine Moeller
CC BY-SA 3.0
2011-04-09T21:40:02.423Z
I played around with the numbers a bit: A hypothesis might be that the maximum imbalance in 2-norm would be $||\vec{e}||_2^2 = \mathcal{O}( \frac{\Delta n}{\lambda_2})$ where $\Delta$ is the maximum degree in the network. It holds for paths and the complete graph. A quick python script suggests that it holds for the hypercube as well (if I follow your "start with 0 and the add weight 1 in each additional step" approach), I'm currently trying to prove it, though. Although, your dumbbell example suggests that this would be a poor bound in that case.
Lagerbaer
CC BY-SA 3.0
2011-04-09T23:10:55.593Z
I think that your new bound is worse in both the cases you mention too. $1/\lambda_2$ is $O(n^2)$ for paths, yielding a cubic bound, and $O(1)$ for cliques, but $\Delta$ is $O(n)$ for cliques, giving a quadratic bound.
Josephine Moeller
CC BY-SA 3.0
2011-04-09T23:34:02.540Z
By the way, some basic spectral graph theory confirms your $\ell_2$ bound. Your constraints make $\|\vec e\|_2^2 = O(|E|/\lambda_2(L))$, which is only slightly tighter than your bound.
Josephine Moeller
CC BY-SA 3.0
2011-04-09T23:34:17.627Z
Note that my bound is given for the square of the $2$-norm. For paths, we can indeed expect a cubic bound. For the complete graph with $n$ nodes, $\lambda_2 = n$, so the bound becomes $n$, which is accurate.
Lagerbaer
CC BY-SA 3.0
2011-04-09T23:36:06.533Z
Oh, this is because of the Laplacian's property $\vec{x}^T L \vec{x} = \sum_{(i,j)\in E} (x_i - x_j)^2$? I see. Interesting. Thank you for this :)
Lagerbaer
CC BY-SA 3.0
2011-04-10T02:15:17.460Z
@Lagerbaer, you can accept this answer (click the checkmark) if you feel that it answers your question.
Suresh Venkat
CC BY-SA 3.0
2011-04-10T02:21:24.700Z
I know. If by tomorrow there won't be another answer, this is the one I'll accept.
Lagerbaer
CC BY-SA 3.0
2011-04-10T02:42:52.890Z
That property, and the fact that $\sum e_i = 0$, which is perpendicular to the first eigenvector ${\vec v}_1=\mathbf{1}$, so $\min_{\vec e} \frac{{\vec e}^T L{\vec e}}{{\vec e}^T{\vec e}} = \lambda_2$.
Josephine Moeller
CC BY-SA 3.0
2011-04-09T20:40:02.350Z
2011-04-10T18:42:25.970Z
2011-04-10T18:42:25.970Z
Josephine Moeller
<p>Let $G$ be a connected graph $G = (V,E)$ with nodes $V = 1 \dots n$ and edges $E$. Let $w_i$ denote the (integer) weight of graph $G$, with $\sum_i w_i = m$ the total weight in the graph. The average weight per node then is $\bar w = m/n$. Let $e_i = w_i - \bar w$ denote the deviation of node $i$ from the mean. We call $|e_i|$ the <em>imbalance</em> of node $i$. </p>

<p>Suppose that the weight between any two <em>adjacent</em> nodes can differ by at most $1$, i.e., 
$$ w_i - w_j \le 1\; \forall (i,j) \in E.$$</p>

<p><strong>Question</strong>: 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$.</p>

<p>For $||\vec{e}||_\infty$, a simple bound in terms of the graph diameter can be found: Since all $e_i$ must sum to zero, if there is a large positive $e_i$, there must somewhere be a negative $e_j$. Hence their difference $|e_i - e_j|$ is at least $|e_i|$, but this difference can be at most the shortest distance between nodes $i$ and $j$, which in turn can be at most the graph diameter.</p>

<p>I'm interested in stronger bounds, preferably for the $1$- or $2$-norm. I suppose it should involve some spectral graph theory to reflect the connectivity of the graph. I tried expressing it as a max-flow problem, to no avail. </p>

<p>EDIT: More explanation.
I'm interested in the $1$- or $2$-norm as they more accurately reflect the total imbalance. A trivial relation would be obtained from $||\vec{e}||_1 \leq n|||\vec{e}||_\infty$, and $||\vec{e}||_2 \leq \sqrt{n}||\vec{e}||_\infty$. I expect, however, that due to the connectedness of the graph and my constraint in the difference of loads between adjacent nodes, that the $1$- and $2$-norms should be much smaller.</p>

<p>Example: Hypercube of Dimension d, with $n = 2^d$. It has diameter $d = \log_2(n)$. The maximum imbalance is then at most $d$. This suggest as an upper bound for the $1$-norm $nd = n\log_2(n)$. So far, I have been unable to construct a situation where this is actually obtained, the best I can do is something along the lines of $||\vec{e}||_1 = n/2$, where I embed a cycle into the Hypercube and have the nodes have imbalances $0$, $1$, $0$, $-1$ etc. So, here the bound is off by a factor of $\log(n)$, which I consider already too much, as I'm looking for (asymptotically) tight bounds.</p>

CC BY-SA 3.0
2011-04-08T21:51:56.237Z
interesting question. is there any particular application ?
Suresh Venkat
CC BY-SA 3.0
2011-04-08T22:26:01.343Z
@András Salamon: Thank's for the edit. 
@Suresh Venkat: Suppose the weights represent the number of uniform sized agents, who want to minimize their experienced load. They will want to move from $i$ to $j$ if $w_i > w_i$. If nobody wants to move, we call it a Nash equilibrium. Question: What's the largest total imbalance we could have in a Nash equilibrium?
Lagerbaer
CC BY-SA 3.0
2011-04-09T04:45:55.617Z
Do you happen to have an example of a graph where your simple diameter bound is much too loose?
mhum
CC BY-SA 3.0
2011-04-09T14:50:27.450Z
Well, I can trivially bound the other two norms using $||\vec{e}||_1 \leq n||\vec{e}||_\infty$. I'm interested in the $1$- or $2$-norm since they more accurately capture the "total" imbalance. I have added an example to my question.
Lagerbaer
CC BY-SA 3.0
2011-04-11T06:50:19.073Z
For the hypercube, what if we weigh the vertexes by their Hamming weight? I get something like $\sqrt{d(n - 2)}/2$ for the $l_2$, and I think the $l_1$ will be of order $nd$.
Artem Kaznatcheev
CC BY-SA 3.0
2011-04-11T13:58:30.213Z
Hamming weight is the number of set bits? I tried that, and you are right.
Lagerbaer
<graph-theory><co.combinatorics><spectral-graph-theory>
Maximum imbalance in a graph?
Lagerbaer
# Maximum imbalance in a graph?

(Asked by: username_0 on 2011-04-08)

Let $G$ be a connected graph $G = (V,E)$ with nodes $V = 1 \dots n$ and edges $E$. Let $w\_i$ denote the (integer) weight of graph $G$, with $\sum\_i w\_i = m$ the total weight in the graph. The average weight per node then is $\bar w = m/n$. Let $e\_i = w\_i - \bar w$ denote the deviation of node $i$ from the mean. We call $|e\_i|$ the *imbalance* of node $i$.

Suppose that the weight between any two *adjacent* nodes can differ by at most $1$, i.e.,
$$ w\_i - w\_j \le 1\; \forall (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$.

For $||\vec{e}||\_\infty$, a simple bound in terms of the graph diameter can be found: Since all $e\_i$ must sum to zero, if there is a large positive $e\_i$, there must somewhere be a negative $e\_j$. Hence their difference $|e\_i - e\_j|$ is at least $|e\_i|$, but this difference can be at most the shortest distance between nodes $i$ and $j$, which in turn can be at most the graph diameter.

I'm interested in stronger bounds, preferably for the $1$- or $2$-norm. I suppose it should involve some spectral graph theory to reflect the connectivity of the graph. I tried expressing it as a max-flow problem, to no avail.

EDIT: More explanation.
I'm interested in the $1$- or $2$-norm as they more accurately reflect the total imbalance. A trivial relation would be obtained from $||\vec{e}||\_1 \leq n|||\vec{e}||\_\infty$, and $||\vec{e}||\_2 \leq \sqrt{n}||\vec{e}||\_\infty$. I expect, however, that due to the connectedness of the graph and my constraint in the difference of loads between adjacent nodes, that the $1$- and $2$-norms should be much smaller.

Example: Hypercube of Dimension d, with $n = 2^d$. It has diameter $d = \log\_2(n)$. The maximum imbalance is then at most $d$. This suggest as an upper bound for the $1$-norm $nd = n\log\_2(n)$. So far, I have been unable to construct a situation where this is actually obtained, the best I can do is something along the lines of $||\vec{e}||\_1 = n/2$, where I embed a cycle into the Hypercube and have the nodes have imbalances $0$, $1$, $0$, $-1$ etc. So, here the bound is off by a factor of $\log(n)$, which I consider already too much, as I'm looking for (asymptotically) tight bounds.

**Tags:** graph-theory, co.combinatorics, spectral-graph-theory

> **Comments:**
> **username_1**: interesting question. is there any particular application ?  
> **username_0**: @username_5: Thank's for the edit.  @username_1: Suppose the weights represent the number of uniform sized agents, who want to minimize their experienced load. They will want to move from $i$ to $j$ if $w_i > w_i$. If nobody wants to move, we call it a Nash equilibrium. Question: What's the largest total imbalance we could have in a Nash equilibrium?  
> **username_2**: Do you happen to have an example of a graph where your simple diameter bound is much too loose?  
> **username_0**: Well, I can trivially bound the other two norms using $||\vec{e}||_1 \leq n||\vec{e}||_\infty$. I'm interested in the $1$- or $2$-norm since they more accurately capture the "total" imbalance. I have added an example to my question.  
> **username_3**: For the hypercube, what if we weigh the vertexes by their Hamming weight? I get something like $\sqrt{d(n - 2)}/2$ for the $l_2$, and I think the $l_1$ will be of order $nd$.  
> **username_0**: Hamming weight is the number of set bits? I tried that, and you are right.  

---

## 2 answers

### Answer by username_6 on 2011-04-09. Score: 8 | Accepted answer

Since $|e\_i|$ is bounded by the diameter $d$, the $\ell\_1$ norm is going to be trivially bounded by $nd$, likewise for the $\ell\_2$ norm, except by $\sqrt{n}d$ (in fact the $\ell\_p$ norm is bounded by $n^{1/p}d$).

The $\ell\_1$ case turns out to be surprisingly easy to analyze.

For a path, it's easy to see that $\|\vec e\|\_1$ is $O(n^2)$, so you can't do any better than $O(nd)$.

For a complete $k$-ary tree, you can divide it in half at the root, setting $w\_{\text{root}} = 0$, ascending one side and descending the other until the leaves have $|e\_i| = |w\_i| = \log\_k n$, producing $O(n\log\_k n) = O(nd)$ again.

For a clique it doesn't really matter how you distribute the weights, since they'll all be within $1$ of each other, and that will yield $O(n) = O(nd)$ again.

When you realize that what we're talking about here is a function $e : \mathbb{Z} \to [-d/2,d/2] \subset \mathbb{R}$, and then we're taking its $\ell\_1$ norm, as long as you can arbitrarily distribute weights $e\_i \in [-d/2,d/2]$ evenly across the range, the bound will be $O(nd)$.

The only way to change this is to play games with the mass. For instance, if you have several giant cliques at points that are necessarily balanced, like a giant clique with two paths of equal length jutting out of it, then you can count on a bound of only (for example) $O(d^2)$.

This may be true for expanders to some degree as well, but I'm not sure. I could imagine a case where you set $w\_1 = 0$ in a regular graph and then let the values increase subsequently from every hop. It seems likely that the mean could possibly have the most mass, but I don't know if it would be enough to affect the bound.

I think that you could reason similarly about $\ell\_2$.

EDIT:

In the comments we figured out a (loose) $\ell\_2$ bound of $O(|E|/\lambda\_2(L))$ using the constraints of the problem and some basic spectral graph theory.

> **Comments:**
> **username_0**: I like your answer. However, I have a problem with "*as long as you can arbitrarily distribute weights evenly across the range*". Couldn't I envision a situation where the diameter bound would allow me to place a weight $e_i = d/2$ somewhere but then the structure of the graph is such that I cannot possibly compensate this large positive weight? So, while $\mathcal{O}(nd)$ of course *is* an upper bound, would it be possible to obtain tighter bounds? Eventually using the second-smallest Laplacian eigenvalue or the second largest adjacency eigenvalue (as they encode connectivity information)?  
> **username_6**: Well you aren't placing $e_i$, you're placing $w_i$. So if you have a skewed $e_i$, there must be a large number of small weights that compensate it on the other side of the mean, or some other large weight diametrically opposed to it.   The only way that you could get a bound smaller than $O(nd)$ is to count on the structure somehow. And like I said, I'm not sure what this would mean for, say, an expander. I don't think you could do it purely based on the conductance, because of the cases I laid out in my answer.  
> **username_6**: Let me offer another example. A dumbell graph with two cliques has very low conductance, but its imbalance is bounded by 2.  
> **username_0**: A bound that relates to the structure would be something I'd be perfectly happy with. That's why I mentioned the eigenvalues, as they relate to the connection properties. There are, eg., bounds on the diameter, the mean path, the isoperimetric number etc. in terms of the second smallest eigenvector of the graph's Laplacian matrix.  
> **username_0**: Read your other example just now. I expect that such a graph would have a very small second-smallest Laplacian eigenvalue as well, as the isoperimetric number would be around $2/n$.  
> **username_6**: Right, $\lambda_2(L)$ is proportional to the conductance. I offered this example of something that gives you a necessarily small imbalance, but a conductance similar to a path, which has high imbalance. In the other direction, high conductance improves your bound by reducing the diameter, but my gut tells me that you're still stuck with the $n$ factor.  
> **username_0**: I played around with the numbers a bit: A hypothesis might be that the maximum imbalance in 2-norm would be $||\vec{e}||_2^2 = \mathcal{O}( \frac{\Delta n}{\lambda_2})$ where $\Delta$ is the maximum degree in the network. It holds for paths and the complete graph. A quick python script suggests that it holds for the hypercube as well (if I follow your "start with 0 and the add weight 1 in each additional step" approach), I'm currently trying to prove it, though. Although, your dumbbell example suggests that this would be a poor bound in that case.  
> **username_6**: I think that your new bound is worse in both the cases you mention too. $1/\lambda_2$ is $O(n^2)$ for paths, yielding a cubic bound, and $O(1)$ for cliques, but $\Delta$ is $O(n)$ for cliques, giving a quadratic bound.  
> **username_6**: By the way, some basic spectral graph theory confirms your $\ell_2$ bound. Your constraints make $\|\vec e\|_2^2 = O(|E|/\lambda_2(L))$, which is only slightly tighter than your bound.  
> **username_0**: Note that my bound is given for the square of the $2$-norm. For paths, we can indeed expect a cubic bound. For the complete graph with $n$ nodes, $\lambda_2 = n$, so the bound becomes $n$, which is accurate.  
> **username_0**: Oh, this is because of the Laplacian's property $\vec{x}^T L \vec{x} = \sum_{(i,j)\in E} (x_i - x_j)^2$? I see. Interesting. Thank you for this :)  
> **username_1**: @username_0, you can accept this answer (click the checkmark) if you feel that it answers your question.  
> **username_0**: I know. If by tomorrow there won't be another answer, this is the one I'll accept.  
> **username_6**: That property, and the fact that $\sum e_i = 0$, which is perpendicular to the first eigenvector ${\vec v}_1=\mathbf{1}$, so $\min_{\vec e} \frac{{\vec e}^T L{\vec e}}{{\vec e}^T{\vec e}} = \lambda_2$.  

---

### Answer by username_4 on 2011-04-09. Score: 3

For connected graphs, the imbalance is upper bounded by the diameter of the graph. In order to bound the imbalance $|w\_i - 1/n\sum\_k w\_k|$, we can rewrite each $w\_k$ as $w\_k - v\_1 + v\_1 - v\_2 + v\_2 - ... - v\_k + v\_k - w\_i + w\_i$ where $w\_k, v\_1,...,v\_k, w\_i$ is the shortest path from $w\_i$ to $w\_k$. Define $w\_{ki} = w\_k - v\_1 + v\_1 - v\_2 + v\_2 - ... - v\_k + v\_k - w\_i$. We can write
$$|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}|$$

Each $w\_{ki}$ is upper bounded by the length of the shortest path from $i$ to $k$ by your assumption that $w\_i - w\_j \leq 1$ for each $i,j\in E$. Therefore, we get the trivial bound:
$$|w\_i - 1/n\sum\_k w\_k| \leq \frac{(n-1)}{n} D$$

This might not actually be too far from optimal. I'm thinking of a complete $k$-ary tree where the nodes on each level have weight one higher than the weight of the previous level. A large fraction of the graph has the highest weight, $D+1$. So, the average should be skewed towards the top. As $k$ and $n$ get larger, I expect $m$ to get closer and closer to $D+1$ which means the imbalance should get closer and closer to $D$.

> **Comments:**
> **username_5**: As far as I can tell the construction sketched here can be made rigorous, to achieve imbalance as close to $D<\infty$ as is desired.  However, since the question does not specify what happens when vertices are not adjacent, an easier construction is a completely disconnected graph with vertex $0$ having weight $0$ and all other vertices with weight $k$.  This has average weight $k(n-1)/n$ which is also its maximum imbalance.  This clearly can be made arbitrarily close to $k$ by choosing a large enough $n$, and $k$ can be made as large as is desired.  
> **username_4**: @username_5: Good point.  The above answer assumes that the given graph $G$ is connected.  I'll edit it to make that clear.  
> **username_0**: I have added the "connected" constraint to my question, as this was what I had in mind. The answer here presents a bound on $||\vec{e}||_\infty$. Also, when I asked for the "worst" case, I had in mind that the graph would be fixed, and I'd try to find the worst case for that particular graph.  

---

