¿Es posible hacer pagerank sin todo el conjunto de datos?

Question

Lo siento si esto es tonto, pero estaba pensando que debería dar una oportunidad. Digamos que tengo un gráfico que es enorme (por ejemplo, 100 mil millones de nodos). Neo4J admite 32 mil millones y otros admiten más o menos lo mismo, por lo que no puedo tener todo el conjunto de datos en una base de datos al mismo tiempo, ¿puedo ejecutar pagerank si es un gráfico dirigido (sin bucles) y cada conjunto de nodos se conecta al siguiente conjunto de nodos (por lo que no se crearán nuevos enlaces hacia atrás, solo se crearán nuevos enlaces a nuevos conjuntos de datos).

¿Hay alguna manera de que pueda tomar los puntajes del pagerank anterior y aplicarlos a nuevos conjuntos de datos (solo me importa el pagerank para el conjunto de datos más reciente pero necesito el pagerank del conjunto anterior para derivar los últimos datos de conjuntos)?

¿Tiene sentido? Si es así, ¿es posible?

Answer 1

Necesita calcular el vector eigen principal de una matriz de 100 mil millones por 100 mil millones. A menos que sea extremadamente escaso, no puede caber eso dentro de su máquina. Por lo tanto, necesita una forma de calcular el autovector principal de una matriz cuando solo puede observar una pequeña parte de su matriz a la vez.

Los métodos iterativos para calcular autovectores solo requieren almacenar algunos vectores en cada iteración (cada uno de ellos tendrá 100 mil millones de elementos). Esos pueden caber en su máquina (con flotadores de 4 bytes necesitará alrededor de 375 GB por vector). Una vez que tenga un vector candidato de clasificaciones, puede (muy lentamente) aplicar su matriz gigante leyendo la matriz en fragmentos (ya que puede ver 32 mil millones de filas a la vez, necesitará poco más de 3 trozos). Repita este proceso y tendrá los conceptos básicos del método de potencia, que es lo que se usa en el pagerank. cf http://www.ams.org/samplings/feature-column/fcarc-pagerank y http://en.wikipedia.org/wiki/Power_iteration

Por supuesto, el factor limitante aquí es cuántas veces necesita examinar la matriz. Resulta que almacenando más de un vector candidato y usando algunos algoritmos aleatorizados puede obtener una buena precisión con menos lecturas de sus datos. Este es un tema de investigación actual en el mundo de las matemáticas aplicadas. Puede encontrar más información aquí http://arxiv.org/abs/0909.4061, aquí http://arxiv.org/abs/0909.4061, y aquí http://arxiv.org/abs/0809.2274. Hay un código disponible aquí: http://code.google.com/p/redsvd/ pero no puedes usarlo para los tamaños de datos de los que estás hablando.

Otra forma de hacerlo es buscar en "svd incremental" que puede adaptarse mejor a su problema pero es un poco más complicado. Considere esta nota: http://www.cs.usask.ca/~spiteri/CSDA-06T0909e.pdf y por este Foro: https://mathoverflow.net/questions/32158/distributed-incremental-svd