Calcul pageranks pour un graphe orienté clairsemée avec un pourcentage élevé de deadlinks

Question

Je suis un étudiant diplômé en informatique à l'Université de l'Indiana, Bloomington. Pour un de mes projets de recherche, je travaille sur le calcul pageranks pour un graphe orienté qui est très rare et a un pourcentage élevé de deadlinks.

Par deadlinks Je veux dire des noeuds qui ont zéro degré sortant. Parfois, dans un graphique avec beaucoup de deadlinks, pièges araignée peuvent se produire. Quoi qu'il en soit, le problème que je suis intéressé est de trouver pageranks dans ce scénario.

J'utilise JUNG (Java Universal Graph Réseau) pour le calcul des pageranks.

Quand j'utilise la procédure normale,

Graph<String, String> jungGraph = new DirectedSparseGraph<String, String>();
PageRank<String, String> pagerank = new PageRank<String,String>(jungGraph, 0.2);
pagerank.setMaxIterations(20);
pagerank.setTolerance(0.000001);
pagerank.evaluate();

Je reçois plus ou moins les mêmes valeurs pagerank pour tous les nœuds, quand je sais clairement que ne devrait pas être le cas. Comme certains noeuds du graphique ont un grand nombre de noeuds sortants et sont fortement reliés entre eux.

Quelle est l'approche proposée dans ce cas. Je sais qu'il ya cette PageRankWithPriors de classe. Dois-je d'abord extraire le réseau sans deadlinks, pageranks de calculate pour eux, et propager leur rang aux deadlinks jusqu'à ce qu'ils convergent.? Dans ce dernier cas, tous les nœuds du réseau réduite (! = 0 degré sortant) auront leurs prieurs fixés, alors que les deadlinks wont.

Suis-je manque quelque chose ici?

Answer 1

Je ne pense pas PageRankWithPriors est ce que vous voulez.

Quelle version de PageRank utilisez-vous? La edu.uci.ics.jung.algorithms.importance.PageRank de classe ou edu.uci.ics.jung.algorithms.scoring.PageRank? Le premier a été dépréciée en faveur de ce dernier en version bêta Jung 2.0.

Ils semblent traiter différemment des nœuds 0 degré sortant, qui peut être votre problème. spec de l'ancien dit:

  

probabilité de passer du noeud u   le noeud v est égal à   (1-alpha) [1 / degré sortant (u)] +   alpha (1 / | V |)

     

Si u n'a pas sur-bords dans l'original   graphique alors 0 est utilisé au lieu de   1 / degré sortant (v).

Cela semble mal, car elle conduit à une perte de probabilité (la probabilité totale de partir par une méthode u doit être égale à 1, et il ne fonctionne pas). Ce dernier différemment fait:

  

Si un sommet n'a pas de bords sortants,   alors la probabilité de prendre un   saut aléatoire de ce sommet est (par   par défaut) efficacement 1

Cela devrait conserver la probabilité qui est ce que vous voulez.