Заметки разработчика поисковых сервисов ([info]itman) wrote in [info]ru_ir,
@ 2008-03-12 10:29:00
Previous Entry  Add to memories!  Tell a Friend!  Next Entry
Entry tags:pagerank

Пейджранк на ненаправленном графе
А у меня вот какой любопытный вопрос: никто никогда не задумывался (или, может быть, читал статьи), что означает PageRank для графа, у которого связь между узлами симметричная, то есть, если есть ребро, ведущее из A в B, то также есть и ребро из B в A?
UPDATE: лучше, наверное, назвать этот граф ненаправленным.


(Post a new comment)

Эу...
[info]jescid
2008-03-12 04:18 pm UTC (link)
Если стр. А ссылается на стр. В1...Bn и на каждой есть обратная на А — то это тоже такой граф. Или имеется ввиду (сильно) связный граф? (каждая Bi ссылается на Bj (i,j) = 1...n)

Потому что в первом случае формула Google PR вполне работает, т.к. она учитывает кол-во исх. ссылок для расчёта PR данной стр. Во втором случае по-момеу тоже всё ок, если брать dumping factor =1 (равновероятная кликабельность для виртуального случайного сёрфера). Нет?

(Reply to this)(Thread)
Re: Эу...
[info]itman
2008-03-12 04:31 pm UTC (link)
Имеется в виду обычный граф, у которого любая "связь" взаимная, то есть, есть ссылки в обоих направлениях. Формула PR, несомненно, работает, но что же она в данном случае считает?

(Reply to this)(Parent)(Thread)
Так разные вещи считает.
[info]jescid
2008-03-12 05:10 pm UTC (link)
В случае, когда ссылка взаимная, но каждый узел НЕ связан с каждым, PR будет разный в зависимости от числа ссылок со стр..
Во втором случае (для каждого d=1/N, N=число узлов, а не 1 — то у меня ошибка) у всех узлов будет одинаковый PR, само понятие PR тогда бессмысленно, конечно.
Но такой сетки не существует (в интернете) — это уже не scale-free сеть, конечно. А просто масштабируемая сетка, у которой не м.б. PR по определению.
В первом случае в приниципе это м.б. scale-free, PR (понимаемый как вес узла) будет расти там, где сходится много рёбер. Т.е., это вполне такой нормальный PR — ближайший пример этого вашего графа: сеть дорог (на Земном шаре вообще).

Edited at 2008-03-12 05:11 pm UTC

(Reply to this)(Parent)(Thread)
Re: Так разные вещи считает.
[info]itman
2008-03-12 05:18 pm UTC (link)
Понятно, что разный, но вот насколько он непропорационален числу ссылок...

(Reply to this)(Parent)(Thread)
ПМСМ от того же dumping factor надо исходить...
[info]jescid
2008-03-12 05:36 pm UTC (link)
Или, иначе, надо брать вероятность встретить не менее заданного числа ссылок N в данном узле. Если P падает по экпоненте с ростом N — то всё пучком и PR по ф-ле Пейджа считает то, что надо. А если как-то иначе, по другому закону, то и формулу для PR надо выводить другую — поскольку PR может ещё иметь смысл.
А чем более сетка становится однородной (вплоть до типа картографич. разметки широт и долгот), то тем скорее PR теряет смысл.

(Reply to this)(Parent)

[info]sply
2008-03-12 04:30 pm UTC (link)
Это электрическая цепь, которая по закноам Кирхгофа решается за линейное время.

(Reply to this)(Thread)

[info]sply
2008-03-12 04:51 pm UTC (link)
что-то я туплю, вопрос другой был.

но ведь для такой схемы pr у всех элементов будет одинаков.

(Reply to this)(Parent)(Thread)

[info]itman
2008-03-12 05:04 pm UTC (link)
Если у PR коэффициент затухания не равен нулю или единицы, то нет.

(Reply to this)(Parent)
Только если все узлы связаны со всеми
[info]jescid
2008-03-12 05:14 pm UTC (link)
(сильно связный граф)
А если не все — то разный.

Edited at 2008-03-12 05:14 pm UTC

(Reply to this)(Parent)(Thread)
Re: Только если все узлы связаны со всеми
[info]itman
2008-03-12 05:34 pm UTC (link)
Любопытно, что если взять нулевой коэффициент затухания (вероятность остаться на месте ноль) и рассмотреть простенькую схему "звезда", то PR получается
1/2, 1/2N, ... , 1/2N. Количество ссылок в чистом виде. Вопрос, что будет в более сложном случае?

(Reply to this)(Parent)

[info]itman
2008-03-12 05:14 pm UTC (link)
Хотя, похоже, что некие аналогии между random walks и цепями существуют, но я их пока не очень смыслил. надо еще подумать.

(Reply to this)(Parent)

[info]itman
2008-03-12 04:57 pm UTC (link)
А разве в электрической цепи не однонаправленные "ребра"?

(Reply to this)(Parent)(Thread)

[info]sply
2008-03-12 05:15 pm UTC (link)
Нет, ток может течь в обоих направлениях. Но смысла в этой аналогии все-равно нет.

(Reply to this)(Parent)

[info]cgvictor
2008-03-12 06:08 pm UTC (link)
Если есть затухание и связность неполная, то это значение покажет "вес" точки пропорционально количеству связей ее и ее соседей. Чем показатель больше, тем с большим количеством узлов связан узел через наименьшее количество соседей. Относительно. Как-то так.

(Reply to this)(Thread)

[info]itman
2008-03-12 06:16 pm UTC (link)
У меня было подозрение, что ранг в таком случае зависит только от количества соседей. Вот насколько это верно, я пока не проверил.

(Reply to this)(Parent)(Thread)

[info]cgvictor
2008-03-12 07:38 pm UTC (link)
От количества ссылок на соседей, обратно пропорционально удаленности ссылки от узла. Да, вроде так и есть.

(Reply to this)(Parent)(Thread)

[info]itman
2008-03-12 07:42 pm UTC (link)
Что значит, обратно пропорационально удаленности? И какие соседи имеются в виду: все достижимые узлы?

(Reply to this)(Parent)(Thread)

[info]cgvictor
2008-03-12 08:12 pm UTC (link)
>>Что значит, обратно пропорационально
Фигура речи.
Учитываются же ссылки не только от заданного узла к соседям, а от соседей до "соседей второго уровня" & so on.

>>все достижимые узлы?
Ну вроде - да, пока в задаче не сказано иное.

(Reply to this)(Parent)(Thread)

[info]itman
2008-03-12 08:15 pm UTC (link)
Нашелся пример, когда это неправда :-)
У центрального узла самое большое число непосредственных соседей и самое короткое расстояние (два ребра максимум) до любого другого узла. тем не менее он не самый "жирный":
http://itman.livejournal.com/200665.html?thread=1808857#t1808857

(Reply to this)(Parent)

(Anonymous)
2008-03-12 06:15 pm UTC (link)
Разумеется, во всем виноват itman:) В частности, с никуда не ведущей “локальной симметрией” - pr гарантированно одинаков, если вершины одинаково расположены вовсе не относительно друг друга, а относительно всего графа.
пенсионерка Кириешко
Ps.а про виноват - почти-не-шутка - не то что задача не сформулирована, пока не ясно и “что же я хочу” (что,конечно,нормально; мой папаша регулярно пребывает в последнем состоянии неделями;)

(Reply to this)(Thread)

[info]itman
2008-03-12 06:18 pm UTC (link)
Да-да, граф не симметричен! Я написал неправильно. Граф не направлен.
По поводу хочу-ли-я-могу-ли-маголи-я: хотелось бы проверить вот эту гипотезу.

Edited at 2008-03-12 06:19 pm UTC

(Reply to this)(Parent)(Thread)

(Anonymous)
2008-03-12 06:26 pm UTC (link)
Может, я не про то, но
вот есть цепочка 1=2=3=4=5 (= про связи в обе стороны). У симметричных(относительно ГРАФА)pr равен, у несимметричных - нет.
Да?

(Reply to this)(Parent)(Thread)

(Anonymous)
2008-03-12 06:30 pm UTC (link)
забыл подписаться(хотя блог не Корпоративный)- пенс.Кириешко

(Reply to this)(Parent)

[info]itman
2008-03-12 07:37 pm UTC (link)
А разве 1=2=3=4=5 симметричный?
Мне казалось, что симметричный - это 1=2=3=4=5=1
PS: да у несимметричных бывает всяко разно.

(Reply to this)(Parent)(Thread)

(Anonymous)
2008-03-12 07:50 pm UTC (link)
я про
1) то, что 1 "симметрична"5, 2"симметрична" 4. И про ранги(3 самая пейджранкистая, 2и4 -след. и 1и5-самые ходосочные).
2)пост,на который вы сослались (у (2,4) и 3 - разные ранги,но одно и то же число входов/выходов).
НБ (п.Кир.)

(Reply to this)(Parent)(Thread)

(Anonymous)
2008-03-13 08:28 am UTC (link)
так контрпример 1=2=3=4=5 про гипотезу в Вашей ссылке (On an undirected graph, sorting nodes by their PageRank produces the same ordering as sorting nodes by their number of links.) Вас не удовлетворил?
НБ

(Reply to this)(Parent)(Thread)

[info]itman
2008-03-13 08:42 am UTC (link)
В каком-то смысле удовлетворил, потому что для малых значений d там получается большая разница, а вот для любимого гугловского значения 0.85 получается уже:
0.13453 0.24595 0.23905 0.24595 0.13453
Ну, почти, гипотеза.
PS: и программку, конечно, надо бы проверить еще :-)

Edited at 2008-03-13 08:43 am UTC

(Reply to this)(Parent)(Thread)

(Anonymous)
2008-03-13 09:15 am UTC (link)
Вы что, их (pr'ов)не поленились посчитать?! весь контрпример был (а)про гипотезу,(б)ровно как оче(=глазьями)видный
п.Кир.
PS А флэшмоб удался :)

(Reply to this)(Parent)(Thread)

[info]itman
2008-03-13 09:26 am UTC (link)
Я сделал проще: написал программку, но не для конкретно этого примера, а для более общего случая и посмотрел, что получится...
PS: это не флешмоб, я пытаюсь понять, какое свойство графа будет описывать подобный PR. В случае сильно несимметричных графов все очевидно: есть лидер, его все линкуют. А тут всегда есть обратная связь.

(Reply to this)(Parent)

(Anonymous)
2008-03-13 12:37 am UTC (link)
http://en.wikipedia.org/wiki/PageRank

(Reply to this)(Thread)

[info]itman
2008-03-13 12:47 am UTC (link)
Оч смешная шутка, но абсолютно "мимо кассы"

(Reply to this)(Parent)(Thread)

[info]alexf
2008-03-13 07:21 pm UTC (link)
Вообще то вопрос как то загадочно сформулирован - что означает ПэйджРанк. :) Он означает то, что должен означать по определению, а именно ранг имени тов. Ларри Пэйджа, независимо от связей в графе.
Насчёт корреляции между ПР и числом ссылок, понятно что она будет, и чем меньше аномально жирных страниц линкуется на обычные страницы, тем корреляция будет лучше.

(Reply to this)(Parent)(Thread)

[info]itman
2008-03-13 07:55 pm UTC (link)
Он только на первый взгля загадочный. На самом деле, когда ссылки расставляются ассиметрично и есть ярко выраженные лидеры, Пейджранк - это просто ссылочное цитирование, подкорректированное с учетом тезиса "жирные страницы дают более жирные ссылки". В случае абсолютного взамного цитирования, это не так, очевидно, корреляция с числом ссылок еще больше. Возникает разумный вопрос, а имеет ли пейджранк на таких графах какой-либо смысл, улучшает ли он или ухудшает ранжирование.

(Reply to this)(Parent)

(Anonymous)
2008-03-15 11:44 am UTC (link)
Извините, про слона забыл,а потом возможности написать не было.
По ходу педжранк-флэшмоба ;) выяснилось, 1) что истинный вопрос — “где посмотреть инструменты/результаты, переносимые на зависимости на соцсетях?”, 2) вопрос действительно Вас занимает.
Поэтому [историко-методологический ;)))] ответ /который наверняка не понравится ;) — ведь никаких ссылок ни на какие ссайты не предлагаю/:

— в работах по математической социологии (той,где графы),социо-,науко- и библиометрии.

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

(Reply to this)(Thread)

[info]itman
2008-03-15 07:12 pm UTC (link)
Это не социальные сети. Тут, просто прозвучала довольно безумная идея посчитать ссылочную популярность на основе похожести документов. Наверное, это не вполне бессмысленная затея, но вот что получится в итоге?
Есть большое подозрение, что тут начнет играть кластеризация. Центры кластеров похожих документов получат большие веса. Далее, если кластеры как-то группируются в супер-кластеры, то кластеры, контактирующие с большим числом, кластеров тоже оказываются в выигрыше, итд... Возможно, что в результате, наиболее "интердисциплинарные" документы получат самые большие веса. Но это так догадка. Второй вопрос - чисто поведенческий. А нужные ли такие документы пользователю, предпочтет ли он их документах "узкоспециализированным", которые стоят "в сторонке"?

(Reply to this)(Parent)

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