Pagerank vs SVD

Question

Pagerank работает над нодеграфом серии страниц и направленными краями, образованными их соответствующими внутренними и внешними звеньями. Таким образом, ранг конкретной страницы является широко локально индуцированным эффектом в нодеграфе.

SVD, с другой стороны, работает над целой матрицей значений и не имеет направленности - связь между сайтом A и сайтом B будет регистрироваться только как 1 на правильном матричном элементе. Это глобальная система, поэтому ранжирование является глобальным эффектом.

Учитывая чрезвычайную разреженность матриц, полученных из Интернета, я ожидал бы, что SVD будет плохим исполнителем здесь, поскольку он требует полного набора данных и имеет значительные требования к памяти.

Это правда? Pagerank превзошел SVD в значительной степени потому, что это алгоритм на основе голографии? Как Pagerank может вывести семантическую значимость со страницы за пределы того количества слов, о котором говорится? Или это будет второй шаг, который будет выполнен после того, как Pagerank разместит страницы?

Answer 1

Здесь есть две проблемы: какую меру легко вычислить и которая дает информацию, которую мы ищем? Я не знаю ответа на любой вопрос, но я могу дать частичный ответ.

Во-первых, актуальность. Обе величины составляют centrality мер, чтобы использовать термин из теории сети. PageRank вычисляет (вариант) собственную независимость вектора, а SVD, по-видимому, приводит к алгоритму поиска по гиперссылкам (HITS). Я получил это от this handout от Peter Dodds (Университет Вермонта). Они измеряют разные вещи, но мне непонятно, какая из них наиболее важна для измерения важности веб-страницы.

Во-вторых, вычислительная стоимость. Математически говоря, PageRank является доминирующим собственным вектором (модифицированной) матрицы смежности - как объяснено на странице Википедии - в то время как HITS дает доминирующий особый вектор матрицы смежности. Оба они определяются глобальной сетью веб-страниц и связей между ними, и оба могут быть вычислены только с учетом локального графа узлов. На первый взгляд, я думаю, что вычислительная стоимость примерно равна.

В заключение я не знаю, почему PageRank лучше SVD; мне даже не ясно, что это лучше, чем SVD.

Answer 2

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