Специальность “прикладная математика” Методы ссылочного ранжирования в информационно-поисковых системах. Диплом
Скачать 300.82 Kb.
|
1 2
| Глава 3. Увеличение сходимости на основе метода релаксации Рассмотрим одну из вершин графа. Пусть  - ранг в вершине  на  -той итерации. Web-граф содержит большое число контуров, в результате чего ранг вершины на -той итерации отчасти определяется рангом этой же вершины на предыдущей итерации.Значение, принимаемое , можно представить в виде: (3.1)где  - ранг вершины на предыдущей итерации,  - коэффициент влияния и  - доля ранга, получаемая из других вершин, в том случае, если бы из web-графа были удалены все содержащие вершину контуры. Ранг вершины, не содержащейся ни в одном из контуров графа, полностью определяется рангами других вершин графа. Если бы web-граф не содержал контуров, его вершины можно было бы подвергнуть топологической сортировке и рассчитать их ранги за один проход.Коэффициент влияния  для каждой вершины можно представить в виде суммы коэффициентов влияния всех содержащих эту вершину контуров  . Для всех вершин  , содержащихся в контуре  , определена некоторая модель, согласно которой вычисляется ранг в этой вершине. Для того, чтобы определить коэффициент влияния вершины в данном контуре, необходимо рассмотреть суперпозицию моделей всех содержащихся в нем вершин. Зафиксировав ранги всех вершин, мы получим функцию, зависящую только от ранга рассматриваемой вершины. Коэффициент при аргументе этой функции и будет коэффициентом влияния для данной вершины в этом контуре. Для подграфа из четырех вершин, изображенного на рисунке 5, вычисление коэффициента влияния для первой вершины будет происходить следующем образом:  Рис 5. Вычисление коэффициента влияния в контуре. Последовательность вершин и дуг  образует контур.Пусть ранг каждой вершины вычисляется с помощью модели PageRank, т.е.:  (3.2)В этом случае ранг второй вершины на -той итерации будет содержать часть ранга первой вершины:  . Ранг третьей вершины будет содержать  . Ранг четвертой вершины:  . И, наконец, вернется в первую вершину:  . Таким образом:  .Коэффициент влияния вершины в контуре для модели PageRank может быть найден следующим образом: (3.3) (3.4)Заметим, что не зависит от номера итерации.Т.к. метод сходится, то, начиная с некоторой итерации :  (3.5)С другой стороны  , следовательно, для сходимости необходимо выполнение условия:  или  . Таким образом, зная коэффициент влияния, мы можем на каждой итерации  вычислить  .
Для экспериментальной оценки эффективности вышеизложенного метода, результаты его работы сравнивались с результатами метода Зейделя. Оба метода были реализованы на языке C++. Экспериментальными данными служили графы различной размерности, сгенерированные согласно копирующей модели web-графа [22]. Результаты тестирования приведены в таблице 1. В качестве модели ссылочного ранжирования была использована модель PageRank. Так как коэффициент затухания в модели PageRank строго меньше единицы, то с ростом числа вершин в контуре коэффициент влияния стремительно убывает. Поэтому на практике достаточно ограничится рассмотрением контуров малой длины. Для проведения эксперимента были рассмотрены контуры, содержащие не более пяти вершин. Заметим, что в модели PageRank коэффициент влияния для всех принадлежащих контуру вершин одинаков:  .Для вычисления коэффициента влияния был применен следующий метод: Шаг 1. Все вершины графа помечаются как не просмотренные. Шаг 2. Выбирается еще не просмотренная вершина. Шаг 3. С помощью поиска в глубину ищется содержащий выбранную вершину контур, длиной не превосходящий заданный параметр и не содержащий ни одной уже просмотренной вершины. Как только контур обнаружен, по формуле (3.3) вычисляется коэффициент влияния вершины в контуре. Найденный коэффициент прибавляется к коэффициентам влияния всех содержащихся в контуре вершин. Шаг 3 выполняется до тех пор, пока не обнаружены все отвечающие заданным требованиям контуры. Если ни одного контура не осталось, то выбранная вершина помечается как просмотренная и алгоритм переходит к Шагу 2. Таблица 1. Эффективность метода ранжирования на основе релаксации. Заключение Метод ссылочного ранжирования на основе релаксации действительно показал лучшую сходимость по сравнению с методом Зейделя. Вычисление коэффициентов влияния для всех вершин задача не менее трудоемкая, чем задача ссылочного ранжирования, но при ее решении необходимо учесть следующие особенности:
Значение коэффициента влияния является очень интересным показателем, который можно использовать в моделях ссылочного ранжирования или для обнаружения ссылочного спама. Его вычисление может проводиться параллельно определению компонент сильной связности или тематических групп. Данный метод может быть обобщен для любой линейной модели ссылочного ранжирования. Несмотря на вышеперечисленные особенности, облегчающие этап предобработки, преимущество в сходимости метода на основе релаксации не настолько велико, чтобы рекомендовать его к использованию в задаче ссылочного ранжирования. Библиография
1 Первый каталог – Yahoo возник в апреле 1994 г. 2 Наряду с неявными, различают также явные кибер-сообщества: кольца (webrings), службы новостей и группы, образованные клиентами пиринговых сетей. |
1 2
Похожие:
 | Курсовая работа на тему: «Исследование эффективности поиска в Интернете... Целью данной работы является оценка эффективности поисковых стратегий в информационно-поисковых системах (ипс) | | Реферат по информатике на тему: «Символика русского народного традиционного костюма» Целью данной работы является оценка эффективности поисковых стратегий в информационно-поисковых системах (ипс) |
| Программа дисциплины «История» для направления 231300. 62 и 230700.... Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления подготовки 231300.... | | Курсовая работа по информатике на тему: «Эффективность поиска в Интернете... Целью данной работы является оценка эффективности поисковых стратегий в информационно-поисковых системах (ипс) |
 | Культуры и искусств Целью данной работы является оценка эффективности поисковых стратегий в информационно-поисковых системах (ипс), в качестве исследуемых... | | Программа дисциплины Современные методы принятия решений для направления... Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления подготовки 010400.... |
| Программа дисциплины «Модели корпусной лингвистики» для направления... Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления 010400. 68 "Прикладная... | | Программа «Методы принятия решений». Гу-вшэ, 2010 г. Министерство... Методы принятия решений для направления 010500. 62 "Прикладная математика и информатика" подготовки бакалавра |
| Программа по формированию навыков безопасного поведения на дорогах... Программа предназначена для преподавателей, ведущих данную дисциплину и студентов направлений 233400. 62 «Информационные системы... | | Кибернетический подход к организации управления в корпоративных системах Специальность: 05. 13. 10 – Управление в социальных и экономических системах (экономические науки) |
| Программа дисциплины «Герменевтика» для направления 010400. 68 «Прикладная... Программа предназначена для преподавателей, ведущих данную дисциплину, и студентов направления подготовки 010400. 68 "Прикладная... | | Контрольная работа По информатике Тема: «Информационно поисковые языки» Целью данной работы является исследование эффективности поиска в Интернете сведений на тему «Информационно поисковые языки», в качестве... |
| Методы решения задач с переменной интенсивностью потоков данных на... Специальность 05. 13. 11 Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей | | Программа дисциплины Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направлений 231300. 62 «Прикладная... |
| Программа дисциплины «Методы оптимизации» для направления 010400.... Федеральное государственное автономное образовательное учреждение высшего профессионального образования | | Рабочая программа учебной дисциплины изотопная геохимия специальность:... «Прикладная геохимия, петрология, минералогия» в течение 6 семестра после прохождения курсов «Химия», «Общая геология», «Кристаллохимия»,... |
