Pagerank vs SVD

Question

Pagerank fonctionne sur le noeudgraph d'une série de pages et les bords dirigés formés par leurs liens respectifs vers l'intérieur et vers l'extérieur. Ainsi, le rang d'une page particulière est globalement un effet induit localement dans le nodegraph. D'autre part, fonctionne sur une matrice entière de valeurs, et n'a pas de directionnalité - un lien entre le site A et le site B ne serait enregistré comme 1 sur l'élément de la matrice correcte. C'est un système global, donc le classement est un effet global. Compte tenu de l'extrême rareté des matrices dérivées du web, je m'attendrais à ce que SVD soit un mauvais joueur ici, car il nécessite un jeu de données complet, et a des besoins en mémoire importants.

Est-ce vrai? Est-ce que Pagerank surpasse largement SVD parce qu'il s'agit d'un algorithme basé sur nodegraph? Comment Pagerank peut-il déduire la pertinence sémantique d'une page au-delà du nombre de fois qu'un mot est mentionné? Ou serait-ce une deuxième étape, effectuée après que Pagerank ait classé les pages?

Answer 1

Il y a deux problèmes ici: quelle mesure est facile à calculer et qui fournit l'information que nous cherchons? Je ne connais pas la réponse à l'une ou l'autre question, mais je peux peut-être donner une réponse partielle.

Tout d'abord, la pertinence. Les deux quantités sont centrality mesures, pour utiliser un terme de la théorie des réseaux. Le PageRank calcule (une variante de) la centralité du vecteur propre, tandis que le SVD conduit apparemment à l'algorithme HITS (Hyperlink-Induced Topics Search). J'ai reçu ceci de this handout de Peter Dodds (Université du Vermont). Ils mesurent différentes choses, mais il n'est pas clair pour moi quel est le plus pertinent pour mesurer l'importance d'une page Web.

Deuxièmement, le coût de calcul. Mathématiquement, le PageRank est le vecteur propre dominant de la matrice d'adjacence (modifiée) - comme expliqué sur la page Wikipedia - alors que HITS donne le vecteur singulier dominant de la matrice d'adjacence. Les deux sont définis par le réseau global de pages Web et les liens entre eux, et les deux peuvent être calculés en ne considérant que le graphe de nœud localement. Donc, à première vue, je pense que le coût de calcul est à peu près égal. En conclusion, je ne sais pas pourquoi PageRank est meilleur que SVD; il n'est même pas clair pour moi que c'est mieux que SVD.

Answer 2

Notez que PageRank utilise une matrice de marche aléatoire téléportée. La téléportation est importante pour éviter les vecteurs propres localisés (de faible degré) de la matrice de marche aléatoire. Je pense que PageRank est meilleur que HITS, parce que la matrice de marche aléatoire, qui est une matrice d'adjacence normalisée en degrés, diminue les effets des nœuds et des boucles de gros degrés, contrairement aux HITS où les nœuds de grand degré pourraient faire des vecteurs localisés.