Beat me to it. Yeah, it seems that Hodge decomposition of graph flows is the right tool here.
The papers make it sound a bit scary, so I’ll try to explain it simpler: imagine a complete graph on N vertices, two of which are marked A and B, and a flow F on that graph, which is nonzero on the edge from A to B and zero everywhere else. We can write it like this, where ∗ means “any vertex except A or B”:
F(A,B) = 1
F(A,∗) = 0
F(∗,B) = 0
F(∗,∗) = 0
Then F can be written as the sum of these two flows C and G:
The reason for this choice is that C is a “cyclic” flow, which means there are no sources or sinks—the net contribution of each vertex is 0. And G is a “gradient” flow, which means there’s a function P (“potential”) such that G(X,Y) = P(X)-P(Y) for any two vertices X and Y:
P(A) = 1/N
P(B) = -1/N
P(∗) = 0
This construction is easy to generalize: since every flow on our graph is a linear combination of flows like F that are nonzero on only one edge, and the conditions on cyclic and gradient flows are also linear, we can rewrite any flow as a sum of cyclic and gradient flows and find the potential function up to a constant. For example, if we start with a cyclic flow, then G will be everywhere zero and P will be constant.
A more complex version of this also works for non-complete graphs. For any flow on any graph, the decomposition into cyclic and gradient flows is unique, and the potential function is unique up to a constant per each connected component of the graph.
In principle, this idea lets us infer complete and consistent preferences from incomplete and/or inconsistent preferences. Apparently it has been used in practical problems, like the Netflix prize. I’d love to hear from people who have experience with it.
Beat me to it. Yeah, it seems that Hodge decomposition of graph flows is the right tool here.
The papers make it sound a bit scary, so I’ll try to explain it simpler: imagine a complete graph on N vertices, two of which are marked A and B, and a flow F on that graph, which is nonzero on the edge from A to B and zero everywhere else. We can write it like this, where ∗ means “any vertex except A or B”:
Then F can be written as the sum of these two flows C and G:
The reason for this choice is that C is a “cyclic” flow, which means there are no sources or sinks—the net contribution of each vertex is 0. And G is a “gradient” flow, which means there’s a function P (“potential”) such that G(X,Y) = P(X)-P(Y) for any two vertices X and Y:
This construction is easy to generalize: since every flow on our graph is a linear combination of flows like F that are nonzero on only one edge, and the conditions on cyclic and gradient flows are also linear, we can rewrite any flow as a sum of cyclic and gradient flows and find the potential function up to a constant. For example, if we start with a cyclic flow, then G will be everywhere zero and P will be constant.
A more complex version of this also works for non-complete graphs. For any flow on any graph, the decomposition into cyclic and gradient flows is unique, and the potential function is unique up to a constant per each connected component of the graph.
In principle, this idea lets us infer complete and consistent preferences from incomplete and/or inconsistent preferences. Apparently it has been used in practical problems, like the Netflix prize. I’d love to hear from people who have experience with it.