Placement, PageRank, and the PGR: Part 1

This is the first of two posts devoted to an idea of David Wallace’s.

Suppose you pick a philosophy PhD program at random and you go visit their website. There you pick a random person from the faculty list and see where they got their PhD. Then you go to that program’s website and repeat the exercise: pick a random faculty member, see where they did their PhD, and go to that program’s website. And again, and again.

You’d come back to some programs more often than others in the long run. Which ones? Those whose graduates are in demand at other programs whose graduates are in demand at still other programs etc. In other words, the programs you keep coming back to are central in the hiring network of philosophy PhD programs.

This is the idea behind Google’s famous “PageRank” algorithm. In a classic paper, Google’s founders imagined a web surfer starting at a random page, following a random link from there, then following a random link found on the new page, and so on. Pages where the surfer winds up more often are more likely to be of interest to the users of a search engine.

Wallace’s idea was to apply the same algorithm to the APDA’s placement data. And he found that the resultant rankings correlated closely with the Philosophical Gourmet Report’s ratings from 2006.

These posts expand on the idea in two parts. This post explains the theory behind the PageRank algorithm, and reproduces Wallace’s rankings. The next post considers the possibility of predicting a department’s PageRank, using either past PGR scores, or past placement data fed into the PageRank algorithm itself.

Motivation

Why care about a department’s PageRank? You might think it’s an indicator of a program’s “quality”, but I’m more interested in its potential use to students. Some want to become professors at programs where they will train PhDs who go on to do the same.

I’m also just intrigued by the PageRank algorithm itself. It’s mathematically very nifty, and it has a delightfully philosophical flavour too. It takes a problem that looks like a vicious regress and shows how to give it a virtuous grounding.

So these posts are partly an exercise for me, to learn about the algorithm and the math behind it. Plus I just like playing with data.

Theory

There are two ways to understand the PageRank algorithm. First is the random surfer idea already described. The second we might call the “vote of confidence” model.

When program X hires a graduate of program Y, that’s a vote of confidence for program Y. But this vote carries more weight if program X itself is well regarded. So we have to see where program X’s own graduates have been placed, and determine how much confidence people have in those programs. And so on.

The threat of regress looms. How do we break out? With a dash of high school algebra.

Imagine we have just three programs, A, B, and C. Program A got 80% of its faculty from B, and 10% each from C and from A itself. B is similar, except… well, here’s the whole story:

A’s Faculty B’s Faculty C’s Faculty
PhD from A 10% 20% 30%
PhD from B 80% 70% 40%
PhD from C 10% 10% 30%

Thinking row-wise, A cast 10% of its votes for A so to speak; B cast 20% of its votes for A; and C cast 30% of its votes for A. But how much weight does a vote from program A carry, compared to say a vote from B? Labeling these unknown weights $w_A$, $w_B$, and $w_C$, we get a linear equation: $$w_A = .1 w_A + .2 w_B + .3 w_C.$$ Applying the same formula to B and C, and we get a system of three linear equations, in three unknowns: \begin{aligned} w_A &= .1 w_A + .2 w_B + .3 w_C.\\ w_B &= .8 w_A + .7 w_B + .4 w_C.\\ w_C &= .1 w_A + .1 w_B + .3 w_C. \end{aligned}

Solving this system we find that $(w_A, w_B, w_C) = (0.19, 0.68, 0.12)$ is the only solution with positive weights. So we’ve determined how much weight a vote from each program carries. And unsurprisingly, votes from program B carry by far the most weight.

Will the same reasoning work no matter how many programs we have, and no matter what their hiring patterns are like? More or less yes. We have to upgrade the math a bit and add a small tweak. But the heart of the idea is pretty much the same.

General Solution

In the general case, we have $n$ programs and we want to give each program $i$ a weight $w_i$ that reflects the votes of confidence it’s received. Placement data tells us for any two programs $i$ and $j$ the portion of faculty at program $j$ hired from program $i$, call it $m_{ij}$. Since the weight of program $i$ is the weighted sum of these numbers, we have a set of $n$ linear equations with $n$ unknowns: \begin{aligned} m_{11} w_1 + m_{12} w_2 + \ldots + m_{1n} w_n &= w_1,\\ m_{21} w_1 + m_{22} w_2 + \ldots + m_{2n} w_n &= w_2,\\ \vdots & \\ m_{n1} w_1 + m_{n2} w_2 + \ldots + m_{nn} w_n &= w_n. \end{aligned} In matrix terms, we’re looking to solve the equation $\mathbf{M} \mathbf{w} = \mathbf{w}.$ This is an eigenvector equation $\mathbf{M} \mathbf{w} = \lambda \mathbf{w}$, where the eigenvalue $\lambda = 1$. And a famous theorem guarantees that a unique solution exists, given assumptions to be discussed momentarily.

The same theorem also guarantees that this solution is the result of the random-surfing exercise we opened with. This is why we can understand PageRank using either of our two interpretations. The weight $w_B$ will also be the frequency with which our random surfer comes back to program B’s faculty page.

Why? Well suppose we start on some random program’s page, say program A. We represent this with the vector $\mathbf{p} = (1, 0, 0)$, because right now we’re on program A’s page with probability 1. Then we start our random walk. What is the probability we’ll arrive at A, or B, or C next? To find out we multiply $\mathbf{M}$ against $\mathbf{p}$: \begin{aligned} \mathbf{M} \mathbf{p} &= \left( \begin{matrix} 0.1 & 0.2 & 0.3\\ 0.8 & 0.7 & 0.4\\ 0.1 & 0.1 & 0.3 \end{matrix} \right) \left( \begin{matrix} 1\\ 0\\ 0 \end{matrix} \right)\\ &= \left( \begin{matrix} 0.1\\ 0.8\\ 0.1 \end{matrix} \right). \end{aligned} To find out where we’ll probably be at the next step, we multiply this result by $\mathbf{M}$ again, i.e. we compute $\mathbf{M}(\mathbf{M}\mathbf{p})$. Since matrix multiplication is associative, this is the same as $\mathbf{M}^2 \mathbf{p}$. And in general the probabilities of the $k$-th step are given by $\mathbf{M}^k \mathbf{p}$.

Our theorem guarantees now (given conditions still to be specified): $$\lim_{k \rightarrow \infty} \mathbf{M}^k \mathbf{p} = \mathbf{w},$$ where $\mathbf{w}$ is the solution to $\mathbf{M}\mathbf{w} = \mathbf{w}$ we found earlier. In other words, as the random walk progresses, the portion of time spent at a program’s page converges to the weight that program’s votes carry.

Importantly, this convergence happens no matter where the random walk starts. In fact we get the same convergence for any probability vector $\mathbf{p}$ we might start with. (A probability vector is a list of non-negative numbers that sum to one.)

So what conditions guarantee this happy convergence? Our matrix $\mathbf{M}$ is stochastic, meaning its columns are probability vectors: they contain nonnegative numbers that sum to one. Given that, it suffices for $\mathbf{M}$ to be regular, meaning $\mathbf{M}^k$ has all positive entries for some positive integer $k$. This is equivalent to it being possible to get from the page of any one program to any other, with positive probability.

In reality this condition may well fail, but there’s any easy fix. We just have our random surfer occasionally start over, picking a new program at random to start their surfing from. Then there’s always a positive chance of ending up anywhere, however briefly.

Application

Let’s put this theory into practice. We need a list of PhD programs, and the number of hires from each of them, by each of them. Happily the APDA provides a table of just such data up through 2016.

This table counts hires broadly, notice. It includes postdoc positions, and any “permanent academic” post apparently (see page 65 here).

It also includes “selfies”: when a program hires one of its own PhDs. Some selfies are certainly legitimate for our purposes, but others probably aren’t the sort of thing we’re after here. For example, KU Leuven stands out as having far more selfies than any other program save Oxford. Judging from Leuven’s website, most of these posts are not permanent positions, nor the sort of highly desirable fellowships Oxford often hires its own graduates into.

In this analys I’m going to exclude selfies. This is a bit arbitrary, but not entirely. It has a big, negative impact on KU Leuven, not nearly so much Oxford. Disclosure: it also slightly favours the University of Toronto, where I work.

That in mind let’s see our top 10 PageRank programs, alongside Wallace’s results for comparison:

Wallace Weisberg
New York University New York University
Columbia University Columbia University
Princeton University Princeton University
Yale University Yale University
Katholieke Universiteit Leuven University of California, Berkeley
University of California, Berkeley Rutgers University
University of Oxford University of Pittsburgh (HPS)
Rutgers University University of Toronto
University of Pittsburgh (HPS) University of Oxford
University of Toronto Harvard University

The match is quite close. And the two big differences (Oxford and Leuven) are explained by the exclusion of selfies. So we seem to have implemented the algorithm correctly.

Next time we’ll look at predicting PageRanks, based on past PGR ratings, and past placement data. Meanwhile, here’s the full listing:

Ordinal Program PageRank
1 New York University 0.0556761
2 Columbia University 0.0513814
3 Princeton University 0.0469022
4 Yale University 0.0364091
5 University of California, Berkeley 0.0347961
6 Rutgers University 0.0320305
7 University of Pittsburgh (HPS) 0.0306536
8 University of Toronto 0.0255954
9 University of Oxford 0.0237988
10 Harvard University 0.0234968
11 University of North Carolina at Chapel Hill 0.0226243
12 University of Pittsburgh 0.0222314
13 Massachusetts Institute of Technology 0.0189393
14 University of California, Los Angeles 0.0185778
15 University of Chicago 0.0174908
16 Stanford University 0.0167941
17 University of Cambridge (HPS) 0.0132451
18 University of California, San Diego 0.0130881
19 University of Arizona 0.0125996
20 Brown University 0.0119340
21 Northwestern University 0.0115745
22 University of Michigan 0.0111104
23 London School of Economics and Political Science 0.0107691
24 Graduate Center of the City University of New York 0.0100186
25 University of Cambridge 0.0100180
26 Indiana University Bloomington 0.0097714
27 University of Notre Dame 0.0094539
28 King’s College London 0.0091462
29 University of Pennsylvania 0.0091080
30 Ohio State University 0.0090754
31 University of Maryland, College Park 0.0089689
32 Katholieke Universiteit Leuven 0.0089271
33 University of Chicago (CHSS) 0.0086507
34 University of Southern California 0.0083793
35 Cornell University 0.0082857
36 Institut Jean Nicod 0.0082398
37 Western University 0.0080649
38 Indiana University Bloomington (HPS) 0.0079434
39 Australian National University 0.0079356
40 Duke University 0.0077089
41 The University of Melbourne 0.0077023
42 University College London 0.0068843
43 St Andrews and Stirling Graduate Programme in Philosophy 0.0067107
44 University of California, Irvine (LPS) 0.0062144
45 University of Alberta 0.0062053
46 University of Texas at Austin 0.0061678
47 University of Sheffield 0.0061209
48 Georgetown University 0.0057809
49 Carnegie Mellon University 0.0056723
50 Pennsylvania State University 0.0056654
51 Arizona State University 0.0056481
52 University of British Columbia 0.0055508
53 Boston College 0.0054974
54 University of Edinburgh 0.0052731
56 McGill University 0.0049022
57 Tulane University 0.0048671
58 University of Memphis 0.0047615
59 McMaster University 0.0045715
60 University of Minnesota Twin Cities 0.0045700
61 University of Oregon 0.0045430
62 Boston University 0.0041329
63 University of Connecticut 0.0039652
64 University of California, Riverside 0.0039192
65 The University of Sydney 0.0038372
66 Johns Hopkins University 0.0037778
67 University of Colorado Boulder 0.0036436
68 The New School 0.0035828
69 University of California, Santa Barbara 0.0035150
70 University of Virginia 0.0034553
71 University of South Florida 0.0034273
72 State University of New York at Buffalo 0.0033737
73 York University 0.0030985
74 University of Massachusetts Amherst 0.0030937
75 University of California, Irvine 0.0030890
76 Vanderbilt University 0.0030261
77 Michigan State University 0.0030149
78 Saint Louis University 0.0029294
79 Emory University 0.0028953
80 University of Illinois at Chicago 0.0028281
81 Purdue University 0.0027891
82 University of California, Davis 0.0027106
83 State University of New York at Stony Brook 0.0025640
84 DePaul University 0.0025005
85 University of Iowa 0.0023518
86 Baylor University 0.0021004
87 Macquarie University 0.0020773
88 University of Illinois at Urbana-Champaign 0.0020013
89 The University of Manchester 0.0019471
90 Syracuse University 0.0018914
91 William Marsh Rice University 0.0018034
92 University of Calgary 0.0017465
93 University of York 0.0017356
94 University of Hawai’i at Manoa 0.0017302
94 University of Oklahoma 0.0017302
96 Duquesne University 0.0016160
97 Kingston University 0.0015818
98 Tilburg University 0.0015262
99 The Catholic University of America 0.0015213
100 Fordham University 0.0015210
101 University of Arkansas 0.0015187
102 University of Rochester 0.0014903
103 University of Nebraska, Lincoln 0.0014715
104 University of Washington 0.0014668
105 Washington University in St. Louis 0.0013589
106 Villanova University 0.0012493
107 Loyola University Chicago 0.0011959
107 University of South Carolina 0.0011959
107 Victoria University of Wellington 0.0011959
110 University of Florida 0.0011906
111 Bowling Green State University 0.0011731
112 University of Guelph 0.0011575
113 University of Utah 0.0011462
114 Binghamton University 0.0011355
115 University of Tennessee 0.0011087
116 University of Waterloo 0.0010800
117 University at Albany 0.0010486
118 University of New Mexico 0.0010049
119 Birkbeck, University of London 0.0009510
120 University of Kentucky 0.0008533
121 Marquette University 0.0008356
122 University of Cincinnati 0.0008316
123 University of Georgia 0.0007732
124 Brandeis University 0.0007232
124 California Institute of Technology 0.0007232
124 Central European University 0.0007232
124 Dalhousie University 0.0007232
124 Deakin University 0.0007232
124 Durham University 0.0007232
124 Eindhoven University of Technology 0.0007232
124 Florida State University 0.0007232
124 Free University of Berlin 0.0007232
124 Goethe University Frankfurt 0.0007232
124 Humboldt University of Berlin 0.0007232
124 Iowa State University 0.0007232
124 Monash University 0.0007232
124 Montclair State University 0.0007232
124 Pantheon-Sorbonne University 0.0007232
124 Southern Illinois University 0.0007232
124 Stockholm University 0.0007232
124 Temple University 0.0007232
124 Texas State University 0.0007232
124 The University of Adelaide 0.0007232
124 The University of Western Australia 0.0007232
124 Trinity College, Dublin 0.0007232
124 University de Montreal 0.0007232
124 University of Aberdeen 0.0007232
124 University of Amsterdam 0.0007232
124 University of Auckland 0.0007232
124 University of Bristol 0.0007232
124 University of California, Santa Cruz 0.0007232
124 University of Cologne 0.0007232
124 University of Dallas 0.0007232
124 University of East Anglia 0.0007232
124 University of Geneva 0.0007232
124 University of Glasgow 0.0007232
124 University of Groningen 0.0007232
124 University of Helsinki 0.0007232
124 University of Kansas 0.0007232
124 University of Kent 0.0007232
124 University of Leeds 0.0007232
124 University of Miami 0.0007232
124 University of Milan 0.0007232
124 University of Missouri 0.0007232
124 University of New South Wales 0.0007232
124 University of Oslo 0.0007232
124 University of Otago 0.0007232
124 University of Ottawa 0.0007232