Tactical Information Systems
Biometric Identification Software
SERVER.png

Identity & Technology

Tactical Information Systems Blog

Graphs are Everywhere

Graphs are everywhere, right? Like this graph showing the correlation between the decline in pirates and the rise of global warming.

pirates.png

Well, I’m not really talking about these kinds of graphs, I am talking about graphs. And you see part of the dilemma already – the term graphs can refer to things like pie charts and bar graphs, but also to a different type of graph that shows connectedness between things. These are sometimes called network graphs, but not often enough. Usually, they are just called graphs and you have to figure it out by context. So to establish the context of this blog post, I am only talking about graphs that connect things.

Wikipedia uses the mathematical description of a graph as:

simple-graph-definition.png

The bolding is my emphasis. I believe this is a very loose interpretation of the term “common sense”. Maybe common sense for a mathematician, but I expect if you aren’t one of the 0 mathematicians who read this blog, this definition doesn’t do much for you. So, my True Common Sense™ definition of a graph is this:

A graph is a map of things that are connected to each other.

Sure, you can’t use it for proofs, but I think it works much better in terms of basic understanding. So, let’s look at some examples. Here’s a simple one:

simple-graph.png

You can read this in simple, plain English as “The person Alex likes the TV show Game of Thrones.” This is pretty straightforward, and although it looks very English-like, it can also be turned into a mathematical representation that can be used by a computer. The blue circles are called nodes, and the lines are called edges. They can be anything you want them to be, so they can map any kind of relationship.

Let’s expand this a bit:

medium-graph.png

We’re expanding out this network to show a new person, Peter Dinklage, who acts in the TV show Game of Thrones. We’ve created a new type of edge here as well. So, what can we do with this very small network? Maybe we can infer something like this:

complex-graph.png

Can we infer Alex likes Peter Dinklage? Maybe. We can’t know it, for sure. There are plenty of counter-examples where people may like a show but hate a particular actor. (It so happens that I think Peter Dinklage is awesome). But there is a decent chance that if Alex likes Game of Thrones, he might like other shows that feature Peter Dinklage.

Now, if you have been waiting patiently for how this applies to Mobile Dating, here is where we get into that. I’m going to throw another person into the mix:

xtra-complex-graph.png

Donna is a potential mate for Alex, and maybe we want to recommend that he check her out as a potential date. But it turns out she hates Game of Thrones. Should that kill the recommendation? Well, it depends on many factors. How important are TV shows for compatibility? Well, even that depends. Here is one potential algorithm (recipe) we could use to evaluate this:

  1. If a person registers a lot of LIKES for TV shows, then TV is an important thing to them
  2. If a person registers a small number of LIKES for TV shows, then TV isn’t important to them
  3. If Person A and Person B both LIKE a large number of different shows, they may not be very compatible
  4. If Person A and Person B both LIKE a large number of the same shows, they may be compatible
  5. If Person A likes a lot of TV shows and Person B doesn’t, they may be compatible

In this example, Donna is my wife. She hates Game of Thrones, but she doesn’t watch more than one or two shows a year. I watch more TV, but it isn’t something we do together, so it all works out.

This example is very, very trivial compared to real-world graph analysis done by giants such as Facebook, Amazon, Netflix, etc., where a graph representing a single person might have thousands of connected nodes. However, it does illustrate the expressiveness of graphs – they can be used to represent anything. However, they aren’t magic. Computers can do the heavy lifting of storing and analyzing the connections, but it takes human expertise and judgment to guide the analysis itself.

So how does this apply to Mobile Dating? Well, with mobile dating, you don’t have the screen real estate or attention span in order to have people fill out complex profiles of what they like. So you have to leverage platforms that can provide that data for you, like Facebook. If you use Facebook login, you can get access to a user’s likes. For example, here is a snippet of my likes, returned from the Facebook API.

{
      "category": "Community", 
      "name": "My stealthy freedom", 
      "created_time": "2014-05-22T16:25:59+0000", 
      "id": "499340400192384"
    }, 
    {
      "category": "Author", 
      "name": "Cormac McCarthy", 
      "created_time": "2014-04-11T02:40:19+0000", 
      "id": "151000201600745"
    }, 
    {
      "category": "Community", 
      "name": "Open Coffee Austin", 
      "created_time": "2014-03-31T02:19:30+0000", 
      "id": "135556399838401"
    }, 
    {
      "category": "Movie", 
      "name": "District 9", 
      "created_time": "2014-03-15T04:42:21+0000", 
      "id": "76221618220"
    }

This provides a ready-made set of nodes that can be connected between people, looking for similarities. Facebook helpfully provides categories that we can use in order to understand the relative importance of the likes. “Community” connections are probably stronger indicators of connection than “Movie” “Religion” indicators are likely to be very important. You can also see how graphs are used by Amazon.com:

bought-together.png

This is only scratching the shallowest surface of what can be done with Graph Theory. Some other ideas might be:

  • Determining whether a potential new user fits into a particular dating community/niche
  • Suggesting things to talk about on a first date
  • Determining patterns of behavior on a dating platform to understand intent (casual vs serious daters)
  • Determining personality types (introvert vs extrovert)
  • Finding “friend of a friend” connections

In summary, graphs are powerful enough to represent pretty much everything about our complex world, social connections, preferences, actions, and even things we might not know about ourselves. With modern computing power, graphs of 100’s of millions of nodes are easily achievable. This can provide a powerful back-end for a limited mobile dating platform, but it will take some work to understand the implications of the graphs themselves. If you want to learn more, give us a shout – we love talking graphs and how people are using them.

Note: This blog entry is based on a presentation Dr. Kilpatrick gave at the iDate 2014 conference in Beverly Hills. The goal was to help mobile dating companies use this technology in their own mobile fraud prevention efforts.