Preface
“Always the beautiful answer who asks a more beautiful question.”—e.e. cummings
Purpose
We became intrigued by the power of rating and ranking methods while writing our earlier book Google’s PageRank and Beyond: The Science of Search Engine Rankings [49]. While developing this “Google book,” we came to appreciate how rich (and old) the area of rating and ranking is and how far beyond Web search it extends. But learning about the various facets of the subject was tedious because we could not find a convenient source that neatly tied the multitude of methods and applications together into one nice package. Thus this book was born. In addition to collecting in one place relevant information that is spread throughout many individual articles, websites, and other sources, we also present several new ideas of our own concerning rating and ranking that have heretofore not been published. Our goal is to arm readers with enough background and diversity to generate an appreciation for the general art of rating and ranking as well as to prepare them to explore techniques and applications beyond those that appear in this book.
Audience
As the list on page 6 at the end of Chapter 1 points out, the applications of ranking are extremely numerous and varied. Consequently, there are many types of readers who might be interested in the topic, and likewise, this book. For example, readers might be sports enthusiasts, social choice theorists, mathematicians, computer scientists, engineers, and college and high school teachers of classes such as linear algebra, optimization, mathematical modeling, graph theory, or special topics classes, not to mention the people interested in wagering on just about anything that you can think of.
Prerequisites
Most of the book assumes that the reader has had a course in elementary linear algebra and a few chapters assume some knowledge of optimization. If you haven’t had these classes, we have a few suggestions.
1. You should read through the book anyway. Every linear algebra-based method in the book boils down to one of two fundamental elements of the subject: solving a system of linear equations or computing an eigenvector. Even if you don’t understand these two elements, you can still implement the methods. For example, there is software, both free and for a fee, that can solve a system of linear equations or compute an eigenvector for you. You just need to understand what data is required as input and how to interpret the output—an understanding of what your software is doing internally is not required.
2. Of course, a true understanding of these subjects will improve your ability to implement, modify, and adapt the methods for your specific goals, so you might consider self-study with an online tutorial or a classic book. Our favorite linear algebra books are [54, 76, 40], but if you are a complete novice, then seek out an online elementary tutorial (many exist) concerning the topic(s) in question. A few of our favorite optimization books, in increasing level of depth, are: [82, 60, 10, 84, 85].
3. Finally, and ideally, we recommend taking an elementary linear algebra class, and later, if time and money permit, an optimization class.
Teaching from This Book
We anticipate that college or high school teachers will use this book for either a short 1–2 lecture module or an entire class such as a special topics or mathematical modeling class. In the former case, teachers will find it quite easy to extract material for a short module. In fact, we have “modularized” the material with this aspect in mind—i.e., very little in the book builds on prior material. The various chapters can be presented in nearly any order. For example, a linear algebra teacher might want to add a lecture on an application of linear systems. In this case, a good choice is Chapter 3 on the Colley method, which is the simplest, most straightforward linear system method in the book. Similarly, after a lecture on the theory of eigenvalues and eigenvectors, a teacher may choose to lecture on an application of eigensystems using the material in Chapter 4. Chapter 6 contains material on Markov chains, a topic that typically appears toward the end of a linear algebra class.
Acknowledgments
• The College of Charleston. Luke Ingram and John McConnell, two former M.S. students, completed a class project on ranking teams in the March Madness basketball tournament in the spring of 2006. Luke Ingram extended this class project and created an outstanding thesis [41] with several interesting ranking ideas. Then in the spring of 2008, two undergraduate mathematics majors, Neil Goodson and Colin Stephenson, tackled the same class project, predicting games in that year’s March Madness tournament. Neil and Colin used a very preliminary draft of this book and tested several of the ranking models presented herein. They did such a good job of predicting games in the 2008 tournament that they earned a shocking amount of national press. See the aside and notes on pages 151 and 212. Kathryn Pedings, a B.S. Mathematics graduate, continued on as a M.S student working on her thesis topic of linear ordering. She served as assistant extraordinaire by collecting data used in several asides and participating in several brainstorming and discussion sessions. Much of Kathryn’s work appears in Chapters 8 and 15. Finally, all students of the Ranking and Clustering research group at the College of Charleston participated in weekly research discussions that helped to form this book. Thus, the first author makes additional shout-outs to Emmie Douglas, Ibai Basabe, Barbara Ball, Clare Rodgers, Ryan Parker, and Patrick Moran.
• North Carolina State University. As part of her thesis Ranking Theory with Applications to Popular Sports [34], Anjela Govan contributed to the development of the Offense-Defense rating theory [35] by establishing and formalizing the connections between the OD method and the Sinkhorn–Knopp theory of matrix balancing. In addition, her work on Web scraping and data collection was the basis for a significant number of experiments on a large variety of rating and ranking methods, some of which are included in this book. Evaluating techniques that do not work well is as important as revealing those that do. We limited our book to methods that have significant merit, so many of Anjela’s significant contributions are not transparent to the reader, but the book is much better because of her work. Charles D. (Chuck) Wessell, was a graduate student at NC State at the time this book was being written, and is now part of the mathematics faculty at Gettysburg College in Gettysburg, PA. Chuck provided many helpful suggestions, and we are indebted to him for his eagle sharp eyes. His careful reading of the manuscript along with his careful scrutiny of the data (the NFL data in particular) prevented several errors from being printed. In addition, Chuck taught an undergraduate class from the material in our book, and his class-room experiences helped to hone the exposition.
• Colleagues. Discussions with David Gleich during his visits to the College of Charleston influenced aspects in Chapters 14 and 16. Timothy Chartier of Davidson College corresponded regularly with the first author, and Tim’s projects with his student Erich Kreutzer along with their feedback on early drafts of this book were insightful. In particular, the discussion on ties in Chapter 11 resulted from this collaboration. Kenneth Massey of Carson-Newman College hosts a huge data warehouse and website dedicated to sports ranking. Almost all of the sports examples in this book owe their existence to Dr. Massey and his data. We are grateful for his generosity, attitude, knowledge, and computer expertise.
• Support. The work of the first author was supported in part by the National Science Foundation CAREER award CCF-0546622, which helped fund collaborative travel and a mini-sabbatical to complete and revise the manuscript. Furthermore, the first author is grateful for the support and nurturing environment provided by the College of Charleston. Since Day 1, the university, college, and department have been extremely welcoming and supportive of her career and research. In particular, she thanks the departmental chairs, former and current, Deanna Caveny and Bob Mignone, respectively, as well as former Dean Noonan for their creative leadership and warm support.
• Photographs. The National Science and Technology Medals Foundation and Ryan K. Morris are acknowledged for their permission to reprint the photograph of K. Arrow on page 4. The photograph of K. Massey on page 9 is reprinted courtesy of Kenneth Massey, and the photograph of J. Keener on page 51 is reprinted courtesy of James Keener. The photograph of J. Kleinberg on page 92 is by Michael Okoniewski. The photograph of A. Govan on page 94 is reprinted courtesy of Anjela Govan. The photographs of Neil Goodson and Colin Stephenson on page 152 are courtesy of the College of Charleston. The photographs of Kathryn Pedings and Yoshitsugu Yamamoto on page 153 are courtesy of Kathryn Pedings and Yoshitsugu Yamamoto.