Как работает PageRank: реализация на языке R через линейную алгебру и power-метод

[S_A]

Заинтересовали pagerank'ом, благодаря идее диффузии. Надо будет посмотреть на досуге подробнее.

Вообще диффузные процессы хорошо описываются в терминах стохастических дифф. уравнений для непрерывный случаев… Надо будет с этой стороны присмотреться.

[Alexey_mosc]

А вы меня идеей заинтересовали. ) Спасибо.

Есть оценка качества кластеризации Markov Stability of Community Partitioning. В ней буквально запускают частицу в граф путешествовать и записывают вектор переходов, затем можно увидеть, между какими узлами частица провела больше времени, и если эти узлы совпадают с кластерами, то партишнинг был сделан успешно.

[S_A]

Да, непрерывный случай так легко на граф не натянешь. Присмотрелся к СДУ, Фоккера-Планка (здесь страница 108). Если положить нулевой drift (снос) для процесса диффузии, то лучшей оценкой, хотя и с увеличивающейся (пропорционально корню из t) дисперсией, будет начальное состояние.

Чаще всего Random surfer'а найти легче там, где он начал :) На странице Google.

P.S. Первое предложение набрал в этом комменте, случился флэшбэк. Когда-то давно, году так в 2003, я занимался алгебраической теорией узлов и зацеплений (2 курс универа). Помню, пришел к выводу, что-то по типу, что «узел можно развязать, когда после того, как разрубишь его диаграмму, из кусков можно склеить сферу». Что значит «из кусков склеить сферу» я так и не смог ни сам понять, ни другим объяснить, поэтому на следующий год уже занялся СДУ… :)

Вобщем теперь сижу и не думаю что СДУ могут как-то помочь с ранжированием на графах.

[Alexey_mosc]

Я должен почитать теорию. СДУ не решал. По идее, для непрерывного случая можно ввести плотность вероятности перехода, и перейти к условной плотности. Но это чуть больше, чем я знаю.