Pour déterminer le score de chaque page,
o n attribue d 'abo rd à c hac une le mê me
score (égal à 25 % ici). Ensuite,on ti e nt
compte des interfére nces entre les pages.
A in s i , la page B po inte s ur les d e u x
pages A et D, auxquelles elle va donc donne r la mo itié de son score . De mê me,
e l le reço it le score de la page A et le
ti ers de celui de la page C. Ces di verses
form ules sont appliquées plus ie urs fo is ,
et do nne nt le tableau sui vant :
Page Score 1
Score2
Score 3
A
25 %
12,5 %
16,66 %
B
25 %
33.33 %
15 ,27 %
c
25 %
8,33 %
2,77 %
D
25 %
45 ,83 %
65 ,27 %
Pa e Score4
Score 5
Score6
A
7,63 %
8,79 %
3,97 %
B
17,59 %
7,94 %
8,90 %
c
0 ,92 %
0 ,3 1 %
0,10 %
D
73,84 %
82,94 %
87,02 %
li est in util e de continue r lo ng te mps
pour que le systè me se stabilise. Il en ressort le classeme nt des pages : D , B , A et
C , da n s ce t ord re. L es m o t e ur s d e
rec herche o pè re nt a ins i, ma is avec des
millie rs de pages. Mathé matique me nt ,
cette faço n de procéde r appelle le ca lc ul matric ie l (voir e n e ncadré).
Le princ ipe est d o nc réc urs if, l 'a lgori thme auss i. Les calcul s sont é normes ,
infaisab les à la ma in ma is s imples da ns
leurs princ ipes. S i vo us avez un s ite e t
q ue vo us le dés irez v is ible, ce princ ipe
montre q u ' il est inutile de paye r po ur
ce la , il suffit de le fa ire connaître ! Certains sites po inte ro nt dessus e t l' affa ire
sera lancée.
H.L.
Références
• Co mment Goog le classe les pages. Tan gente
Sup 44-45 , 2008.
• Le théorème de Perron-Frobenius. Tangell/e Sup
44-45 ,2008.
• L'algorithme P(lgeR(lnk de Google : promen(lde
sur l(l Toile. Tangente 130 , 2009.
• Les marrices . Bibliot hèque Tangente 44, 20 12 .
CHANGER LE MONDE
Le graphe du Web
Le Web peut être représenté comme un graphe gigantesque. Ce graphe énumère toutes les pages avec leurs
connections, celles-ci correspondant aux liens que l'on
peut atteindre en cliquant. Ce graphe est immense puisqu'il réunit plusieurs millions de pages. Vu de loin, il prend
une forme de nœud papillon.
0
Composantes déconnectées ()
10%
0
0
Le nœud papillon. Les Dèches indiquent le sens des liens.
L'essentiel des pages (90 %) sont connectées entre elles,
dans un sens, dans l'autre ou les deux. Les autres forment
quelques composantes déconnectées. Celles-ci ne pointant
qu'entre elles n'intéressent pas le surfeur moyen. En revanche,
elles pourraient intéresser la police car il peut s'agir de
réseaux de malfaiteurs, comme les pédophiles ou des terroristes par exemple. Les repérer est un problème intéressant aussi bien mathématiquement que pratiquement. Le
critère est exactement l'inverse des moteurs de recherche
qui, au contraire, classent les pages les plus populaires.
Si l'on exclut ces composantes déconnectées, le Web est
constitué d'un gros noyau central, contenant 27 % des pages.
Leur particularité est d'être accessibles les unes des autres
en quelques clics. Autour de ce noyau, on trouve les pages
liées au noyau dans un sens ou dans l'autre ( on y va ou on
en vient), plus deux branches non accessibles du noyau
mais connectées en sens inverse.
A un niveau plus local, on peut reconnaître des structures
particulières, comme des groupes de pages pointant toutes
vers la même ou les mêmes, l'inverse étant faux. Ces structures représentent des groupes de fans, que l'on peut ainsi
retrouver.
Hors-série n° 52. Mathematiques & informatique Tangente 145
o n attribue d 'abo rd à c hac une le mê me
score (égal à 25 % ici). Ensuite,on ti e nt
compte des interfére nces entre les pages.
A in s i , la page B po inte s ur les d e u x
pages A et D, auxquelles elle va donc donne r la mo itié de son score . De mê me,
e l le reço it le score de la page A et le
ti ers de celui de la page C. Ces di verses
form ules sont appliquées plus ie urs fo is ,
et do nne nt le tableau sui vant :
Page Score 1
Score2
Score 3
A
25 %
12,5 %
16,66 %
B
25 %
33.33 %
15 ,27 %
c
25 %
8,33 %
2,77 %
D
25 %
45 ,83 %
65 ,27 %
Pa e Score4
Score 5
Score6
A
7,63 %
8,79 %
3,97 %
B
17,59 %
7,94 %
8,90 %
c
0 ,92 %
0 ,3 1 %
0,10 %
D
73,84 %
82,94 %
87,02 %
li est in util e de continue r lo ng te mps
pour que le systè me se stabilise. Il en ressort le classeme nt des pages : D , B , A et
C , da n s ce t ord re. L es m o t e ur s d e
rec herche o pè re nt a ins i, ma is avec des
millie rs de pages. Mathé matique me nt ,
cette faço n de procéde r appelle le ca lc ul matric ie l (voir e n e ncadré).
Le princ ipe est d o nc réc urs if, l 'a lgori thme auss i. Les calcul s sont é normes ,
infaisab les à la ma in ma is s imples da ns
leurs princ ipes. S i vo us avez un s ite e t
q ue vo us le dés irez v is ible, ce princ ipe
montre q u ' il est inutile de paye r po ur
ce la , il suffit de le fa ire connaître ! Certains sites po inte ro nt dessus e t l' affa ire
sera lancée.
H.L.
Références
• Co mment Goog le classe les pages. Tan gente
Sup 44-45 , 2008.
• Le théorème de Perron-Frobenius. Tangell/e Sup
44-45 ,2008.
• L'algorithme P(lgeR(lnk de Google : promen(lde
sur l(l Toile. Tangente 130 , 2009.
• Les marrices . Bibliot hèque Tangente 44, 20 12 .
CHANGER LE MONDE
Le graphe du Web
Le Web peut être représenté comme un graphe gigantesque. Ce graphe énumère toutes les pages avec leurs
connections, celles-ci correspondant aux liens que l'on
peut atteindre en cliquant. Ce graphe est immense puisqu'il réunit plusieurs millions de pages. Vu de loin, il prend
une forme de nœud papillon.
0
Composantes déconnectées ()
10%
0
0
Le nœud papillon. Les Dèches indiquent le sens des liens.
L'essentiel des pages (90 %) sont connectées entre elles,
dans un sens, dans l'autre ou les deux. Les autres forment
quelques composantes déconnectées. Celles-ci ne pointant
qu'entre elles n'intéressent pas le surfeur moyen. En revanche,
elles pourraient intéresser la police car il peut s'agir de
réseaux de malfaiteurs, comme les pédophiles ou des terroristes par exemple. Les repérer est un problème intéressant aussi bien mathématiquement que pratiquement. Le
critère est exactement l'inverse des moteurs de recherche
qui, au contraire, classent les pages les plus populaires.
Si l'on exclut ces composantes déconnectées, le Web est
constitué d'un gros noyau central, contenant 27 % des pages.
Leur particularité est d'être accessibles les unes des autres
en quelques clics. Autour de ce noyau, on trouve les pages
liées au noyau dans un sens ou dans l'autre ( on y va ou on
en vient), plus deux branches non accessibles du noyau
mais connectées en sens inverse.
A un niveau plus local, on peut reconnaître des structures
particulières, comme des groupes de pages pointant toutes
vers la même ou les mêmes, l'inverse étant faux. Ces structures représentent des groupes de fans, que l'on peut ainsi
retrouver.
Hors-série n° 52. Mathematiques & informatique Tangente 145