Here's my precise situation: I have a graph with nodes $V$ and edges $E$, and the nodes have some non-negative integer weights $w_i$. In one step of the protocol, I am now allowed to move weight around among nodes. This is expressed through a flow $f$ defined on the edges: $f(i,j)$ tells me how much weight I transfer from $i$ to $j$.The flow cannot create new weight. The flow must be integer.$f(i,j)$ is allowed to be larger than $w_i$, but after the entire flow has been applied all the $w_i$ must be non-negative again.Let $\Delta_i$ be the total change in the weight on node $i$, with the sign convention such that $\Delta_i$ is positive if more tasks leave node $i$ than arrive at $i$. An upper bound on $\Delta_i$ is $w_i$, by virtue of the third condition on the flow. My question now is: Is there also a lower bound? A naive lower bound for each $\Delta_i$ would be given by the sum of the $\Delta_j$ for all neighbors of $i$, but I wonder if some network- and graph-theory can find better bounds?If a good lower bound on the $\Delta_i$ is not possible, maybe there is a good \emph{upper} bound on the quantity $$\sum_{i \in V} \Delta_i^2$$?
Given a network flow, are there bounds on the change in weight on nodes?
ds.algorithms;graph theory;application of theory;network modeling
I think you're using a confusing sign convention, but I'll stick with it.  It's pretty easy to see that for any connected graph you can have all weight flowing into a single vertex (unless I'm misunderstanding something), so the lower bound you'll get is $$\Delta_i\geq -\sum_{i\in V}w_i.$$Things won't really be better for bounding the square.  For example, if your graph is a star in which every leaf has $w_i=1$, then $$\sum_{i\in V}\Delta_i^2 = (|V|-1)+(|V|-1)^2.$$You can't get a neighbourhood restriction, either, because you can take the example of a $k$-ary tree in which every leaf has weight 1 and all the weight goes to the root.What you can get, however, is the possibly useful bound $$\sum_{i\in V}{|\Delta_i|} \leq 2\sum_{i\in V}w_i.$$To see this, just note that when charge leaves a vertex you'll count it twice.