Поисковик-затейник ([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 or password?
Login w/ OpenID
English • Español • Deutsch • Русский…