This site is devoted to mathematics and its applications. Created and run by Peter Saveliev.

Acyclic ranking

From Mathematics Is A Science

Jump to: navigation, search

The main problem with web search is that you need to find the best page based on the links but the links may look like this:

 A -> B -> C -> A.

It's a "cycle".

PageRank circumvented the problem but didn't solve it. The result is bad math.

The idea of an "acyclic rank" is that we should remove cycles.

The mathematics needed is fully covered by this site, see Courses.

It surprising that there isn't more written on the subject from the theoretical point of view. It makes sense to start at the bottom and try to come up with a few principles that such a ranking must satisfy. I'll try to keep them from being over-restrictive to avoid that a fate similar to Arrow's Impossibility Theorem. Hopefully, this will be a uniqueness theorem instead of impossibility theorem.

A good place to start is the simple tally used in elections:

 ranking = number of "for" votes - number of "against" votes.

In a more general setting, we'd use the "normalized tally":

 ranking = sum of votes / number of votes.

Clearly this number is unaffected by cycles. The main problem is that it doesn't matter who votes, so a string

 A -> B -> C -> D -> ... -> Z

will produce a multiple tie in the middle.

Let's start with the axioms (something Google should have done a long time ago):

  1. If the set of candidates is split into two sets $X,Y$ with no preferences between their members, the average ranks of these set should be equal: $\Sigma _{A \in X}R(A)/|X|=\Sigma _{A \in Y}R(A)/|Y|$.
  2. If two candidates $A,B$ have the exact same set of preferences, their ranks should be equal: $R(A)=R(B)$.
  3. ?

A way to test new approaches could be this.

About the Netflix prize read here.