CheiRank

Le CheiRank est un vecteur propre avec une valeur propre réelle maximale de la matrice Google construite pour un réseau dirigé avec les directions inversées des liens. Il est similaire au vecteur PageRank , qui classe les nœuds du réseau en moyenne proportionnellement à un nombre de liens entrants étant le vecteur propre maximal de la matrice Google avec une direction initiale donnée des liens. En raison de l'inversion des directions des liens, le CheiRank classe les nœuds du réseau en moyenne proportionnellement à un nombre de liens sortants. Étant donné que chaque nœud appartient à la fois aux vecteurs CheiRank et PageRank, le classement du flux d'informations sur un réseau dirigé devient bidimensionnel .

Pour un réseau orienté donné, la matrice Google est construite de la manière décrite dans l'article Google matrix . Le vecteur PageRank est le vecteur propre avec la valeur propre réelle maximale . Il a été introduit dans et est discuté dans l'article PageRank . De la même manière, le CheiRank est le vecteur propre avec la valeur propre réelle maximale de la matrice construite de la même manière que mais en utilisant la direction inversée des liens dans la matrice d'adjacence initialement donnée . Les deux matrices et appartiennent à la classe des opérateurs de Perron-Frobenius et selon le théorème de Perron-Frobenius, les vecteurs propres CheiRank et PageRank ont ​​des composantes non négatives qui peuvent être interprétées comme des probabilités. Ainsi, tous les nœuds du réseau peuvent être classés dans un ordre de probabilité décroissant avec des rangs pour CheiRank et PageRank respectivement. En moyenne, la probabilité PageRank est proportionnelle au nombre de liens entrants avec . Pour le réseau World Wide Web (WWW), l'exposant où est l'exposant pour la distribution des liens entrants. De la même manière, la probabilité CheiRank est en moyenne proportionnelle au nombre de liens sortants avec où est l'exposant pour la distribution des liens sortants du WWW. Le CheiRank a été introduit pour le réseau d'appel de procédure du logiciel Linux Kernel en, le terme lui-même a été utilisé dans Zhirov. Alors que le PageRank met en évidence des nœuds très connus et populaires, le CheiRank met en évidence des nœuds très communicatifs. Les nœuds PageRank et CheiRank supérieurs ont une certaine analogie avec les autorités et les hubs apparaissant dans l' algorithme HITS mais le HITS dépend de la requête tandis que les probabilités de rang et classent tous les nœuds du réseau. Étant donné que chaque nœud appartient à la fois au CheiRank et au PageRank, nous obtenons un classement bidimensionnel des nœuds du réseau. Il y avait eu des études précoces sur le PageRank dans les réseaux avec direction inversée des liens mais les propriétés du classement bidimensionnel n'avaient pas été analysées en détail.

Un exemple de distribution de nœuds dans le plan PageRank et CheiRank est présenté dans la Fig.1 pour le réseau d'appels de procédure du logiciel Linux Kernel.

Français La dépendance de pour le réseau de liens hypertexte des articles de Wikipédia en anglais est illustrée dans la Fig.2 de Zhirov. La distribution de ces articles dans le plan du PageRank et du CheiRank est illustrée dans la Fig.3 de Zhirov. La différence entre le PageRank et le CheiRank est clairement visible à partir des noms des articles de Wikipédia (2009) avec le rang le plus élevé. Au sommet du PageRank, nous avons 1.États-Unis, 2.Royaume-Uni, 3.France tandis que pour le CheiRank, nous trouvons 1.Portail : Contenu/Aperçu des connaissances/Géographie et lieux, 2.Liste des dirigeants d'État par année, 3.Portail : Contenu/Index/Géographie et lieux. Clairement, le PageRank sélectionne d'abord les articles sur un sujet largement connu avec un grand nombre de liens entrants tandis que le CheiRank sélectionne d'abord les articles très communicatifs avec de nombreux liens sortants. Comme les articles sont distribués en 2D, ils peuvent être classés de différentes manières correspondant à la projection de l'ensemble 2D sur une ligne. Les lignes horizontales et verticales correspondent au PageRank et au CheiRank, 2DRank combine les propriétés du CheiRank et du PageRank comme indiqué dans Zhirov. Il donne les meilleurs articles de Wikipédia 1. Inde, 2. Singapour, 3. Pakistan.

Le classement 2D met en évidence les propriétés des articles de Wikipédia d'une manière nouvelle, riche et fructueuse. Selon le PageRank, les 100 premières personnalités décrites dans les articles de Wikipédia ont des activités dans 5 catégories principales : 58 (politique), 10 (religion), 17 (arts), 15 (sciences), 0 (sport) et donc l'importance des hommes politiques est fortement surestimée. Le CheiRank donne respectivement 15, 1, 52, 16, 16 tandis que pour le 2DRank on trouve 24, 5, 62, 7, 2. Ce type de classement 2D peut trouver des applications utiles pour divers réseaux dirigés complexes, y compris le WWW.

CheiRank et PageRank apparaissent naturellement pour le réseau commercial mondial, ou le commerce international , où ils sont liés respectivement aux flux d'exportation et d'importation pour un pays donné.

Les possibilités de développement de moteurs de recherche bidimensionnels basés sur le PageRank et le CheiRank sont envisagées. Les réseaux dirigés peuvent être caractérisés par le corrélateur entre les vecteurs PageRank et CheiRank : dans certains réseaux, ce corrélateur est proche de zéro (par exemple, le réseau Linux Kernel) tandis que d'autres réseaux ont des valeurs de corrélateur élevées (par exemple, Wikipédia ou les réseaux universitaires).

Français Un exemple simple de construction des matrices Google et , utilisées pour la détermination des vecteurs PageRank et CheiRank associés, est donné ci-dessous. L'exemple de réseau dirigé à 7 nœuds est illustré à la Fig.4. La matrice , construite avec les règles décrites dans l'article Matrice Google , est illustrée à la Fig.5 ; la matrice Google associée est et le vecteur PageRank est le vecteur propre droit de avec la valeur propre unitaire ( ). De la même manière, pour déterminer le vecteur propre CheiRank toutes les directions des liens de la Fig.4 sont inversées, puis la matrice est construite, selon les mêmes règles appliquées pour le réseau avec des directions de liens inversées, comme illustré à la Fig.6. La matrice Google associée est et le vecteur CheiRank est le vecteur propre droit de avec la valeur propre unitaire ( ). Voici le facteur d'amortissement pris à sa valeur habituelle.