Langville Amy N. - Whos number one?: the science of rating and ranking

Whos #1?
The Science of Rating and Ranking

Amy N. Langville and Carl D. Meyer

Copyright 2012 by Princeton University Press

Published by Princeton University Press
41 William Street, Princeton, New Jersey 08540

In the United Kingdom: Princeton University Press
6 Oxford Street, Woodstock, Oxfordshire, OX20 1TW

All Rights Reserved

Library of Congress Cataloging-in-Publication Data

Langville, Amy N.
Whos #1?: The science of rating and ranking / Amy N. Langville and Carl D. Meyer.
p. cm.
Includes bibliographical references and index.
ISBN 978-0-691-15422-0 (alk. paper)
1. Ranking and selection (Statistics) I. Meyer, C. D. (Carl Dean) II. Title.
QA278.75.L36 2012
519.5dc23 2011036016

British Library Cataloging-in-Publication Data is available

This book has been composed in

The publisher would like to acknowledge the authors of this volume for providing the camera-ready copy from which this book was printed.

Printed on acid-free paper.

press.princeton.edu

Printed in the United States of America

10 9 8 7 6 5 4 3 2 1

To John,
for whom I need no algorithm
to tell me who is, was,
and ever shall be
my #1.

AND

To Bethany,
Rating = 10, Rank = 1.

Always the beautiful answer who asks a more beautiful question.e.e. cummings

We became intrigued by the power of rating and ranking methods while writing our earlier book Googles PageRank and Beyond: The Science of Search Engine Rankings []. 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.

As the list on 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.

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 havent 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 dont 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 outputan 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 [].

3. Finally, and ideally, we recommend taking an elementary linear algebra class, and later, if time and money permit, an optimization class.

We anticipate that college or high school teachers will use this book for either a short 12 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 mindi.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 contains material on Markov chains, a topic that typically appears toward the end of a linear algebra class.

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 [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 [] by establishing and formalizing the connections between the OD method and the SinkhornKnopp 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 Anjelas 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 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.