[igraph] Transitivity question on directed graphs

[Ken Williams]

Hi,

I'm hoping someone can help with a question I have about transforming
directed graphs.

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.

I start out with a raw graph like this, representing the number of rides
each person (row) has given each other person (column):

> get.adjacency(gr, attr="weight")
   J W  K R
J  0 0  0 0
W 22 0  4 8
K 22 2  0 4
R 22 2 10 0

As a first step I can reduce that by subtracting edges that point in
opposite directions:

> a <- get.adjacency(gr, attr="weight")
> a <- a - t(a)
> a <- a * (a > 0)
> gr <- graph.adjacency(a, weighted=TRUE)
> get.adjacency(gr, attr="weight")
   J W K R
J  0 0 0 0
W 22 0 2 6
K 22 0 0 0
R 22 0 6 0

After that, there's no obvious (to me) general way to proceed, but what I'd
like to end up with is a minimal graph (minimum number of edges, and
probably minimum sum of [squares of?] edge weights) like the following:

   J W K R
J  0 0 0 0
W 30 0 0 0
K 14 0 0 0
R 22 0 0 0

Or other alternatives:

   J W  K R
J  0 0  0 0
W 30 0  0 0
K 36 0  0 0
R  0 0 22 0

   J W  K R
J  0 0  0 0
W  0 0 30 0
K 66 0  0 0
R  0 0 22 0


The transformation must preserve the quantity indegree-outdegree for all
nodes:

> structure(graph.strength(gr, mode="in") - graph.strength(gr, mode="out"),
names=V(gr)$name)
  J   W   K   R 
 66 -30 -14 -22 

Anyone have any suggestions?

Thanks.

-- 
Ken Williams
Sr. Research Scientist
Thomson Reuters
Phone: 651-848-7712
address@hidden