Расчет постраничных рангов для разреженного ориентированного графа с высоким процентом мертвых ссылок - PullRequest
Новая
       15

Расчет постраничных рангов для разреженного ориентированного графа с высоким процентом мертвых ссылок

1 голос
/ 08 сентября 2010

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

Под мертвыми ссылками я подразумеваю узлы с нулевым перевесом.Иногда на графике с множеством мертвых ссылок могут появляться ловушки для пауков.В любом случае, проблема, которая меня интересует, заключается в поиске постранков в этом сценарии.

И я использую JUNG (Java Universal Graph Network) для вычисления рангов страниц.

Когда я использую обычную процедуру, 

Graph<String, String> jungGraph = new DirectedSparseGraph<String, String>();
PageRank<String, String> pagerank = new PageRank<String,String>(jungGraph, 0.2);
pagerank.setMaxIterations(20);
pagerank.setTolerance(0.000001);
pagerank.evaluate();

я получаю более или менееодни и те же значения PageRank для всех узлов, когда я четко знаю, что это не должно быть так.Поскольку некоторые узлы в графе имеют большое количество исходящих узлов и сильно взаимосвязаны.

Что такое предлагаемый подход в этом случае.Я знаю, что есть этот класс PageRankWithPriors.Должен ли я сначала извлечь сеть без мертвых ссылок, рассчитать для них постранные ранги, а затем распространить их рейтинг до мертвых ссылок, пока они не сойдутся?В последнем случае все узлы в сокращенной сети (outdegree! = 0) будут иметь свои установленные приоритеты, тогда как мертвые ссылки не будут.

Я что-то здесь упускаю?

1 Ответ

1 голос
/ 08 сентября 2010

Я не думаю, что PageRankWithPriors - это то, что вы хотите.

Какую версию PageRank вы используете?Класс edu.uci.ics.jung.algorithms.importance.PageRank или edu.uci.ics.jung.algorithms.scoring.PageRank?Первый был объявлен устаревшим в пользу последнего в бета-версии Jung 2.0.

Похоже, что они по-разному обрабатывают узлы со степенью 0, что может быть вашей проблемой.Первая спецификация гласит:

вероятность перехода от узла u к узлу v равна (1-альфа) * ​​1012 * [1 / outdegree (u)] + альфа (1 /| V |)

Если у u нет исходных ребер в исходном графе, то вместо 1 / outdegree (v) используется 0.

Это кажется неправильным, так как ведетк потере вероятности (общая вероятность ухода u каким-либо способом должна равняться 1, а это не так).Последний делает это по-другому:

Если у вершины нет исходящих ребер, тогда вероятность случайного прыжка из этой вершины (по умолчанию) составляет 1

Это должно сохранить вероятность того, что вы хотите.

...