Cálculo pageranks para un grafo dirigido escaso con alto porcentaje de vínculos muertos

Question

Soy un estudiante graduado en ciencias de la computación en la Universidad de Indiana, Bloomington. Para uno de mis proyectos de investigación, estoy trabajando en el cálculo de pageranks para un grafo dirigido que es muy escasa y tiene un alto porcentaje de vínculos muertos.

Por vínculos muertos I nodos medias que tienen cero grado de salida. A veces, en un gráfico con una gran cantidad de vínculos muertos, se pueden producir trampas de araña. De todas formas, el problema que me interesa es averiguar pageranks en este escenario.

Y estoy usando JUNG (Java Red Gráfica Universal) para el cálculo de los pageranks.

Cuando utilizo el procedimiento normal,

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

me sale más o menos los mismos valores de PageRank para todos los nodos, cuando sé claramente que no debería ser el caso. Como algunos nodos en el gráfico tienen un gran número de nodos de salida y están fuertemente interconectadas.

¿Cuál es el enfoque sugerido en este caso. Sé que hay esta clase PageRankWithPriors. Debería extraer primero la red sin vínculos muertos, pageranks calcular para ellos, y luego propagar su rango a los vínculos muertos hasta que convergen.? En el último caso, todos los nodos de la red reducida (grado de salida! = 0) tendrán fijan sus distribuciones previas, mientras que los vínculos muertos costumbre.

Me estoy perdiendo algo aquí?

Answer 1

No creo PageRankWithPriors es lo que desea.

¿Qué versión de PageRank está usando? El edu.uci.ics.jung.algorithms.importance.PageRank clase o edu.uci.ics.jung.algorithms.scoring.PageRank? El primero ha sido desaprobado en favor de este último en Jung 2.0 Beta.

Se parece a tratar grado de salida 0 nodos de manera diferente, que puede ser su problema. especificación de la antigua dice:

  

probabilidad de ir desde el nodo u para   nodo v es igual a   (1-alfa) [1 / grado de salida (u)] +   alfa (1 / | V |)

     

Si u no tiene bordes fuera en el original   gráfico a continuación, 0 se utiliza en lugar de   1 / grado de salida (v).

Esto parece un error, ya que conduce a una pérdida de probabilidad (la probabilidad total de U dejando por algún método debe ser igual a 1, y no lo hace). Este último hace de manera diferente:

  

Si un vértice no tiene bordes salientes,   entonces la probabilidad de tomar una   salto azar de ese vértice es (por   predeterminado) efectivamente 1

Esto se debe conservar la probabilidad de que es lo que desea.