MarcheAuHasard

MeatballWiki | RecentChanges | Random Page | Indices | Categories

Cette page a démarré sur AccumulatedRandomWalk

: http://sunir.org/meatball/walk.html

C'est une bidouille bon marché pour éviter de faire beaucoup de mathématiques compliquées afin de calculer quels sont les faisceaux. Ce SchémaIndexation pioche une page au hasard dans la base de donnnées et suit ses RétroLiens, conservant la trace du nombre de visites vers chaque page pendant qu'il le fait. La profondeur de la marche actuelle est de 3 (Je ne pense pas que beaucoup de personnes soient prêtes à voyager plus loin que 3 pages avant de s'ennuyer) et la taille est de 5000 essais.

La raison pour laquelle cela suit les RétroLiens est que nous voulons trouver des pages "à partir desquelles" les personnes aimeront démarrer, et non pas aller "vers". Par conséquent, nous inversons la direction de la marche en faisant essentiellement ce qu'un utilisateur typique ferait sur un rebours.

L'échec principal dans ce modèle, hormis le fait de pouvoir mentir sur les statistiques, est que cela s'initialise avec une page "au hasard". Toutes les pages ne peuvent pas être accédées par hasard. Mais le fait de charger cela avec disons les statistiques tirées des CompteursHits pourrait biaiser inutilement cela avec une pratique existante. Si la pratique existante est pauvre, la détection du centre sera pauvre. Peut-être que ce n'est néanmoins pas une grosse perte.

Un autre échec est que cela part du principe que tous les liens sont égaux, et que toutes les collections de liens sont égales, ce qui est la raison pour laquelle EricScheidRandomThoughts est sur la liste. Que se passerait t'il si je mets la liste des "centres&amp" sur une page -- est-ce que cette page flotterait en haut de la liste ?

Code source sur http://sunir.org/src/meatball/IndexingSchemes.

En passant, il existe un moyen parfaitement adapté qui pourrait être faisable sur un plan inforamtique pour quelques wikis, tout spécialement les plus petits. Pour chaque noeud la récursirvité suit chaque lien enfant, etc. vers une profondeur de d, en comptant les noeuds. Les noeuds enracines les hyper-arblres les plus grands sont les meilleurs centres.

<pre> Centres(graph G)

    for each node N in G
        sizes[N] &lt;-- countChildren N, d
    end for

    for the 25 largest sizes, print their respective nodes.

end Centres

countChildren(node N, depth d)

     size &lt;-- 1
     return size if d = 0.

     for each child C of N
         size &lt;-- size + countChildren( C, d-1 )
     end for

     return size

end countChildren </pre>

Néanmoins c'est supercher sur un grand wiki, ou pour un grand d, ou pour un wiki avec des liens denses (comme le sont la plupart des wikis). La MarcheAuHasard est meilleur marché, à ce stade probalement adaptée.

Voici un autre exemple où la récursion permet un algorithme propre mais moins qu'optimal. Le coeur du problème est que countChildren sera appelé de nombreuses fois pour la même page (& same d). Ceci pourrait être résolu en cachant les résultats de chaque appel de countChildren ("memoization"), ou en utilisant un algorithme non récursif.

En supposant que je ne sois pas trop confus, (pas nécessairement une affirmation sûre), voici un algorithme non récursif qui calcule les même chiffres que countChildren. (pardon le pseudo-perl) :

<pre> foreach my $page (@pages) {

  $count{$page}[0] = 1;

} for ($d = 1; $d < 3; $d++) {

  foreach my $page (@pages) {
    $count{$page}[$d] = 0;
  }
  foreach my $child (@pages) {
    foreach my $parent (backlinks($child)) {
      $count{$parent}[$d] += $count{$child}[$d - 1];
    }
  }

}

</pre> Then, I think, <pre>

 countChildren($page,3) == sum(@{count{$page}}[0 .. 3])

</pre>

Notez que $count{$page}[0] (normalisé de manière appropriée) est le pdf de votre marche au hasar à l'étape zéro (c.a.d. votre distribusion uniforme initale à travers toutes les pages). $Count{$page}[1] donne le pdf décrivant où vous serez une étape dans votre marche. (et ainsi de suite...)

-- JeffDairiki

For reference, the "starting points" on 2001-09-30 are:

Pour référence, les points de départs au 29 avril 2005 sont :

Note en LangueFrançaise

Hormis IgeneratorWiki, on remarquera que 5 pages "centres" sont en LangueFrançaise. Les pages centrées peuvent être corrigées ou traduites :

AbsentLeader est traduit en LeaderAbsent,
WikiSyntax peut se traduire en SyntaxeWiki?,
AccumulatedRandomWalk est une MarcheAuHasard,
AccessLevels - NiveauxAccès,
MeatballDigest se traduit par RésuméMeatball,
StartingPoints par PointsDeDéparts,
RecentChangesDigested? par ModificationsRécentesDigérées?,
OtherHypermedia par AutresHypermédia, etc..

... ...

SockPuppet est traduit par ChaussetteMarionnette (on regardera la différence avec la CommunityWiki:PoupéeWiki)

-- ChristopheDucamp

PageTranslation LangueFrançaise AccumulatedRandomWalk DossierThéorieGraphe? DossierSchémaIndexation

MarcheAuHasard

Note en LangueFrançaise

Discussion