# Mathematically ranking ranking methods

##### May 24, 2011

In a world where everything from placement in a Google search result to World Cup eligibility depends on ranking and numerical ratings of some kind, it is becoming increasingly important to analyze the algorithms and techniques that underlie such ranking methods in order to ensure fairness, eliminate bias, and tailor them to specific applications.

In a paper published this month in the SIAM Journal on , authors Timothy Chartier, Erich Kreutzer, Amy Langville, and Kathryn Pedings mathematically analyze three commonly-used ranking methods. "We studied the sensitivity and stability of three popular ranking methods: PageRank, which is the method has used to rank web pages, and the Colley and Massey methods, which have been used by the Bowl Championship Series to rank U.S. college football teams," explains Langville.

All three methods analyzed – the Colley and the Massey ranking techniques and the Markov web page rankings—which is a generalized version of PageRank—are linear algebra-based with simple elegant formulations. Here, the authors apply a modified version of PageRank to a sports season.

"Both web page authors and teams sometimes try to game, or spam, ranking systems to achieve a higher ranking. For instance, web page authors try to modify their incoming and outgoing links while teams try to run up the score against weak opponents," says Langville, pointing out the significance of studying such methods. "Mathematically, such spamming can be viewed as changes to the input data required by the ranking method."

Most methods, including the aforementioned three, produce "ratings" of numerical scores for each team, which represents their playing ability. When sorted, these ratings produce ranks with integer values for each team, simply representing a numerical listing of the teams based on their rating.

In the first step of their analysis, the authors assume a simple rating scheme with constant difference of 1 in scores and apply it to a perfect sports season. In a perfect season, each team plays every other team only once and there are no upset victories or losses. In such an ideal scenario, a highly-ranked team would always beat a lower-ranked team. Thus, in a system with teams numbered 1 through 4 for their ranks, team 1 would beat all other teams; team 2 would beat teams 3 and 4, and lose to 1; team 3 would beat team 4, losing to teams 1 and 2; and team 4 would lose to all other teams. They then compute the output rating for each of the three methods and compare them to the input rating.

The three methods are applied to this ideal data, and all three methods recover the input ranking. However, while the Colley and Massey methods produce ratings that are uniformly spaced as would be desirable in a rating system, the Markov method, produces non-uniformly spaced ratings.

The authors analyze the sensitivity of the methods to small perturbations and determine how much the rating and ranking is affected by these changes. If, for instance, small changes in input data cause large changes in the output ratings, the method is considered sensitive. Similar discrepancies in the input and output ranking data would show instability of the ranking method.

The authors conclude that while the Colley and Massey methods are insensitive to small changes, the Markov method (or Page Rank method) is highly sensitive to such changes, often resulting in anomalies in rankings. For instance, there are cases of a single upset in a perfect season resulting in rearrangements of rankings for all teams because of the Markov method's high sensitivity. In these cases, the Colley and Massey methods would have an isolated response, resulting in changes to the rankings of only the two teams in question.

In addition, the sensitivity of the PageRank or Markov method gets more pronounced further down in the rankings. "The PageRank vector is quite sensitive to small changes in the input data. Further, this sensitivity increases as the rank position increases," Langville explains. "In other words, values in the tail (low-ranked positions) of the PageRank vector are extremely sensitive, which calls into question PageRank's use to produce a full ranking, as opposed to a simply top-k ranking. It also partially explains PageRank's susceptibility to spam. On the other hand, the Colley and Massey methods are stable throughout the entire ranking."

PageRank has recently evolved from being used exclusively for web pages to rank various entities, from species to social networks, reinforcing the ubiquity of these ranking systems.

But the stability displayed by the Colley and Massey methods in this study shows that these two methods would perhaps be effective even in ranking other entities, such as and movies, though originally conceived for sports rankings.

"As future work, we are exploring the use of the Colley and Massey methods in other settings beyond sports. For example, we have found that these two methods are more appropriate than PageRank for ranking in social networks such as Twitter," says Langville.

While methods can be applied to a wide range of areas, modifications are often required in order to translate a particular method to suit a specific application, making analyses of sensitivity and stability that much more important.

Explore further: Researchers help Boston Marathon organizers plan for 2014 race

## Related Stories

#### New Algorithm Ranks Sports Teams like Google's PageRank

Dec 15, 2009

(PhysOrg.com) -- Sports fans may be interested in a new system that ranks NFL and college football teams in a simple, straightforward way, similar to how Google PageRank ranks webpages. The new sports algorithm, ...

#### Google PageRank-like algorithm dates back to 1941

Feb 19, 2010

(PhysOrg.com) -- When Sergey Brin and Larry Page developed their PageRank algorithm for ranking webpages in 1998, they certainly knew that the seeds of the algorithm had been sown long before that time, as ...

#### Web page ranking algorithm detects critical species in ecosystems

Sep 04, 2009

Google's algorithm for ranking web-pages can be used to determine which species are critical for sustaining ecosystems. Drs. Stefano Allesina and Mercedes Pascual find that "PageRank" can be applied to the study of food webs, ...

#### IST researchers categorize social media searches

Jul 30, 2010

(PhysOrg.com) -- By integrating social media, Penn State researchers have found a way to better satisfy individual users' multimedia searches on the Web.

#### Ranking research

May 03, 2011

A new approach to evaluating research papers exploits social bookmarking tools to extract relevance. Details are reported in the latest issue of the International Journal of Internet Technology and Secured Transactions.

#### Think College Football Teams Punished For Late Losses? Not So Fast, My Friend

Nov 21, 2007

A new study of 25 years of data from a major college football poll challenges three strongly held beliefs of many coaches and fans.

## Recommended for you

#### Egypt archaeologists find ancient writer's tomb

4 hours ago

Egypt's minister of antiquities says a team of Spanish archaeologists has discovered two tombs in the southern part of the country, one of them belonging to a writer and containing a trove of artifacts including reed pens ...

#### Researchers create methylation maps of Neanderthals and Denisovans, compare them to modern humans

Apr 18, 2014

(Phys.org) —A team of Israeli, Spanish and German researchers has for the first time created a map of gene expression in Neanderthals and Denisovans and has compared them with modern humans. In their paper ...

#### 3 Qs: Economist makes the case for new quasi-experiments as a way of studying environmental issues

Apr 18, 2014

How can scholars get traction on environmental problems, particularly those relating to pollution? In an essay appearing in this week's issue of the journal Science, MIT economist Michael Greenstone, along ...

#### New specimens of Yanornis indicate a digestive system of living birds

Apr 18, 2014

In a recent paper describing ten new specimens of Yanornis martini identified by the director of the Shandong Tianyu Museum of Natural History Mr. Xiaoting Zheng, an international team of scientists lead ...

#### Study finds law dramatically curbing need for speed

Apr 18, 2014

Almost seven years have passed since Ontario's street-racing legislation hit the books and, according to one Western researcher, it has succeeded in putting the brakes on the number of convictions and, more importantly, injuries ...

#### Changing dinosaur tracks spurs novel approach

Apr 17, 2014

Paleontologists are using a range of old and new techniques to map the Broome Sandstone dinosaur trackways.

##### emsquared
not rated yet May 24, 2011
So... you're saying Google should have a Web-page Bowl Play-off Series??
##### nine1189
not rated yet Jun 23, 2011
This makes sense. Just look at the Google panda update! As I have been into online marketing, this stability issue and sensitivity would be giving us a glimpse or some sort of an explanation why websites ranked low than what they rank before. Interesting!

## More news stories

#### Egypt archaeologists find ancient writer's tomb

Egypt's minister of antiquities says a team of Spanish archaeologists has discovered two tombs in the southern part of the country, one of them belonging to a writer and containing a trove of artifacts including reed pens ...

#### Researchers create methylation maps of Neanderthals and Denisovans, compare them to modern humans

(Phys.org) —A team of Israeli, Spanish and German researchers has for the first time created a map of gene expression in Neanderthals and Denisovans and has compared them with modern humans. In their paper ...

#### Last Week's Best—Quantum mechanics breakthrough, 3-D printed human heart, and paraplegia therapy

(Phys.org) —Hello readers—we'd like to try something new here at Phys.org and Medical Xpress: offer a weekly summary every Monday highlighting what we feel are the most important stories of the past ...

#### Earliest ancestor of land herbivores discovered

New research from the University of Toronto Mississauga demonstrates how carnivores transitioned into herbivores for the first time on land.

#### Neanderthals and Cro-magnons did not coincide on the Iberian Peninsula

The meeting between a Neanderthal and one of the first humans, which we used to picture in our minds, did not happen on the Iberian Peninsula. That is the conclusion reached by an international team of researchers ...

#### NASA's space station Robonaut finally getting legs

Robonaut, the first out-of-this-world humanoid, is finally getting its space legs. For three years, Robonaut has had to manage from the waist up. This new pair of legs means the experimental robot—now stuck ...

#### Ex-Apple chief plans mobile phone for India

Former Apple chief executive John Sculley, whose marketing skills helped bring the personal computer to desktops worldwide, says he plans to launch a mobile phone in India to exploit its still largely untapped ...

#### Free the seed: OSSI nurtures growing plants without patent barriers

(Phys.org) —Members of the Open Source Seed Initiative this week held a rally and seed giveaway event. The group is concerned over restricting access to seeds through patents. They are stirring up public ...

#### Filipino tests negative for Middle East virus

A Filipino nurse who tested positive for the Middle East virus has been found free of infection in a subsequent examination after he returned home, Philippine health officials said Saturday.