Online Dating in a Non-Bipartite System
Online dating has often been considered a common application of a perfect matching algorithm in a bipartite system. However, assuming the network is bipartite would be heteronormative and cisnormative; in reality, you cannot make two distinct groups none of which are neighbors with anyone in their group if the sample size is large enough. I did some research on what I thought would be a more complex dating model: an exclusively homosexual one in which all of the participants are of the same gender (if they were not, then there would just be two unconnected graphs).
In the article attached, the researchers used a speed-dating model which I had to simplify to ignore the extra math they did to account for different rounds of dating. Here, everyone starts out as an unconnected node, and connections are formed as they meet each potential match. After they meet and talk (or both swipe right if it is online), the hosts run their matching algorithm and assign matches. Every couple that is a match gets a weight assigned to their connection based on how strong of a match they were. In the article, these weights fell in the range [1, infinity], with 1 being the least of a match. Although there is no strict upper bound, it gets expectedly harder to reach higher numbers very quickly. Instead of creating a regular perfect matching problem in a bipartite graph, we now want to solve a weight-perfect matching problem. That is, given our graph, we want to create a maximum weight edge subset–a subset graph of maximum weight such that each node has exactly one edge. In other words, we want to assign couples such that we generate the highest possible number of matches of the maximum total weight. If everyone gets a match, we have a perfect matching.
Lemon’s matching algorithm can be used to solve this in O(n m log(n)) where n is the number of nodes and m is the number of edges. It solves this as a linear programming problem that maximizes the sum of the product of the weights and the edges (1 or 0 whether they exist) in the final subset. In a linear programming model, you generally have constraints that must be satisfied in addition to this optimization. Here, the authors list three constraints. First, for every node in V, the set of all nodes, that node must have exactly 1 edge. They formulate this by saying the sum of all edges for a given node must be 1. Next, they say that for every subset of nodes of an odd cardinality (odd number of nodes in the subset), the sum of the number of edges that have both their ends in that subset must be even, and must be less than or equal to half the number of nodes in that subset. The formula for this constraint is SUMsub(e⍷gamma(B))[Xe] < (|B|-1)/2 for each set B in the set of all odd cardinal subsets. e represents a single edge, gamma(B) is the set of edges with both ends in B, and B is each odd cardinal subset. The math is written much more neatly if you click the link. The last constraint just specifies that we are only dealing with positive values. The linear program proceeds to maximize the weights in the perfect match subset. That is, this solution optimizes utility, making the whole community of singles happiest, rather than necessarily prioritizing the best matches at the cost of others not having one.
Resources:
https://i11www.iti.kit.edu/_media/teaching/theses/sa-strasser-10.pdf
http://lemon.cs.elte.hu/pub/doc/latest-svn/a00388.html