WikiDer > Матрица Google

Google matrix
Рисунок 1. Матрица Google сети статей Википедии, написанная на основе индекса PageRank; показан фрагмент верхних элементов матрицы 200 X 200, общий размер N = 3282257 (от [1])

А Матрица Google особый стохастическая матрица что используется Googleс PageRank алгоритм. Матрица представляет собой граф с ребрами, представляющими ссылки между страницами. PageRank каждой страницы затем может быть итеративно сгенерирован из матрицы Google с использованием силовой метод. Однако для сходимости степенного метода матрица должна быть стохастической, несводимый и апериодический.

Матрица смежности А и матрица Маркова S

Чтобы создать матрицу Google грамм, мы должны сначала сгенерировать матрицу смежности А который представляет отношения между страницами или узлами.

Предполагая, что есть N страниц, мы можем заполнить А сделав следующее:

  1. Матричный элемент заполняется 1, если узел есть ссылка на узел , и 0 в противном случае; это матрица смежности ссылок.
  2. Связанная матрица S соответствующие переходам в Цепь Маркова данной сети построена из А разделив элементы столбца "j" на количество куда это общее количество исходящих ссылок с узлаj ко всем остальным узлам. Столбцы с нулевыми матричными элементами, соответствующие висячим узлам, заменяются постоянным значением 1 / N. Такая процедура добавляет ссылку из каждого приемника, висящего состояния ко всем остальным узлам.
  3. Теперь по построению сумма всех элементов в любом столбце матрицы S равно единице. Таким образом, матрица S математически корректно определено и принадлежит классу цепей Маркова и классу операторов Перрона-Фробениуса. Что делает S подходит для PageRank алгоритм.

Построение матрицы Google грамм

Рис 2. Матрица Google сети Кембриджского университета (2006 г.), элементы крупнозернистой матрицы записаны в базах индекса PageRank, показан общий размер N = 212710 (из [1])

Тогда окончательная матрица Google G может быть выражена через S в качестве:

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

Обычно S является разреженной матрицей, и для современных направленных сетей она имеет только около десяти ненулевых элементов в строке или столбце, то есть только около 10N умножения необходимы для умножения вектора на матрицуграмм.[2][3]

Примеры матрицы Google

Пример матрицы построение по уравнению (1) в простой сети приведено в статье CheiRank.

Для реальной матрицы Google использует коэффициент демпфирования около 0,85.[2][3][4] Период, термин дает пользователю вероятность случайного перехода на любую страницу. Матрица принадлежит к классу Операторы Перрона-Фробениуса из Цепи Маркова.[2] Примеры структуры матрицы Google показаны на рис. 1 для сети гиперссылок статей Википедии в 2009 г. в мелком масштабе и на рис. 2 для сети Кембриджского университета в 2006 г. в крупном масштабе.

Спектр и собственные состояния грамм матрица

Рис 3. Спектр собственных значений матрицы Google Кембриджского университета из рис. , синие точки - собственные значения изолированных подпространств, красные точки - собственные значения ядерной компоненты (из [5])

За есть только одно максимальное собственное значение с соответствующим правым собственным вектором, который имеет неотрицательные элементы которое можно рассматривать как стационарное распределение вероятностей.[2] Эти вероятности, упорядоченные по их уменьшающимся значениям, дают вектор PageRank с PageRank используется поиском Google для ранжирования веб-страниц. Обычно во всемирной паутине с . Количество узлов с заданным значением PageRank масштабируется как с показателем .[6][7] Левый собственный вектор при имеет постоянные матричные элементы. С все собственные значения движутся как кроме максимального собственного значения , который остается без изменений.[2] Вектор PageRank зависит от но другие собственные векторы с остаются неизменными из-за их ортогональности постоянному левому вектору при . Разрыв между и другое собственное значение дает быструю сходимость случайного начального вектора к PageRank примерно после 50 умножений на матрица.

Рис 4. Распределение собственных значений матриц Google в комплексной плоскости на для словарных сетей: Roget (A, N = 1022), ODLIS (B, N = 2909) и FOLDOC (C, N = 13356); WWW сети университетов Великобритании: Университет Уэльса (Кардифф) (D, N = 2778), Университет Бирмингема (E, N = 10631), Университет Кил (Стаффордшир) (F, N = 11437), Университет Ноттингем-Трент (G, N = 12660), Ливерпульский университет Джона Мура (H, N = 13578) (данные по университетам за 2002 г.) (из [8])

В матрица обычно имеет много вырожденных собственных значений (см., например, [6][8]). Примеры спектра собственных значений матрицы Google различных направленных сетей показаны на рис. [5] и фиг.4 с.[8]

Матрица Google может быть также построена для сетей Улама, генерируемых методом Улама [8] для динамических карт. Спектральные свойства таких матриц обсуждаются в [9,10,11,12,13,15].[5][9] В ряде случаев спектр описывается фрактальным законом Вейля [10,12].

Рис 5. Распределение собственных значений в комплексной плоскости для матрицы Google ядра Linux версии 2.6.32 с размером матрицы в , единичный круг показан сплошной кривой (от [9])
Рис.6. Крупнозернистое распределение вероятностей для собственных состояний матрицы Google для ядра Linux версии 2.6.32. Горизонтальные линии показывают первые 64 собственных вектора, упорядоченных по вертикали следующим образом: (из [9])

Матрица Google может быть построена также для других направленных сетей, например для сети вызова процедур программного обеспечения ядра Linux, представленного в [15]. В этом случае спектр описывается фрактальным законом Вейля с фрактальной размерностью (см. рис. 5 из [9]). Численный анализ показывает, что собственные состояния матрицы локализованы (см. рис. 6 из [9]). Итерация Арнольди Метод позволяет вычислять множество собственных значений и собственных векторов для матриц достаточно большого размера [13].[5][9]

Другие примеры Матрица включает матрицу мозга Google [17] и управление бизнес-процессами [18], см. также.[1] Применение матричного анализа Google к последовательностям ДНК описано в [20]. Такой матричный подход Google позволяет также анализировать взаимосвязь культур посредством ранжирования многоязычных статей Википедии о людях [21]

Исторические заметки

Матрица Google с коэффициентом затухания описывалась следующим образом: Сергей Брин и Ларри Пейдж в 1998 г. [22], см. также статьи по истории PageRank [23], [24].

Смотрите также

Рекомендации

  1. ^ а б c Ermann, L .; Чепелянский, А.Д .; Шепелянский, Д. Л. (2011). «К двумерным поисковым системам». Журнал физики А. 45 (27): 275101. arXiv:1106.6215. Bibcode:2012JPhA ... 45A5101E. Дои:10.1088/1751-8113/45/27/275101.
  2. ^ а б c d е Лэнгвилл, Эми Н.; Мейер, Карл (2006). PageRank Google и не только. Princeton University Press. ISBN 978-0-691-12202-1.
  3. ^ а б Остин, Дэвид (2008). "Как Google находит вашу иглу в стоге сена Интернета". Столбцы характеристик AMS.
  4. ^ Закон, Эдит (2008-10-09). "PageRank Лекция 12" (PDF).
  5. ^ а б c d Frahm, K. M .; Georgeot, B .; Шепелянский, Д. Л. (01.11.2011). «Повсеместное появление PageRank». Журнал физики А. 44 (46): 465101. arXiv:1105.1062. Bibcode:2011JPhA ... 44T5101F. Дои:10.1088/1751-8113/44/46/465101.
  6. ^ Донато, Дебора; Лаура, Луиджи; Леонарди, Стефано; Миллоцци, Стефано (30 марта 2004). «Крупномасштабные свойства веб-графа» (PDF). Европейский физический журнал B. 38 (2): 239–243. Bibcode:2004EPJB ... 38..239D. CiteSeerX 10.1.1.104.2136. Дои:10.1140 / epjb / e2004-00056-6.
  7. ^ Пандуранган, Гопал; Рангхаван, Прабхакар; Упфал, Эли (2005). «Использование PageRank для характеристики веб-структуры» (PDF). Интернет-математика. 3 (1): 1–20. Дои:10.1080/15427951.2006.10129114.
  8. ^ а б c Жоржо, Бертран; Жиро, Оливье; Шепелянский, Дима Л. (25.05.2010). «Спектральные свойства матрицы Google всемирной паутины и других направленных сетей». Физический обзор E. 81 (5): 056109. arXiv:1002.3342. Bibcode:2010PhRvE..81e6109G. Дои:10.1103 / PhysRevE.81.056109. PMID 20866299.
  9. ^ а б c d е ж Ermann, L .; Чепелянский, А.Д .; Шепелянский, Д. Л. (2011). «Фрактальный закон Вейля для архитектуры ядра Linux». Европейский физический журнал B. 79 (1): 115–120. arXiv:1005.1395. Bibcode:2011EPJB ... 79..115E. Дои:10.1140 / epjb / e2010-10774-7.

внешняя ссылка