WWeebb SScciieennccee MMaasstteerr 11 IIFFII Andrea G. B. Tettamanzi Université de Nice Sophia Antipolis Département Informatique [email protected] Andrea G. B. Tettamanzi, 2014 1 CM - Séance 3 PageRank et comment Google transforme des mots en argent Andrea G. B. Tettamanzi, 2014 2 Introduction • Quelques chiffres sur Google (mise à jour : 25 mai 2014) – Capitalisation de marché : ~ 375 milliards de dollars – Chiffre d'affaires : 62 milliards de dollars $590/s !!! – Bénéfices avant intérêts, impôts, etc. : 18.6 milliards de $ – Environs 54 000 employés • Par comparaison – PIB du Luxembourg : 57 milliards de dollars – Si Google était un pays, il serait le 70ème par PIB sur 193 – En 2013, Google était 15ème au monde par capitalisation parmi les entreprises cotées en bourse • Pas mal pour un « simple » moteur de recherche… Andrea G. B. Tettamanzi, 2014 3 La clé du succès • Le succès de Google se base sur deux algorithmes : – PageRank – AdWords + AdSense • Le premier permet de trier les résultats des recherches : – valeur d'usage – il a imposé Google comme leader du marché • Le deuxième génère l'impression de messages publicitaires ciblés aux intérêts du public d'une page Web : – valeur d'échange – AdWords permet d'acheter du trafic, AdSense de le vendre Andrea G. B. Tettamanzi, 2014 4 Plan • PageRank • AdWords + AdSense • TD Andrea G. B. Tettamanzi, 2014 5 1ère Partie PageRank Andrea G. B. Tettamanzi, 2014 6 Intuition de fond • Le Web comme graphe orienté – Ses nœuds sont les pages HTML – Ses arcs sont les hyperliens <a href=''…''> . . . </a> • Quelles pages visiterait un surfeur aléatoire ? – Le surfeur aléatoire commencerait par une page arbitraire – Il sauterait d'une page à la suivante en cliquant sur un hyperlien choisi au hasard • Idée : mesurer l'importance d'un page par la probabilité qu'elle soit visitée à l'instant t par un surfeur aléatoire ! • Cette probabilité est la fréquence de visite de la page Andrea G. B. Tettamanzi, 2014 7 Événements Espace échantillon ou univers D   A B Andrea G. B. Tettamanzi, 2014 8 Variables aléatoires   0 Andrea G. B. Tettamanzi, 2014 9 Processus Stochastiques Une suite de variables aléatoires Chacune dotée de sa propre distribution de probabilité. Notation: Andrea G. B. Tettamanzi, 2014 10