10
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ interesting question. is there any particular application ? $\endgroup$ – Suresh Venkat Apr 8 '11 at 21:51
  • 2
    $\begingroup$ @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? $\endgroup$ – Lagerbaer Apr 8 '11 at 22:26
  • $\begingroup$ Do you happen to have an example of a graph where your simple diameter bound is much too loose? $\endgroup$ – mhum Apr 9 '11 at 4:45
  • $\begingroup$ 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. $\endgroup$ – Lagerbaer Apr 9 '11 at 14:50
  • $\begingroup$ 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$. $\endgroup$ – Artem Kaznatcheev Apr 11 '11 at 6:50
8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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)? $\endgroup$ – Lagerbaer Apr 9 '11 at 20:51
  • 1
    $\begingroup$ 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. $\endgroup$ – John Moeller Apr 9 '11 at 20:58
  • $\begingroup$ Let me offer another example. A dumbell graph with two cliques has very low conductance, but its imbalance is bounded by 2. $\endgroup$ – John Moeller Apr 9 '11 at 21:11
  • $\begingroup$ 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. $\endgroup$ – Lagerbaer Apr 9 '11 at 21:13
  • $\begingroup$ 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$. $\endgroup$ – Lagerbaer Apr 9 '11 at 21:15
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – András Salamon Apr 9 '11 at 11:14
  • $\begingroup$ @András Salamon: Good point. The above answer assumes that the given graph $G$ is connected. I'll edit it to make that clear. $\endgroup$ – Nicholas Ruozzi Apr 9 '11 at 11:55
  • 1
    $\begingroup$ 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. $\endgroup$ – Lagerbaer Apr 9 '11 at 14:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.