Pagerank et ses mathématiques: Explication nécessaire

Question

Je suis étudiant intéressé par le développement d'un moteur de recherche qui indexe les pages de mon pays. J'ai fait des recherches sur les algorithmes à utiliser pour un certain temps maintenant et j'ai identifié HITS et PageRank comme le meilleur là-bas. J'ai décidé d'aller avec PageRank, car il est plus stable que l'algorithme HITS (ou alors j'ai lu).

Je l'ai trouvé d'innombrables articles et documents académiques liés à PageRank, mais mon problème est que je ne comprends pas la plupart des symboles mathématiques qui forment l'algorithme dans ces documents. Plus précisément, je ne comprends pas comment la matrice Google (la matrice stochastique irréductible,) est calculé.

Ma compréhension est basée sur ces deux articles:

• http: // en ligne. redwoods.cc.ca.us/instruct/darnold/LAPROJ/fall2005/levicob/LinAlgPaperFinal2-Screen.pdf
• http://ilpubs.stanford.edu:8090/386/ 1 / 1999-31.pdf

Quelqu'un pourrait-il fournir une explication de base (exemples serait bien) avec moins de symboles mathématiques?

Merci d'avance.

Answer 1

Le défintion formel de PageRank, tel que défini à la page 4 du document cité, est exprimée dans l'équation mathématique avec le symbole « E » drôle (il est en fait la capitale Sigma lettre grecque. Sigma est la lettre « S » qui se tient ici pour sommation ).

En un mot cette formule dit que pour calculer le PageRank de la page X ...

   For all the backlinks to this page  (=all the pages that link to X)
   you need to calculate a value that is
         The PageRank of the page that links to X    [R'(v)]
         divided by 
         the number of links found on this page.    [Nv]
         to which you add
           some "source of rank",  [E(u)] normalized by c
             (we'll get to the purpose of that later.)

     And you need to make the sum of all these values [The Sigma thing]
     and finally, multiply it by a constant   [c] 
        (this constant is just to keep the range of PageRank manageable)

L'idée principale étant cette formule est que toutes les pages Web qui pointent vers une page donnée X à la valeur ajoutent à sa « valeur ». En liant en faveur de cette page à une page, ils sont « vote ». Toutefois, ce « vote » a plus ou moins de poids, en fonction de deux facteurs:

• La popularité de la page que les liens vers X [R '(v)]
• Le fait que la page qui lie à X aussi des liens vers d'autres pages ou non. [Nv]

Ces deux facteurs reflètent des idées très intuitive:

• Il est généralement préférable d'obtenir une lettre de recommandation d'un expert reconnu dans le domaine que d'une personne inconnue.
• Peu importe qui donne la recommandation, par recommandation également donner à d'autres personnes, ils diminuent la valeur de leur recommandation à vous.

Comme vous le remarquez, cette formule fait usage de en quelque sorte une référence circulaire , parce que pour connaître la gamme de page de X, vous devez connaître le PageRank de toutes les pages un lien vers X. Alors, comment faire vous figurez ces valeurs de PageRank? ... C'est là la prochaine question de la convergence expliqué dans la section du document coup de pied dans.

Pour l'essentiel, en commençant par quelques « aléatoires » (ou, de préférence « guess décent » valeurs de PageRank, pour toutes les pages, et en calculant le PageRank avec la formule ci-dessus, les nouvelles valeurs calculées se « mieux », comme vous itérer cette traiter quelques fois. les valeurs Converge , à savoir chacun d'eux se rapprochent de plus en plus de ce qui est la valeur réelle / théorique. par conséquent, en réitérant une quantité suffisante de temps, on arrive à un moment où des itérations supplémentaires ne serait pas ajouter une précision pratique aux valeurs fournies par la dernière itération.

... C'est bien beau en théorie. L'astuce consiste à convertir cet algorithme pour quelque chose d'équivalent, mais qui peut être fait plus rapidement. Il y a plusieurs documents qui décrivent la façon dont cela et des tâches similaires, peut être fait. Je n'ai pas de telles références main gauche, mais ajoutera ces plus tard. Prenez garde qu'ils n'impliquera une bonne dose d'algèbre linéaire.

EDIT: comme promis, voici quelques liens concernant des algorithmes pour calculer le rang de page. calcul efficace du PageRank Haveliwala 1999 /// exploitant la structure du bloc Web pour le calcul PR Kamvar 2003 etal /// Un algorithme en deux étapes rapide pour le calcul du PageRank Lee et Al. 2002

Bien que la plupart des auteurs des liens fournis ci-dessus sont de Stanford, il ne faut pas longtemps pour se rendre compte que la quête de calcul comme PageRank efficace est un champ de recherche importants. Je sais que ce matériel va au-delà de la portée de l'OP, mais il est important de faire allusion au fait que l'algorithme de base est pas pratique pour les grandes toiles.

Pour en finir avec un texte très accessible (mais avec de nombreux liens vers les informations en profondeur), je voudrais mentionner l'excellent article de Wikipedia

Si vous êtes sérieux au sujet de ce genre de choses, vous pouvez envisager une classe d'introduction / recyclage en mathématiques, l'algèbre linéaire particulièrement, et une classe informatique qui traitent avec des graphiques en général. BTW, grande suggestion de Michael Dorfman, dans ce poste, foLa vidéo de r OCW des conférences de 1806.

J'espère que cela aide un peu ...

Answer 2

Si vous êtes sérieux au sujet de l'élaboration d'un algorithme pour un moteur de recherche, je vous recommande sérieusement de suivre un cours d'algèbre linéaire. En l'absence d'un cours en personne, au cours du MIT OCW par Gilbert Strang est assez bonne (conférences vidéo à http://ocw.mit.edu/OcwWeb/Mathematics/18-06Spring-2005/VideoLectures/ ).

Une classe comme ceci serait certainement vous permettre de comprendre les symboles mathématiques dans le document que vous provide-- il n'y a rien dans ce document qui ne serait pas couvert dans une première année du cours d'algèbre linéaire.

Je sais que ce n'est pas la réponse que vous cherchez, mais il est vraiment la meilleure option pour vous. Avoir quelqu'un essayer d'expliquer les symboles individuels ou des algorithmes à vous lorsque vous ne disposez pas d'une bonne compréhension des concepts de base n'est pas un très bon usage du temps de tout le monde.

Answer 3

Ceci est le document que vous avez besoin: http://infolab.stanford.edu/~ backrub / google.html (Si vous ne reconnaissez pas les noms des auteurs, vous trouverez plus d'informations à leur sujet ici: http://www.google.com/corporate/execs.html ).

Les symboles utilisés dans le document, sont décrits dans le document en anglais laïque.

Merci de me faire google.

Answer 4

Vous pouvez également lire le tutoriel d'introduction sur les mathématiques derrière la construction de la matrice de Pagerank écrit par David Austin intitulé Comment Google trouve votre aiguille dans Haystack du Web; il commence par un exemple simple et construit à la définition complète.

Answer 5

"Le 25.000.000.000 $ Eigenvector: l'algèbre linéaire derrière Google" . de Rose-Hulman est un peu obsolète, parce que maintenant page Rank est le problème d'algèbre linéaire 491B $. Je pense que le papier est très bien écrit.

"Programmation Intelligence Collective" a une belle discussion sur le Page Rank ainsi.

Answer 6

Duffymo a obtenu le meilleur refernce à mon avis. J'ai étudié l'algorithme de classement de la page dans mon année de premier cycle supérieur. Page rank fait ce qui suit:

1. définir l'ensemble des pages Web en cours comme les états d'une chaîne de Markov finie.

2. Définir la probabilité d'une transition à partir du site u à v où l'existence d'un lien sortant de v à partir de u soit

   1 / u_ {n} où u_ {n} est le nombre de liens en allant de u.

3. Supposons que la chaîne de Markov défini ci-dessus est irréductible (ce qui peut être exécutée avec seulement une légère dégradation des résultats)

4. On peut montrer toutes les chaînes de Markov irréductible finie a une distribution stationnaire. Définir le rang de page pour la distribution stationnaire, c'est-à-dire le vecteur qui détient la probabilité d'une particule aléatoire pour finir à chaque site donné que le nombre de transitions d'état va à l'infini.

Google utilise une légère variante de la méthode de la puissance pour trouver la distribution stationnaire (la méthode de la puissance trouve des valeurs propres dominantes). Autre que qu'il n'y a rien à lui. Son assez simple et élégante et probablement l'une des applications les plus simples des chaînes de Markov je peux penser, mais il est beaucoup de wortha d'argent!

Donc tout l'algorithme de pagerank n'est prise en compte de la topologie du Web comme une indication de savoir si un site doit être important. Les liens entrants un site a plus la probabilité d'une particule aléatoire passer son temps sur le site sur une quantité infinie de temps.

Answer 7

Si vous voulez en savoir plus sur le classement des pages avec moins de mathématiques, puis ce est très bon tutoriel sur les opérations de la matrice de base. Je le recommande pour tous ceux qui ont peu d'expérience de mathématiques, mais veut plonger dans les algorithmes de classement.