Введення

Відбір та упорядкування результатів по запитам для трьох мільярдів гіпертекстових документів, які складають веб-граф G (V, E), представляється роботою вкрай важкою, разом з тим, дуже важливою. Аналізу ссылочногоранжированияотводится головна роль в статті.
Поступове розростання і динамічна природа веб-графа змушують проводити аналіз посилання ранжирування, грунтуючись на схемах ранжирування, подобнихPageRank. При цьому обов'язково потрібно врахувати "втрачену" інформацію, яка виникає у зв'язку з тим, що деякі гіпертекстові документи не проиндексированыпоисковыми системами.
У зв'язку з цим виникає питання про точність розрахованої величини PageRank: як можна оцінити "втрачену" інформацію та включити її в розрахунок PageRank. Про це буде сказано пізніше.

Ітераційний розрахунок PageRank і недостатні дані

Недолік інформації про посилання зі сторінок, які не були проіндексовані роботами пошукових систем, представляється в ітераціях при розрахунку PR в якості незаповнених рядків матриці переходів, чиє стаціонарний розподіл виражається через вектор PageRank. Підстаціонарним розподіломрозуміється такий розподіл ймовірності, яке не змінюється з плином часу.
Таким чином, необхідно або видалити ті вершини графа, які враховуються при розрахунку, або змінити передбачене розподіл (нормалізований вектор вершин графа). Далі буде показано, як брак інформації може серйозно вплинути на точність розрахунку PageRank.
Але для початку дамо визначення словосполученню "точність PageRank".
Визначення № 1:Дано підмножина Vkвершін графа G (V, E), реальні PR підмножини Vk-це PR, враховані в підграфі G '(Vk, Ek) і змодельовані для вершин Vk, отже, G' має обмеження xy ? E , x, y ? Vk
На будь-якій стадії процесу підрахунку PR все безліч гіпертекстових документів V може бути розділене на підмножину проіндексованих сторінок С і підмножина не проіндексованих сторінок С '. Визначимо безліч З наступним чином F = {p: ? (q ? C) | (q, p) ? E}. Надалі запис q ? p буде використовуватися для позначення записи виду (q, p) ? E. Виділимо також підмножина сторінок, відомих, але не проіндексовані роботами пошукових систем Fc '= {F ? C'}. Посилання з даних сторінок і на ці сторінки не будуть враховуватися при розрахунку PR. Також позначимо множину {C ? Fc '} вже відомим Vkі введемо наступне позначення Nk = | Vk |.
Визначення № 2. "Достовірність":Задамо неповної матриці переходів розмірність N і розподіл p (?), щоб отримати ряди, не відповідні заданим умовам (нормалізований вектор вихідних посилань). Підрахунок PR вважається достовірним в тому випадку, якщо різниця між розрахованим та реальним PR складає O.
Зауваження № 1:Для вихідних посилань, з рівномірним розподілом p (?), розрахунок PR вірний, якщо розмірність підмножини невідомих вершин веб-графа не перевищує O (? Nk).
Припустимо, що розподіл вихідних посилань рівномірне, однак це твердження, не є догмою. Передбачається, що вибірка вихідних посилань більше розріджена, аніж та, яка отримана рівномірної дискретизацією по всій множині N. Більш точне наближення може бути отримано, якщо брати симплекс з меншою розмірністю. Підсимплексомрозуміється геометрична фігура, що представляє собою n-мірне узагальнення трикутника.
Встановимо нашому симплекс розмірність N. Однак, може виявитися так, що різниця результатів, отриманих при рівномірному розподілі і при виборі симплекс меншої розмірності, зросте.
Даний момент необхідно врахувати в якості невідомих змінних матриці переходів. За більш докладним поясненням даного аспекту потрібно звернутися до джерела [2], де описується робота виключно з проіндексованими сторінками.
Стаціонарне розподіл може бути виявлено. Однак, остаточні PR можуть бути підраховані тільки після того, як будуть виконані численні розрахунки.

Також не варто забувати, що тільки певна кількість ітерацій може бути використано для розрахунку PR вершин з підмножини FC '.
Подальший аналіз дозволить нам визначитися з PR для сторінок, які не проіндексовані.

Оцінка кількості "висячих" посилань.

Розглядається той метод, коли будуть заповнюватися невідомі рядка матриці переходів змінними, не пов'язаними з рівномірним розподілом. Можна припустити, що розподіл значень переходів враховує усереднене значення, щоб під впливом досить слабких обмежень перейти до стаціонарного розподілу або до оцінок PR.
Заміна невідомих значень їх очікуваннями є одним з найвідоміших припущень. Найбільш наочним способом представлення веб-графа є графічний. Графік має відіграти вирішальну роль у розумінні основних моментів. Модель, в якій одні вершини зв'язані з іншими вершинами пропорційно їх PR виробляє фундаментальні закони, описані в джерелі [3].
Необхідно проводити ітераційні обчислення багаторазово, де кожен наступний PR буде розраховуватися, заповнюючи при цьому порожні рядки матриці. Таким чином, знайдемо вектор r, при заміні якого як невідомого ряду, ми знову отримаємо наші PR. Величину r можна буде розрахувати аналітичним шляхом, не вдаючись до великої кількості розрахунків на кожній ітерації.
Зауваження № 2:Підрахунок PR сторінок з підмножини С, здійснюваний итерацией за ітерацією, поступово заповнюючи PR матрицю переходів, забезпечує достовірність PR за умови, що вхідні дані в невідомих рядках будуть мати таке ж розподіл як і вектор r.

кластерізовани оцінка.

В даному випадку нашою метою є оцінка невизначених рядів PR-ів матриці T, тобто виявлення умовного розподілу P (y2 | y1) і відповідного стаціонарного розподіл вектора нових PR-ов, вектора r. Для цього вводиться динамічна модель.
Існує ймовірність того, що сторінка, пов'язана зі сторінкою, може бути виражена через безліч змінних Z. Дана модель обчислена в випадкових змінних Z шляхом введення таких обмежень, що кінцеві стовпці і рядки мають однакову розподіл. Дані обмеження мають також велику цінність в тому, що спільний розподіл дискретних випадкових величин, може бути відображено з помощьюцепей Маркова.
Таким чином, з'являється можливість нехай більш грубого підрахунку PR, але з можливістю кінцевої оцінки даного підрахунку. Модель можна представити таким чином:

Безліч Y може бути змодельоване як фіксоване безліч незалежних параметрів, незважаючи на те, чи буде змінюватися безліч Y чи ні. Даний аспект дозволяє використовувати модель в якості динамічної. Однак тут ми сталківаемcя з черговою проблемою: як оцінити P (y2)? Для цього потрібно визначитися з ймовірностями переходів P (y2 | y1), які в свою чергу вимагають знання P (y2).
Введемо наступні позначення:

U [i, j] = P (Z (yi) = i | yi
діагональна матриця R [i, j] = p (yi) = riі r [i] = P (yi)
Використовуючи рівність (1) і властивість стаціонарності отримуємо:

Склавши для матриць A і U лінійне рівняння | Y | = Nk, невідомі можуть бути знайдені численними ітераціями з обраної максимальною ентропією лінійних обмежень.
Відстань L1 між реальними і передбаченими рядками матриці переходів показано на рис. 1 для деякого підмножини веб-графа.Байесовскій подходіспользуется тут для порівняння


Рис.1 Порівняння результатів передбачення ваги вихідних оцінка висять посилань, кластерізовани оцінка, байєсовський підхід, рівномірний розподіл і розподіл , відповідне нульовою гіпотезою.

Більш повну інформацію про розрахунок PR можна отримати з наступних Acharyya, Joydeep Ghosh
Переклад за редакцією Сергія стружковая


Статьяполучена: www.SeoNews.ru

Детальніше »