Мне интересно, является ли относительно низкая производительность, которую я испытываю с JUNG2 и PageRank, разумной, учитывая данные, которые я использую.
Учитывая граф с ~200 вершинами и ~40000 ребер, вычисление PageRank графа занимает около 15 секунд. Учитывая граф с ~900 вершинами и ~800000 ребер, вычисление PageRank графа занимает почти 5 минут.
Я понимаю, что эти графики очень плотные, и, возможно, естественно ожидать, что для расчета потребуется некоторое время. Однако эти графы не особенно велики, и с такой скоростью было бы невозможно вычислить что-либо, кроме небольшого подмножества графа за раз. (примерно 8 часов для 10 000 вершин и 100 000 000 ребер).
Я использую DirectedSparseGraph с примитивными целыми числами в качестве вершин и ребер и без весов ребер. Очевидно, что это НЕ разреженные графы, поэтому, возможно, существует более подходящая структура графа, которая будет более оптимальной для плотных графов?
Я запускаю jvm в режиме сервера с кучей пространства в куче и подтверждаю, что весь график помещается в память, и своп не используется.
Результаты ранжирования верны, их сумма равна 1, и они соответствуют тестовым примерам в источнике Юнга и в других местах.
Может быть, для этого есть гораздо более высокопроизводительный подход или библиотека? Но, даже если бы это было в 10 раз быстрее, не означает ли тот факт, что его временная сложность пропорциональна количеству ребер, что я быстро выйду за пределы какого бы то ни было подхода Я использую?
Например, я решил вообще отказаться от графового подхода и использовать матрицу для представления вероятностей перехода, что, вероятно, дало бы значительный прирост. Но - PageRank - не единственный алгоритм, который меня интересует. Если я начну использовать свои собственные подходы, которые решат одну проблему и привнесут несколько других.
Кроме того, у меня медленная коробка, Dual Core 1Ghz, поэтому ваши цифры, вероятно, будут намного лучше (например, 4-5 секунд для моего первого примера), но суть верна. Меня больше всего беспокоит, ожидается ли, что код будет работать на порядок быстрее или будет масштабироваться логарифмически.
В любом случае, спасибо за ваши идеи.
