Calcolare pageranks per un grafo sparse diretto con elevata percentuale di deadlinks

Question

Sono uno studente laureato in informatica presso l'Indiana University, Bloomington. Per uno dei miei progetti di ricerca, sto lavorando sul calcolo PageRanks per un grafo orientato che è molto scarsa e ha un'alta percentuale di deadlinks.

Per deadlinks I nodi medi che hanno lo zero outdegree. A volte, in un grafico con un sacco di deadlinks, possono verificarsi trappole ragno. In ogni modo, il problema che mi interessa è scoprire PageRanks in questo scenario.

E sto usando JUNG (Java universale grafico Network) per il calcolo dei PageRanks.

Quando uso la procedura 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();

ho più o meno gli stessi valori di PageRank per tutti i nodi, quando so chiaramente che non dovrebbe essere il caso. Come alcuni nodi del grafo hanno un gran numero di nodi in uscita e sono fortemente interconnessi.

Qual è l'approccio suggerito in questo caso. So che c'è questo PageRankWithPriors classe. Devo prima di estrarre la rete senza deadlinks, PageRanks calcolare per loro, e poi diffondere il loro rango ai deadlinks fino a quando non convergono.? In quest'ultimo caso, tutti i nodi della rete ridotta (outdegree! = 0) avranno i priori impostato, mentre le deadlinks wont.

Mi manca qualcosa qui?

Answer 1

Non credo PageRankWithPriors è ciò che si desidera.

Quale versione di PageRank stai usando? Il edu.uci.ics.jung.algorithms.importance.PageRank classe o edu.uci.ics.jung.algorithms.scoring.PageRank? Il primo è stato deprecato in favore di quest'ultimo a Jung 2.0 Beta.

Si sembrano trattare outdegree 0 nodi in modo diverso, che può essere il problema. Il dell'ex specifiche dice:

  

probabilità di andare dal nodo u   nodo v è uguale a   (1-alfa) [1 / outdegree (u)] +   alpha (1 / | V |)

     

Se la u non ci sono fuori-bordo in originale   grafico quindi 0 è usato al posto di   1 / outdegree (v).

Che sembra sbagliato, in quanto porta a una perdita di probabilità (la probabilità totale di lasciare u da qualche metodo deve essere uguale 1, e non è così). Quest'ultimo fa in modo diverso:

  

Se un vertice non presenta spigoli uscenti,   allora la probabilità di prendere una   salto casuale da tale vertice è (by   di default) in modo efficace 1

che dovrebbe conservare probabilità che è quello che si desidera.