Calcolare pageranks per un grafo sparse diretto con elevata percentuale di deadlinks
-
01-10-2019 - |
Domanda
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?
Soluzione
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.