Re: [igraph] Transitivity question on directed graphs

[Tamas Nepusz]

Hi,

> I have a graph that represents payments that need to be made among a group
> of people (in this case, carpoolers who need to settle up for the number of
> rides each person has given another person).  I need to simplify that to
> minimize the number of person-to-person payments.
Hmmm... I can think about a very simple greedy solution that might not generate 
the optimal solution, but my intuition is that it isn't too far away from it in 
the vast majority of cases. You only need the differences between the 
in-strength and the out-strength of the vertices:

>> structure(graph.strength(gr, mode="in") - graph.strength(gr, mode="out"),
> names=V(gr)$name)
>  J   W   K   R 
> 66 -30 -14 -22 
First, I'd say that people with a positive "balance" should only receive 
incoming payments and people with negative "balance" should only pay to others 
in an optimal solution. Keeping that in mind, one can do the following:

Select the two people with the largest and the smallest balance (e.g., J and W 
in the above case). One of them will be the payer, the other one will be the 
payee, and the amount paid will be the minimum of the absolute values of the 
two balances. By adding this payment to the payment graph, at least one of the 
two people will have zero balance after the payment as we have chosen the 
amount of money to be paid this way. Therefore, in each step, the number of 
people with non-zero balance will decrease by at least one. Repeat the above 
step until no one has a non-zero balance. This procedure will terminate in at 
most N-1 steps, where N is the group size.

For instance, the procedure will proceed as follows in the above example:

1. J pays 30 to W. The balances are as follows: J = 36, W = 0, K = -14, R = -22
2. J pays 22 to R. The balances are: J = 14, W = 0, K = -14, R = 0
3. J pays 14 to K. Everyone's balance is at zero, so the algorithm terminates.

-- 
Tamas