A random dot product graph is a mathematical model of social networks. The vast majority of the work I’ve done has been theoretical. But this was driven by an application. 

When I say “graph,” I don’t mean an XY axis and a curve or a pie chart. I mean a network. You have nodes and connections. A graph is the mathematical abstraction of a network. There are ways to make a random graph, and one way is: for every pair of vertices you flip a coin—heads you put in the edge, tails you don’t. That’s known as the Erdős–Rényi Random Graph, a classic thing from the 1950s. It’s a very interesting, important area of mathematics, but it doesn’t look anything like a social network.

On one hand, the goal was to create something that looks like a social network and, on the other hand, something you could do mathematical reasoning on. In other words, can we prove any theorems? Can we say anything about these things? If you create some really complicated definition that’s so hard to work with that you can’t prove anything, that doesn’t help. So this was an attempt to get something in the sweet spot—realistic, maybe simplistic, because we want to actually prove something.

The idea was to imagine that each person is a vector, and by vector I just mean a list of numbers, say a list of 10 numbers. Each component of that vector—this is a story, not actually how we do it—represents something. So we might have one entry in the vector about mathematics. Since you and I both like mathematics, we have a large number there. The next thing might be about singing. I do not like to sing at all; maybe you love to sing. So I may have a 0 where you have a 1. Bicycle riding—I’ve got 0.9 and you might have 0.3. We go through all these categories, and every person in the world has a vector.

Now, how likely is it for two people to be friends? The answer is: the more their interests overlap, perhaps the more likely they’re going to be friends. The way to measure that overlap is to take the matching entries and multiply those two numbers. You do all those products and then add everything up. That’s the dot product of those vectors.

In a random dot product graph, we imagine that each person draws a vector at random, and then the likelihood that they’re friends is proportional to the dot product. That’s a very broad model. There are a couple of different variations, but that’s the big picture.

One of my students wrote her dissertation about this, and what we saw is that the properties of these random dot product graphs look like some of the properties of social networks. In particular, there’s a correlation. If I’m a friend with you, and you’re a friend with somebody else, that probably means I’m more likely to be friends with that third person. So there’s this kind of clustering effect, and we’ve got that. There are other basic properties observed in real social networks that are exhibited in this random dot product graph model. So we have a reasonable model.

There’s another thing I worked on with a different student. We asked: let’s start with a whole bunch of people—can we model that community as a random dot product? Instead of creating an artificial network, try to take this model and stick it onto a real one.

This was a long time ago, so we didn’t really have any good data sets, but we found one called Correlates of War. The data on this site show which nations had treaties with which other nations over time. We imagined that the nodes of the social network are countries, and there’s an edge between two countries if they had some sort of military alliance, some sort of treaty.

From that, using a technique, we said: what are the best vectors that could model that particular network? And so we did that every year over a course of a century, and what was really interesting—it was sort of a validation of this idea—we looked at the angle of the vectors between Britain and France. At first, they were at 90 degrees, which meant they had nothing in common. They weren't friends. And then over time, those vectors came closer together, and then all of a sudden they were at right angles again. That was during World War II, when France was under German occupation, was Vichy France, and they were not friends with Britain. Afterwards they aligned, and then after the creation of the European Economic Community, which predated the EU, they became perfectly aligned. By looking at the angle between the two vectors, it told the story of the relationship between Britain and France. 

I stopped working on this quite a while ago, but some of my colleagues have been working on it, especially my colleague Carey Priebe in my home department. He took this idea and, for example, looked at connectomes in the brain—not down to the individual neurons, but regions. And quite frankly, I don't really know too much about it, but he was able to say that he could infer things about brains by looking at a random dot product model of their connectomes. And they've used it for other things also. 

There's vertex nomination. You have a large network of people, some of whom are known bad actors. Can you guess from this who other bad actors might be? And there is some success in using the random dot product method to do that as well. 

Ongoing thread. More from Edward Scheirneman to follow.