1
$\begingroup$

I'm looking for a solution the following graph problem for data analysis purposes.

Basically, I have a directed graph of $N$ nodes where I know the following:

  • The sum of the weights of the out-edges for each node ($O_i = \Sigma_{j=1}^N e_{i,j}$ where $i$ is a node and $e_{i,j}$ represents the weight of an edge directed from node $i$ to node $j$)
  • The sum of the weights of the in-edges for each node ($I_i = \Sigma_{j=1}^N e_{j,i}$ where $i$ is a node and $e_{i,j}$ represents the weight of an edge directed from node $j$ to node $i$).
  • Following from the above, $\Sigma O_i = \Sigma I_i$
  • No nodes have edges with themselves ($e_{i,i} = 0$)
  • All $e_{i,j}$ are positive

Represented as a weighted adjacency matrix, I know the column sums and row sums but not the value of the edges themselves. I've realized that there is not a unique solution to this problem. However, I'm hoping that I can at least arrive at a solution to this problem that minimizes the sum of the edge weights or maximizes the number of 0 edge weights or something along those lines (Basically, out of infinite choices, I'd like the most 'simple' graph).

I've thought about representing it as:

Min $\Sigma e_{i,j}$ s.t. $O_i = \Sigma_{j=1}^N e_{i,j} $, $I_i = \Sigma_{j=1}^N e_{j,i}$ and $e_{i,j} \ge 0$

I'm primarily using this for data analysis in Scipy and Numpy. However, using their constrained minimization techniques, I'll end up with approximately $2N^2-N$ constraints which I'm worried will be unfeasible for large data sets. Is there an analytic solution to this that I'm missing? Any way to simplify the minimization so I don't need that many constraints?

$\endgroup$
0
$\begingroup$

I can suggest a solution that gives a graph with $2N-1$ or less edges.

1) Take any pair of vertices $v_i$ and $v_j$ with $O_i>0$ and $I_j>0$ and create a directed edge $(v_i, v_j)$ between them.
2) Let the weight of the edge be $min(O_i, I_j)$. If $O_i < I_j$ then $v_i$ should have no other out-edges and $v_j$ should have additional in-edges with total weight $I_j-O_i$. Let now $O_i=0$ and $I_j=I_j-O_i$ (residual total weights of the out-edges for $v_i$ and of in-edges for $v_j$).
Do similarly for the case $O_i > I_j$.

So now we reduced the quantity of vertices with non-zero total out-edge (or in-edge) weight by 1.

3) Repeat steps 1 and 2 until there is only one vertex with non-zero residual total out-edge weight (or non-zero residual total in-edge weight). Connect it with all remaining vertices with non-zero residual total in-edge weight.

Now you have a graph with $2N-1$ edges at most. It can be not the most 'simple' graph but at least it's quite simple/sparse. (A possible simple and obvious optimization is to try to pair vertices with $O_i = I_j$ every time.)
It seems the algorithm can be implemented in linear time.

$\endgroup$

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.