Dating Sites and the Split-complex Numbers

In this post I will present the problem of recommendations in dating websites and its relation to the split-complex numbers.

The split-complex numbers are an extension of the real numbers similar to the complex numbers. Instead of including an imaginary number i such that i² = −1, the split-complex numbers include an imaginary number j such that j² = +1. The split-complex numbers are used much less often than the complex numbers, because they have a few weird properties.  For instance, every complex number z different from zero has an inverse, but the same is not true for the split-complex numbers. However, the split-complex numbers can be used to model dating websites:

Imagine a dating website where persons can rate each other’s profile.  We assume, for the sake of the argument, that men will only be interested in women and women only in men.  A rating can therefore only exist between a man and a woman and therefore, the rating network is bipartite.  Also, we will assume that ratings are always reciprocal, i.e. that rating edges are undirected. However, we may still be interested in links between persons of the same gender as a measure of similarity. For instance, two women are similar if they have rated the same men similarly.  Therefore, we really need two kinds of relationships in this network:  like and is-similar.  Let us represent these two possible values by e_like and e_is-similar.

Now, a very common way to predict links in a network is by the process of triangle closing.  The main idea of triangle closing is that when two edges are touching each other, we can predict a third edge such that a triangle is formed. If the network is unweighted, then we can just count the number of triangles that we would close by adding a specific edge.  If the network contains positive and negative edges (e.g. friends and foes, represented by +1 and −1), then we have to compute the product of the weights of two touching edges:  This is the multiplication rule represented by the phrase “The enemy of my enemy is my friend”, because −1 · −1 = +1.  In the case of a dating site, we can formulate the following natural triangle closing rules:

  • Two persons that like the same person are similar.
  • Two persons that are similar to the same person are similar.
  • A person similar to a person that likes a third person will like that third person.

These rules can be expressed mathematically in the following way:

e_like · e_like = e_is-similar

e_is-similar · e_is-similar = e_is-similar

e_like · e_is-similar = e_like

We thus have to find values of e_like and e_is-similar that solve these equations, and in which both constants are nonzero. A trivial solution is given by e_like = e_is-similar = 1. However, this trivial solution is not satisfactory, since we want the relationships like and is-similar to be different. From the second and third equations, we can derive that e_is-similar = 1.  Therefore, e_like is a number different from zero and from 1 that squares to 1.  Since no real number has these properties, we have to use a non-real value for e_like such that e_like² = 1. This construction corresponds to the split-complex numbers, where the imaginary unit j squares to one:

e_like = j

e_is-similar = 1

Our three requirements then correspond to the identities j · j = 1, 1 · 1 = 1 and j · 1 = j that hold in the split-complex numbers.  Thus, the split-complex numbers can be used to model bipartite relationships.

Split-complex number plane

The split-complex numbers were introduced by William Kingdon Clifford in 1873. They can be defined formally as the set _s = {a + b j | a, b ∈ ℝ}. Note that there is no established notation for the set of split-complex numbers. The defining identity of split-complex numbers is j² = +1. From this, other results can be derived. Unlike the complex numbers, ℂ_s is not a field. Instead, ℂ_s is a commutative ring, i.e. all field axioms are valid except for the existence of the multiplicative inverse, which does not exist for numbers of the form a ± a j. As a result, products of two nonzero numbers can be zero, e.g. (1 + j) (1 − j) = 0. Due to these defects, the split-complex are used much less than complex numbers. Split-complex numbers are also called hyperbolic complex numbers because they can represent hyperbolic angles. In the context of special relativity for instance, numbers of the form a + b j with a² − b² = 1 are used to model Lorentz boosts. Other applications of hyperbolic angles are squeeze mappings in geometry, giving them the alternative name hyperbolic numbers.

Algebraic graph theory

When working with graphs, a common approach is algebraic graph theory, in which a graph is represented as a matrix. For instance, a social network made from n persons will be represented by a n×n matrix in which each entry is 1 when two persons are connected and 0 otherwise.  In other words, we will get a matrix A such that A_uv = 1 when the persons u and v are connected and A_uv = 0 otherwise. A very useful property of the adjacency matrix is that it can be used to count the number of paths between any nodes in the vertex. Let k ≥ 1 be an integer, then the power A^k contains, for each pair of persons (u, v), the number of paths between person u and person v in the network.

In the split-complex approach however, we will use +j as the edge weight when two persons like each other and −j when they don’t like each other. As a result, the matrix A will contain A_uv = ±j when persons u and v are connected. Due to the multiplication rule of split-complex numbers, the power A^k contains, for each pair (u, v), the number of paths between u and v, separated into paths with an even number of like edges in the real part and paths with an odd number of like edges in the imaginary part. This is due to the fact that j^k = 1 when k is even and j^k = j when k is odd.

Equivalently, a split-complex number a + b j can be represented by the following 2×2 matrix (I’m using Matlab notation):

a + b j = [ a b ; b a ]

In this representation, the addition and multiplication of split-complex numbers corresponds to the addition and multiplication of 2×2 matrices. The units 1 and j then correspond to

1 = [ 1 0 ; 0 1]

j = [ 0 1 ; 1 0 ]

Using this representation, the split-complex adjacency matrix A can be reordered to give the matrix

A = [ 0 A_orig ; A_orig^t 0 ]

where A_orig is the original 0/1 adjacency matrix, and 0 is a zero matrix. In fact, this is equivalent to considering the developed form of A as the biadjacency matrix of the bipartite double cover of the original graph!

Phew!  That’s enough for now.  Here’s the main reference for this work:

[1] Jérôme Kunegis, Gerd Gröner, Thomas Gottron. Online Dating Recommender Systems: The Split-complex Number Approach, Proc. Workshop on Recommender Systems and the Social Web, 2012. (Slides from the RecSys’12 conference)

This is the original paper by Clifford that introduced the split-complex numbers:

[2] William K. Clifford. Preliminary sketch of quaternions. Proc. London Math. Soc., 4(1):381–395, 1873.

More about the split-complex numbers:

[3] Joseph Hucks. Hyperbolic complex structures in physics. J. Math. Phys., 34(12):5986–6008, 1993.

[4] Garret Sobczyk. The hyperbolic number plane. The College Math. J., 26:268–280, 1995.

And finally, here’s a dataset from a dating website:

[5] Libimseti.cz network dataset, KONECT – the Koblenz Network Collection, July 2012.

Advertisements

2 thoughts on “Dating Sites and the Split-complex Numbers

  1. Pingback: ACM Recommender Systems #Recsys2012 | Data Science London

  2. Pingback: RecSys 2012: few things i remember | syslog

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s