Заметки разработчика поисковых сервисов ([info]itman) wrote,
@ 2008-05-02 17:07:00
Previous Entry  Add to memories!  Tell a Friend!  Next Entry
Entry tags:google, pagerank, qbic

Пейджранк на ненаправленном графе
Вдогонку недавнему квесту.


(Post a new comment)


[info]marknn
2008-05-02 11:27 pm UTC (link)
Очень странно, pagerank на неориентированном графе дает степень вершины в качестве решения. Странная статья....

(Reply to this)(Thread)

[info]itman
2008-05-03 07:14 pm UTC (link)
Степень вершины - количество соседей?

(Reply to this)(Parent)(Thread)

[info]marknn
2008-05-03 09:46 pm UTC (link)
Ugu. Ili summu vesov vseh reber ishodyashih iz dannoy vershiny.

(Reply to this)(Parent)(Thread)

[info]itman
2008-05-04 04:29 am UTC (link)
А как рассчитываются веса соседних вершин :-)?

(Reply to this)(Parent)(Thread)

[info]marknn
2008-05-04 02:06 pm UTC (link)
В той статье, у каждого ребр есть вес -- некая мера похожести изображений соответствующая вершинам которые оно (ребро) соединяет. Вес данной вершины = общему весу ребер исходящих из двнной вершины.

(Reply to this)(Parent)(Thread)

[info]itman
2008-05-04 02:17 pm UTC (link)
А, ну тогда могу заверить, что PR на ненаправленном графе не рафен степени.

(Reply to this)(Parent)(Thread)

[info]avs313
2008-05-04 05:37 pm UTC (link)
если d=1, то все-таки равен, с точностью до постоянного множителя
потому что если поставить каждой вершине PR=cтепень, то каждая вершина будет сливать каждому соседу по 1, и в итоге получит столько же, сколько отдаст
это естественно если ребра все одинаковы, но если они разные - все так же получается

(Reply to this)(Parent)(Thread)

[info]itman
2008-05-05 03:33 am UTC (link)
Да, я знаю, но речь идет о невырожденном коэффициенте затухания.

(Reply to this)(Parent)

[info]marknn
2008-05-04 09:11 pm UTC (link)
Равен,равен. Спорить будем, иди доказательство предъявить?

Оно простое, главное не забыть нормализовать матрицу смежности по строкам (или столбцам - в зависимости от того с какой стороны собственное значение брать). Что собственно PageRank и делает -- суммарный выход из каждой вершины = 1. А иначе это не pagerank, до и собственное значаение там будет не единица.

В той статье, матрица смежности, кстати, тоже нормализована.


(Reply to this)(Parent)(Thread)

[info]itman
2008-05-05 03:33 am UTC (link)
Это если коэффициент затухания равен нулю, а если не равен, то суммарный выход получается меньше единицы.

(Reply to this)(Parent)(Thread)

[info]marknn
2008-05-06 06:07 pm UTC (link)
Да, согласен, и это убивает симметричность.... Не уверен правда насколько это помогает нетривиальности решения, но может как то и помогаетё

(Reply to this)(Parent)(Thread)

[info]itman
2008-05-06 06:53 pm UTC (link)
Помогает, в предыдущем посте была вычислялка PR для произвольного графа. Я порисовал разные конструкции и очень часто получается, что распределение достаточно нетривиальное.

(Reply to this)(Parent)

Create an Account
Forgot your login?
Login w/ OpenID
English • Español • Deutsch • Русский…