Connectivity

© Copyright 2005, Paul Kislanko

Computer rating systems depend upon the "graph" that connects all teams through chains of opponents, opponents' opponents, and so on. In a truly balanced schedule such as that of Major League Baseball prior to 1961, by the end of the season each team is connected to every other team by no worse than an opponent's opponent relationship.

It turns out that in NCAA Division 1 football (Division 1A), basketball and baseball the longest path length at the end of the season is four. However, for baseball and basketball over half the team-pairs have a pathlength of two or less, while in an 11-game football season, only about 41 percent do. (In 12-game seasons the 117-team division 1A field was slightly more connected than the 290-team baseball field or 330-team basketball field.)

Path# pairsPercentAll PathsPercent
16318.996310.07
2223031.7673440.84
3369252.59740618.48
44686.6779083290.60
The connectivity of the entire field can be characterized by a "distance matrix" that lists the shortest path between each pair of teams. For the 2005 D1A football season, the schedules work out so that the average pathlength between teams is 2.56, and only six of 119 teams are connected to half the field by no worse than an O-O relationship.

Different rating systems depend upon different aspects of the field's connectivity for their processing. The more advanced ones use not the shortest path, but all paths between paired teams. In the "all paths" column in the table, the opponents, opponents' opponents, and so on are not unique. In fact, each team is connected to itself by a path of length 2 for each of its opponents, and length 3 for each pair of its opponents who are also opponents.

Team Connectivity

There are several different ways to measure the strength of a team's connection to the field, and the "correct" method depends entirely upon the rating's algorithm. For simple "RPI-like" ratings, a useful measure is what I call the "Connectivity Index", which is just the sum of the numbers of unique opponents and opponents' opponents. This table orders the teams by "most connected" to "least connected":

Unique Opponents, Opponents' Opponents, etc.
10 Aug 2005

CI Team conf #Os #OOs #OOOs #OOOOs
75 Navy Ind 11 64 42 1
72 Army Ind 10 62 45 1
70 Notre Dame Ind 11 59 45 3
62 Louisville BigE 11 51 55 1
61 Temple Ind 11 50 54 3
60 Minnesota B10 11 49 57 1
59 Wisconsin B10 12 47 57 2
58 North Texas SBC 11 47 59 1
57 North Carolina ACC 11 46 60 1
56 Colorado B12 11 45 55 7
55 Florida Atlantic SBC 11 44 63 0
55 Middle Tenn St SBC 11 44 57 6
55 Florida SEC 11 44 55 8
54 Rice CUSA 11 43 63 1
54 Tulsa CUSA 11 43 60 4
54 Louisiana Tech WAC 11 43 58 6
54 New Mexico St WAC 12 42 58 6
54 Ohio State B10 11 43 56 8
54 Illinois B10 11 43 54 10
53 Arizona St P10 11 42 63 2
53 Boise St WAC 11 42 63 2
53 Pittsburgh BigE 10 43 62 3
53 Colorado St MW 11 42 60 5
53 UL Lafayette SBC 10 43 60 5
53 UCLA P10 11 42 56 9
52 Air Force MW 11 41 66 0
52 TCU MW 11 41 66 0
52 Boston College ACC 11 41 63 3
52 San Diego St MW 12 40 63 3
52 Utah MW 11 41 62 4
52 Georgia SEC 11 41 61 5
52 Hawaii WAC 12 40 60 6
52 New Mexico MW 11 41 58 8
52 Wyoming MW 11 41 57 9
51 Akron MAC 11 40 62 5
51 Clemson ACC 11 40 62 5
51 South Florida BigE 10 41 58 9
51 UCF CUSA 11 40 57 10
51 Oklahoma B12 11 40 56 11
51 Bowling Green MAC 11 40 54 13
51 Wake Forest ACC 11 40 49 18
50 South Carolina SEC 11 39 65 3
50 Texas B12 11 39 65 3
50 Michigan St B10 11 39 62 6
50 Ball State MAC 11 39 58 10
50 Virginia Tech ACC 11 39 58 10
49 Miami-Florida ACC 11 38 69 0
49 Purdue B10 11 38 66 3
49 Rutgers BigE 10 39 65 4
49 Kentucky SEC 10 39 64 5
49 Syracuse BigE 11 38 64 5
49 Alabama SEC 11 38 62 7
49 Georgia Tech ACC 11 38 62 7
49 Ohio MAC 11 38 60 9
49 East Carolina CUSA 11 38 57 12
49 North Carolina St ACC 10 39 57 12
48 BYU MW 10 38 69 1
48 Nebraska B12 10 38 65 5
48 Southern California P10 12 36 65 5
48 Auburn SEC 10 38 64 6
48 Tennessee SEC 11 37 63 7
47 Tulane CUSA 10 37 70 1
47 Iowa B10 10 37 69 2
47 UL Monroe SBC 10 37 68 3
47 Maryland ACC 11 36 67 4
47 Connecticut BigE 10 37 64 7
47 Troy SBC 10 37 62 9
47 Marshall CUSA 10 37 58 13
47 UTEP CUSA 10 37 56 15
46 Indiana B10 10 36 71 1
46 Duke ACC 10 36 66 6
46 Fresno St WAC 11 35 65 7
46 Utah St WAC 11 35 64 8
46 Houston CUSA 10 36 63 9
46 Eastern Michigan MAC 11 35 62 10
46 SMU CUSA 11 35 62 10
46 Cincinnati BigE 10 36 59 13
46 Northwestern B10 11 35 57 15
45 Michigan B10 11 34 71 2
45 LSU SEC 10 35 66 7
45 Penn State B10 11 34 65 8
45 Washington P10 11 34 63 10
45 UAB CUSA 10 35 61 12
45 Toledo MAC 10 35 59 14
44 Oregon St P10 10 34 69 5
44 Kansas B12 10 34 68 6
44 Arizona P10 10 34 66 8
44 Florida St ACC 10 34 65 9
44 Iowa State B12 10 34 64 10
44 Virginia ACC 11 33 64 10
44 Miami-Ohio MAC 11 33 62 12
43 Arkansas St SBC 10 33 69 6
43 Texas A&M B12 10 33 67 8
43 San Jose St WAC 10 33 65 10
43 Arkansas SEC 10 33 64 11
43 Kansas St B12 11 32 64 11
42 Vanderbilt SEC 10 32 73 3
42 Stanford P10 10 32 70 6
42 Central Michigan MAC 11 31 67 9
42 Southern Miss CUSA 10 32 66 10
42 Mississippi SEC 10 32 65 11
42 Missouri B12 11 31 63 13
42 Kent St MAC 10 32 62 14
42 West Virginia BigE 10 32 62 14
41 California P10 10 31 62 15
40 Memphis CUSA 10 30 65 13
40 Idaho SBC 11 29 64 14
40 Baylor B12 10 30 63 15
40 Oregon P10 10 30 63 15
40 Western Michigan MAC 10 30 56 22
39 Nevada WAC 11 28 63 16
38 Buffalo MAC 11 27 53 27
37 Mississippi St SEC 10 27 72 9
37 UNLV MW 11 26 72 9
37 Florida Intl SBC 9 28 69 12
34 Oklahoma St B12 10 24 70 14
34 Northern Illinois MAC 10 24 62 22
33 Washington St P10 10 23 66 19
31 Texas Tech B12 9 22 70 17

Of course, these tables count the number of paths that will exist at the end of the (regular) season. Ratings systems use only those that represent games played, and take into account the winners of the games. Kenneth Massey provides a routine to find the shortest path between two teams based upon games played. Optionally it can find the shortest path on the directed graph based upon wins or losses and ending at the highest ranked team.

Some rating systems do not use all of the paths available. Besides the obvious choice of using a directed graph along paths entirely consisting of wins one could assign weights in a pairwise comparison based upon the number of common opponents and records against them, for instance. See 2005 common opponents for all team-pairs.