1

I am searching for an article on the net which I can't find anymore. It was describing an algorithm to rank web pages. I am trying to remember the name of this algorithm or technique.

The principle was the following:

  1. Each page is given a credit of 10 at the beginning.
  2. Each page is assigned a weight/probability by dividing its credit by the sum of all credits assigned to all pages.
  3. A subset of pages is selected randomly using to their weight/probability.
  4. This subset is displayed to users.
  5. Each time a user clicks on a page, its credit is increased by one. So preferred pages get more credit.
  6. Operation 2. was repeated to update weights/probabilities.

Thanks

1

It is a variation of Multi-armed bandit problem:

In probability theory, the multi-armed bandit problem (sometimes called the K- or N-armed bandit problem) is a problem in which a gambler at a row of slot machines (sometimes known as "one-armed bandits") has to decide which machines to play, how many times to play each machine and in which order to play them. When played, each machine provides a random reward from a distribution specific to that machine. The objective of the gambler is to maximize the sum of rewards earned through a sequence of lever pulls.

There are multiple ways to solve this problem, here is one:

  1. Each page is given two values:

    • number of times it was shown, initially 1
    • number of times it was clicked, initially 1

    The fitness of a page is clicked/shown. I use a term from genetic programming here, maybe there is more appropriate term in probability theory.

  2. Fitness proportionate selection is used to choose one page. To choose more than one, you can exclude the previously selected one from a set and repeat selection.

  3. Each time a page is displayed, its' shown value is increased by one. If it was also clicked, than clicked is also increased by one, otherwise it's left unchanged.

  4. Goto 2

However, it is tricky to decide when you should stop the experiment. You might want to look at Google Analytics docs on A/B-testing for details.

-2

I guess this is what you are looking for because the article says

PageRank is a link analysis algorithm and it assigns a numerical weighting to each element of a hyperlinked set of documents, such as the World Wide Web, with the purpose of "measuring" its relative importance within the set. The algorithm may be applied to any collection of entities with reciprocal quotations and references. The numerical weight that it assigns to any given element E is referred to as the PageRank of E and denoted by PR(E). Other factors like Author Rank can contribute to the importance of an entity.

  • PageRank is based on links, not clicks. – outis May 18 '15 at 23:31
  • 1
    PageRank is a graph algorithm, whereas the problem in the question does not involve graph structure. – scriptin May 19 '15 at 0:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.