Berechnung für ein PageRanks sparse gerichteten Graphen mit hohem Prozentsatz der deadlinks

Question

Ich bin ein Student der Informatik an der Indiana University, Bloomington. Für eine meiner Forschungsprojekte, ich arbeite auf PageRanks für einen gerichteten Graphen zu berechnen, die sehr spärlich ist und hat einen hohen Anteil an deadlinks.

Mit dem deadlinks I mittleren Knoten, die outdegree Null haben. Manchmal, in einem Diagramm mit vieler deadlinks kann Spinne Falle auftreten. Wie auch immer, ist das Problem, ich bin an PageRanks in diesem Szenario herauszufinden.

Und ich bin mit JUNG (Java Universal-Graph Network) für die PageRanks berechnet wird.

Wenn ich die normale Prozedur,

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();

ich mehr oder weniger die gleichen Pagerank-Werte für alle Knoten, wenn ich weiß, klar, dass nicht der Fall sein sollte. Da einige Knoten in der Grafik, die eine große Anzahl von abgehenden Knoten und sind stark miteinander verbunden sind.

Was ist der vorgeschlagene Ansatz in diesem Fall. Ich weiß, es ist diese Klasse PageRankWithPriors. Soll ich extrahiert zuerst das Netzwerk ohne deadlinks, berechnet PageRanks für sie, und dann zu der deadlinks ihres Rang ausbreiten, bis sie zusammenlaufen.? Im letzteren Fall werden alle Knoten im reduzierten Netz (outdegree! = 0) haben ihre priors gesetzt, während die deadlinks gewohnt.

Bin ich etwas fehlt hier?

Answer 1

Ich glaube nicht, PageRankWithPriors ist das, was Sie wollen.

Welche Version von PageRank verwenden Sie? Die Klasse edu.uci.ics.jung.algorithms.importance.PageRank oder edu.uci.ics.jung.algorithms.scoring.PageRank? Der ehemalige hat sich für das letztere in Jung 2.0 Beta veraltet.

Sie scheinen anders 0 Knoten zu behandeln outdegree, was das Problem sein kann. Die ersteren Spezifikation sagt:

Wahrscheinlichkeit von Knoten gehen u Knoten v gleich (1-alpha) [1 / outdegree (u)] + alpha (1 / | V |)

Wenn u hat keine out-Kanten im Original Graph dann 0 verwendet statt 1 / outdegree (v).

Das scheint falsch, da es zu einem Verlust der Wahrscheinlichkeit führt (die Gesamtwahrscheinlichkeit von u durch irgendein Verfahren verlassen soll gleich 1 sein, und es nicht). Letzteres macht es anders:

Wenn ein Knoten keine ausgehenden Kanten hat, dann ist die Wahrscheinlichkeit einer Einnahme zufälliger Sprung von diesem Eckpunkt (durch default) wirksam 1

Das sollte Wahrscheinlichkeit spart das ist, was Sie wollen.