Внедрение PageRank для исследований

Это отличная статья, чтобы узнать о PageRank. Я реализовал Perl-версию из него здесь для использования с Textrank. Однако, если вы хотите просто узнать о PageRank и о том, как различные аспекты, обсуждаемые в статье, влияют на результаты (коэффициент демпфирования, прямой или неориентированный граф и т. д.), я бы рекомендовал провести эксперименты в R или Octave. Если вы хотите научиться эффективно его реализовывать, то лучше всего программировать его с нуля, как вы это делаете.

Большинство веб-графиков (или сетей) очень разрежены, что означает, что большинство записей в матричном представлении графика равны нулю. Распространенной структурой данных, используемой для представления разреженной матрицы, является хеш. -map, где нулевые значения не сохраняются. Например, если матрица была

1, 0, 0
0, 0, 2,
0, 3, 0

двухмерная хэш-карта будет хранить только значения для hm(0,0)=1, hm(1,2)=2 и hm(2,1)=3. Таким образом, в матрице размером 1 000 000 на 1 000 000 веб-графика я ожидал бы получить всего несколько миллионов значений быть ненулевым. Если каждая строка содержит в среднем только 5 ненулевых значений, хэш-карта будет использовать около 5*(8+8+8)*10^6 байтов ~ 115 МБ для ее хранения (8 для левого целочисленного индекса, 8 для правого целочисленного индекса). index и 8 для двойного значения). Квадратная матрица будет использовать 8*10^6*10^6 ~ 7 терабайт.

Реализация эффективного умножения разреженной матрицы на вектор в Java нетривиальна, и уже есть некоторые реализован, если вы не хотите уделять время этому аспекту алгоритма. Умножение разреженной матрицы — наиболее сложный для реализации аспект алгоритма ранжирования страниц, поэтому после этого все становится проще (и интереснее).

Модуль Python networkx имеет хорошую реализацию рейтинга страниц. Он использует scipy/numpy для реализации матрицы. Приведенных ниже двух вопросов о stackoverflow должно быть достаточно, чтобы вы начали.

• Как взвешенные ребра влияют на PageRank в networkx?

• Networkx: различия между pagerank, pagerank_numpy и pagerank_scipy?

Несколько предложений:

• Используйте python, а не Java: python — отличный язык прототипирования, в нем доступны разреженные матрицы (в scipy), а также много других полезных функций. Как отмечали другие, он также имеет реализацию рейтинга страниц.

• Храните ваши данные не все в памяти: любой тип легковесной базы данных подойдет, например, sqlite, hibernate,...

• Работайте с плитками данных: если есть большая матрица NxN, разбейте ее на маленькие плитки MxM, где M — часть N, которые помещаются в памяти. В сочетании с разреженными матрицами это позволяет работать с действительно большими N (от сотен миллионов до миллиардов, в зависимости от того, насколько разрежены данные).

Как предложил Dan W, попробуйте увеличить размер кучи. Если вы запускаете приложение Java из командной строки, просто добавьте переключатель -Xmx с нужным размером кучи. Предположим, вы скомпилировали свой код Java в исполняемый файл JAR с именем pagerank.jar и хотите установить размер кучи равным 512 МБ, вы должны ввести следующую команду:

java -jar -Xmx512m pagerank.jar

EDIT: Но это работает, только если у вас не так много "страниц"... Массив 1 миллион x 1 миллион слишком велик, чтобы поместиться в вашу оперативную память (1 триллион раз * 64-битный двойной значение = 7,27595761 терабайт). Вы должны изменить свой алгоритм, чтобы загружать фрагменты данных с диска, манипулировать ими и сохранять их обратно на диск.

Для этой цели вы можете использовать графическую базу данных, такую ​​как Neo4j.

Вам не нужно хранить всю матрицу 1000000x1000000, потому что большинство элементов матрицы будут нулевыми. Вместо этого вы можете (например) сохранить список ненулевых элементов для каждой строки и написать свои матричные функции, чтобы использовать его напрямую, не расширяя его до полной матрицы.

Этот тип сжатого представления называется форматом разреженной матрицы, и большинство библиотек матриц позволяют создавать и работать с разреженными матрицами.

Одним из недостатков разреженных матриц является то, что умножение двух из них приведет к гораздо менее разреженной матрице. Однако алгоритм PageRank устроен так, что вам не нужно этого делать: матрица гиперссылок постоянна, а обновляется только вектор оценок.

PageRank выполняется Google с использованием структуры Pregel BSP (на самом деле просто ключевые слова).

Я вспомнил Apache Giraph (еще один Pregel), который включает в свой тестовый пакет версию PageRank.

Вот видео о Giraph: это введение, и в нем конкретно рассказывается об управлении PageRank.

Если это не работает:

В Java есть реализация Pregel под названием GoldenOrb.

Псевдокод для алгоритма PageRank находится здесь (на другой реализации Pregel).

Вам придется ознакомиться с BSP и PageRank, чтобы справиться с объемом данных, которые у вас есть.

Поскольку матрица разрежена, вы можете реализовать уменьшение размерности, например svd, pca, mds или Lsi, включающее svd. Существует библиотека для реализации такого рода процессов, которая называется Jama. Вы можете найти его здесь