Directed Games Graph Pathcounts

Arrows and Loops: Untangling the Directed Games Graph

© Copyright 2013, Paul Kislanko

One of my favorite tools for analyzing performance against schedules is the Games Graph. Each team is a vertex and games played are the edges. The graph is connected when there is a path from every vertex to every other vertex. The diameter of the graph is the minimum number of edges required to make the connections - it is the longest shortest path between two vertexes.

Ratings systems work with the Directed Games Graph in which the edges become arrows that indicate the results of the game, for instance pointing from the winning team's vertex to the losing team's. The directed graph cannot be said to be "connected" as long as there are team pairs for which there is no one-way path from one's vertex to another's, as is the case when there is more than one undefeated (or winless) team.

Instead, we might define the radius of the directed graph to be the smallest pathlength for which the most teams with at least one win are connected to teams with at least one loss. Until every team with at least one win is connected to every team with at least one loss this is usually a fairly large number: through games of 18 October it is 22 for the 125-team FBS subdivision and 33 for all of division one (252 teams.)

The challenge for rating systems is to derive from the directed games graph a linear ordering of vertices based upon the connections. There's a lot of raw material, and as we shall see the schedulers do not make it easy.

The first step is to find the radius of the directed games graph. At this writing, it is 27, meaning that it takes 27 "beats" in an A beat B beat... chain to connect the last team-pair that can be connected.

If we pick a vertex (team) we can characterize its position within the graph by ordering each vertex (including itself) according to the difference in number of paths from each vertex to the chosen one.

Now, there are lots of ways to combine such ordered lists, and no one "right" way so I chose four for this analysis.

Self	This is just where a team ranks in the list based upon its position in the graph. Any undefeated team will rank itself first (since no team has more than zero win paths to it) as well as any other team to which it has no win path. Hence, even though Tennessee has three losses, nine undefeated teams do not have a path to the Vols' vertex so rank them tied for first.
Buck	The "Bucklin Rank" as used here is the best rank for which a majority of the voters (teams) rank the team at least that highly. Since there are 252 teams in division one, this is the 127^th-best rank.
Borda	This is the sum of "Borda counts" from each list. The Borda count is the number of alternatives (teams) that are ranked below the choice. For example, if a particular ranking has 10 teams tied for #1, each has a Borda count of 242 (the number ranked second or worse.)
Avg	This is just the arithmetic mean of the 252 rankings for the team.

Those measurements are included below, along with links to a report of how teams ranked each team and how that team ranked all the teams.

Update

With the radius of the graph so large (27 through games of 26 October) the counts are dominated by the large numbers of paths at the radius - there are 2,267,097,073,326 unique paths 27 steps long. This is over 55% of the 4,087,438,912,600 paths of any length.

It also doesn't seem quite right to have an Auburn→Ole Miss→LSU chain by itself nullify the LSU→Auburn (or the Ole Miss→LSU→Auburn chain the Auburn→Ole Miss) result. So we introduce the modification:

ƒ(A,B) =	_radius
	∑	(#paths from A to B at length r)×2^(1-r)
	^{r = 1}

So a path one step long (i.e. a win) counts as 1, an A→x→B path counts as ½, an A→x₁→x₂→B path counts as 1/4^th, and so on up to requiring 67,108,864 27-step paths to offset one win.

The comparison used to order the teams based upon vertex A becomes ƒ(A,x) - ƒ(x,A) instead of the difference in total path counts.

Week 9