¿Por qué mis resultados de pagerank son peores cuando elimino nodos con puntuaciones bajas?

Question

Estaba jugando con el uso de pagerank en los gráficos para hacer inferencias y los resultados parecían bastante buenos, pero pensé que los resultados mejorarían si eliminaba los nodos de puntuación más baja (que tienden a no ser buenos resultados en general).

Pensé que esto mejoraría los resultados, pero parece que está ocurriendo lo contrario, mis inferencias son muy inexactas ahora.

Así que mi pregunta, en general, ¿es mejor mantener el universo lo más grande posible al hacer inferencias o lo más probable es que esté haciendo algo mal aquí?

Gracias,

Nota: Soy un poco nuevo en matemáticas así que estoy preguntando esto no sólo específica a pagerank pero a otro tipo de inferencia / ranking de algo. Siempre he pensado que limpiar los datos es bueno, pero ahora no estoy seguro.

Answer 1

La eliminación de nodos puede mejorar o no la calidad de la clasificación.

1. Consideremos un grafo con vértices $a, a', b_1\cdots b_{1000}, b'_1\cdots b'_{50}, c_1\cdots c_{1000}$ . Con bordes $a' \to a$ , $b_i\to a$ . $b'_i \to a'$ y $c_i \to b_i$ . Si se poda el grafo para eliminar todos los vértices sin enlaces entrantes (que serían $c_i$ y $b'_i$ ), entonces el peso sobre $a'$ bajaría en comparación con $a$ . Y se puede decir que así se obtienen "mejores resultados".
2. Por otro lado, considere su gráfico inicial como el $a, a', b_1\cdots b_{1000}, b'_1\cdots b'_{50}, c', d'$ con $a' \to a$ , $b_i \to a$ , $b'_i \to a'$ , $c' \to a'$ y $d' \to c'$ . PageRank debería mostrar claramente que $a$ es el mejor. Pero si eliminas todos los vértices sin enlaces entrantes, te quedas con $a,a',c',d'$ y la clasificación de $a$ y $a'$ se acercaría.

Básicamente, el problema es que PageRank se calcula de forma recursiva. Así que, dependiendo de la naturaleza exacta de tu gráfico, el efecto de la eliminación de algunos nodos de baja puntuación puede variar. Por poner otro ejemplo:

Sea su gráfica dada por $a_1,\ldots, a_{1000}, b_1, \ldots b_{1000}, c_1, \ldots, c_5, d_1, \ldots d_{100}$ . Deja las flechas $a_{i+1} \to a_i$ y $b_{i+1}\to b_i$ . Y que $c_k \to a_{1000}$ y $d_k\to b_{1000}$ . Entonces en este esquema $b_1$ es un objeto mejor clasificado que $a_1$ . Pero si eliminas sólo el 5% de los vértices eliminando todos los $c_i$ y $d_i$ entonces PageRank no puede decir $a_1$ y $b_1$ aparte.