This is the first of two posts devoted to an idea of David Wallace’s.
- Part 1
- Part 2
- Source on GitHub
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 |
| 55 | University of Wisconsin-Madison | 0.0050191 |
| 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 | Claremont Graduate 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 |
| 124 | University of Reading | 0.0007232 |
| 124 | University of Sussex | 0.0007232 |
| 124 | University of Tasmania | 0.0007232 |
| 124 | University of Tubingen | 0.0007232 |
| 124 | University of Vienna | 0.0007232 |
| 124 | University of Waikato | 0.0007232 |
| 124 | University of Warwick | 0.0007232 |
| 124 | Uppsala University | 0.0007232 |
| 124 | Wayne State University | 0.0007232 |