[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [igraph] Transitivity question on directed graphs
From: |
Tamas Nepusz |
Subject: |
Re: [igraph] Transitivity question on directed graphs |
Date: |
Wed, 10 Mar 2010 22:35:31 +0000 |
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