Graph Theory (or, alternate ways to rank the Big Ten this year)
Football is not transitive. What do I mean? Simple. If Team A beats Team B, and then Team B beats Team C, it does not mean that Team A will beat Team C. We all know this.
Proof of non-transitivity this year comes in the Big Ten. Let's look at the Big Ten Graph. The graph is simple to understand: each team is a node (circle), and there is an line connecting each team that played another team. The line is actually an arrow, making this a directed graph, in the obvious form: if there is an arrow from Team A's node to Team B's node, it means Team A beat Team B. Here is the graph:
The Victory Graph (Click on it for full size)
There are lots of fun cycles to find in the graph. For example, Minnesota beat Iowa, who beat Michigan State, who beat Minnesota. See how many of these three-node cycles you can find (there are plenty). Or not, depends how bored you are at work. There are bigger ones too: for example, Michigan beat Indiana who beat Purdue who beat Minnesota who beat Iowa who beat Michigan State who beat Wisconsin who beat Michigan. And it goes on.
The most amazing fact from the graph, thanks to Indiana finally getting a win, is that the graph is strongly connected. In graph terminology, this means you can get from any node in the graph to any other node, simply by following arrows, for all pairs of nodes. This really shows how non-transitive football is: you can use this graph to say any team "transitively beat" any other team, at least in the Big Ten this past year. For example, Indiana beat Purdue, who beat Minnesota, who beat Iowa, who beat Michigan State, who beat Wisconsin, who beat OSU. If football were transitive, Indiana "beat" OSU! Except when they played, of course.
One interesting metric for each pair of teams (A, B) is the shortest path to victory for A over B. Some of these "shortest paths to victory" are easy to find: for example, it is unfortunately the case that there is a short and quite direct path from OSU (at the top) to Michigan. Some are harder to see: for example, see if you can find the path where Michigan "transitively" beats OSU. This "shortest path" is actually long: 6 steps (the answer is at bottom).
We can then use this graph to order the teams a different way: what is the shortest path between a team and every other team in the Big Ten? Lower is better here: a path of length 1 means Team A directly beat Team B, whereas a path of length 2 between Team A and Team B means that Team A beat Team C who in turn beat Team B. Here is the full summary of the shortest paths between all pairs of Big Ten teams:
OSU | Illinois | Ind | Wisc | Purdue | Minn | PennSt | Iowa | Mich | MichSt | NorthWest | AVERAGE | |
OSU | 0 | 1 | 1 | 3 | 1 | 1 | 1 | 1 | 1 | 2 | 2 | 1.4 |
Illinois | 5 | 0 | 1 | 4 | 1 | 2 | 1 | 2 | 2 | 3 | 1 | 2.2 |
Indiana | 6 | 3 | 0 | 5 | 1 | 2 | 4 | 3 | 4 | 4 | 2 | 3.4 |
Wisconsin | 1 | 2 | 1 | 0 | 1 | 1 | 2 | 1 | 1 | 2 | 1 | 1.3 |
Purdue | 5 | 2 | 2 | 4 | 0 | 1 | 3 | 2 | 3 | 3 | 1 | 2.6 |
Minnesota | 4 | 1 | 2 | 3 | 2 | 0 | 2 | 1 | 2 | 2 | 2 | 2.1 |
PennState | 5 | 2 | 1 | 4 | 2 | 1 | 0 | 2 | 1 | 3 | 1 | 2.2 |
Iowa | 3 | 2 | 1 | 2 | 2 | 2 | 1 | 0 | 1 | 1 | 2 | 1.7 |
Michigan | 6 | 1 | 1 | 5 | 1 | 2 | 2 | 3 | 0 | 4 | 2 | 2.7 |
MichState | 2 | 1 | 2 | 1 | 1 | 1 | 1 | 2 | 1 | 0 | 1 | 1.3 |
Northwestern | 4 | 2 | 1 | 3 | 2 | 1 | 2 | 1 | 2 | 2 | 0 | 2.0 |
You can then use these to create a new ranking among teams, based on their average shortest path to victory:
1. | Wisconsin | 1.3 |
1. | MichState | 1.3 |
3. | OSU | 1.4 |
4. | Iowa | 1.7 |
5. | Northwestern | 2.0 |
6. | Minnesota | 2.1 |
7. | PennState | 2.2 |
7. | Illinois | 2.2 |
9. | Purdue | 2.6 |
10. | Michigan | 2.7 |
11. | Indiana | 3.4 |
This ranking kind of makes sense, too. If you beat a lot of teams directly, then you will have an average near 1 (note that even undefeated teams will average higher than 1, because teams don't all play each other). If you only beat bad teams, who in turn only beat other bad teams, your average will be higher. Thus, Michigan does poorly in this comparison; Minnesota does better because they beat Iowa, who actually beat some good teams (like MSU). Only Indiana fares worse than our boys in Blue.
You can also prune the graph to arrive at some interesting findings. For example, let's say we remove all edges where one team didn't resoundingly beat the other team. I will arbitrarily deem a win as a "strong" win when one team beats the other by more than 10 points. The graph now looks like this:
The Strong Victory Graph (Click on it for full size)
Wow, that is a much different graph! The first thing that stands out: there are no cycles in this graph. That means that if Team A "strongly beat" Team B, and Team B "strongly beat" Team C, that Team C didn't "strongly beat" Team A. There are no cycles here my friends.
We can also then use the "Strong Win" Graph to compute a new ranking. For each strong win, you get a +1, and for each strong loss, you get -1. Here are the teams, ranked by this new "Strong Win" scoring system:
Rank | Team | StrongWins | StrongLosses | Score |
1. | Wisconsin | 6 | 0 | 6 |
2. | OhioState | 6 | 1 | 5 |
3. | MichState | 3 | 1 | 2 |
3. | Iowa | 2 | 0 | 2 |
3. | Illinois | 4 | 2 | 2 |
6. | PennState | 3 | 3 | 0 |
7. | Michigan | 1 | 3 | -2 |
8. | Purdue | 1 | 4 | -3 |
8. | Northwestern | 0 | 3 | -3 |
10. | Indiana | 0 | 4 | -4 |
11. | Minnesota | 0 | 5 | -5 |
This is actually a pretty reasonable ranking I think. Wisconsin is on top, because they beat the tar out of everyone (almost). Michigan State doesn't fare nearly as well as Wisconsin and OSU, because they had many close wins and one game where they were trounced (Iowa). Michigan ends up behind Illinois and Penn State in this ranking, because those two teams had a number of big wins, where Michigan only had one (Purdue, and barely "strong" at that).
Anyhow, that's a short look at how graphs can help us rank teams in different ways. And if you didn't like it, well, remember that I Hate Everything too.
[EDIT: Some people asked how I generated the graphs. All automated, given an input of games and scores. Some python code to compute shortest paths between nodes (there are some fairly standard algorithms for doing this) and then Graphviz to layout the graphs automatically. It would be easy to do this for any set of games.
One other note: the real point of the "Strong Win" graph is how silly it is that score differential is ignored in current computer rankings. A big score difference is a useful metric, and one that I think is better than many other simple ways of comparing teams. One could likely come up with a slightly more nuanced "Strong Win" definition (say, win by 10 and outgain the other team by some threshold number of yards); this was just a simple and easy way to start.]
Appendix:
The path for "transitive victory" of Michigan over OSU: Michigan beat Illinois who beat Northwestern who beat Iowa who beat Michigan State who beat Wisconsin who beat OSU. Ugh, it is really hard for us to beat OSU, apparently.
Comments