Матрица Google - Google matrix

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

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

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

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

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

Матричный элемент ${displaystyle A_ {i, j}}$ заполняется 1, если узел ${displaystyle j}$ есть ссылка на узел ${displaystyle i}$ , и 0 в противном случае; это матрица смежности ссылок.
Связанная матрица S соответствующие переходам в Цепь Маркова данной сети построена из А разделив элементы столбца "j" на количество ${displaystyle k_ {j} = Sigma _ {i = 1} ^ {N} A_ {i, j}}$ куда ${displaystyle k_ {j}}$ это общее количество исходящих ссылок с узлаj ко всем остальным узлам. Столбцы с нулевыми матричными элементами, соответствующие висячим узлам, заменяются постоянным значением 1 / N. Такая процедура добавляет ссылку из каждого приемника, висящего состояния ${displaystyle a}$ ко всем остальным узлам.
Теперь по построению сумма всех элементов в любом столбце матрицы S равно единице. Таким образом, матрица S математически корректно определено и принадлежит классу цепей Маркова и классу операторов Перрона-Фробениуса. Что делает S подходит для PageRank алгоритм.

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

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

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

{displaystyle G_ {ij} = альфа S_ {ij} + (1-альфа) {гидроразрыв {1} {N}} ;;;;;;;;;;; (1)}

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

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

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

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

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

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

Рис 3. Спектр собственных значений матрицы Google Кембриджского университета из рис.

{displaystyle alpha = 1}

, синие точки - собственные значения изолированных подпространств, красные точки - собственные значения ядерной компоненты (из ^[5])

За ${displaystyle 0 <альфа <1}$ есть только одно максимальное собственное значение ${displaystyle lambda = 1}$ с соответствующим правым собственным вектором, который имеет неотрицательные элементы ${displaystyle P_ {i}}$ которое можно рассматривать как стационарное распределение вероятностей.^[2] Эти вероятности, упорядоченные по их уменьшающимся значениям, дают вектор PageRank ${displaystyle P_ {i}}$ с PageRank ${displaystyle K_ {i}}$ используется поиском Google для ранжирования веб-страниц. Обычно во всемирной паутине ${displaystyle Ppropto 1 / K ^ {eta}}$ с ${displaystyle eta приблизительно 0,9}$ . Количество узлов с заданным значением PageRank масштабируется как ${displaystyle N_ {P} propto 1 / P ^ {u}}$ с показателем ${displaystyle u = 1 + 1 / eta приблизительно 2,1}$ .^[6]^[7] Левый собственный вектор при ${displaystyle lambda = 1}$ имеет постоянные матричные элементы. С ${displaystyle 0$ все собственные значения движутся как ${displaystyle lambda _ {i} ightarrow alpha lambda _ {i}}$ кроме максимального собственного значения ${displaystyle lambda = 1}$ , который остается без изменений.^[2] Вектор PageRank зависит от ${displaystyle alpha}$ но другие собственные векторы с ${displaystyle lambda _ {i} <1}$ остаются неизменными из-за их ортогональности постоянному левому вектору при ${displaystyle lambda = 1}$ . Разрыв между ${displaystyle lambda = 1}$ и другое собственное значение ${displaystyle 1-alpha приблизительно 0,15}$ дает быструю сходимость случайного начального вектора к PageRank примерно после 50 умножений на ${displaystyle G}$ матрица.

Рис 4. Распределение собственных значений

{displaystyle lambda _ {i}}

матриц Google в комплексной плоскости на

{displaystyle alpha = 1}

для словарных сетей: 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])

В ${displaystyle alpha = 1}$ матрица ${displaystyle G}$ обычно имеет много вырожденных собственных значений ${displaystyle lambda = 1}$ (см., например, [6]^[8]). Примеры спектра собственных значений матрицы Google различных направленных сетей показаны на рис. ^[5] и фиг.4 с.^[8]

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

Рис 5. Распределение собственных значений

{displaystyle lambda}

в комплексной плоскости для матрицы Google

{displaystyle G}

ядра Linux версии 2.6.32 с размером матрицы

{displaystyle N = 285509}

в

{displaystyle alpha = 0,85}

, единичный круг показан сплошной кривой (от ^[9])

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

{displaystyle | lambda _ {i} |}

(из ^[9])

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

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

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

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

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

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

[Ermann2011-1] а ^б ^c Ermann, L .; Чепелянский, А.Д .; Шепелянский, Д. Л. (2011). «К двумерным поисковым системам». Журнал физики А. 45 (27): 275101. arXiv:1106.6215. Bibcode:2012JPhA ... 45A5101E. Дои:10.1088/1751-8113/45/27/275101.

[Langville2006-2] а ^б ^c ^d ^е Лэнгвилл, Эми Н.; Мейер, Карл (2006). PageRank Google и не только. Princeton University Press. ISBN 978-0-691-12202-1.

[Austin2008-3] а ^б Остин, Дэвид (2008). "Как Google находит вашу иглу в стоге сена Интернета". Столбцы характеристик AMS.

[4] Закон, Эдит (2008-10-09). "PageRank Лекция 12" (PDF).

[Frahm2011-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.

[Georgeot2010-8] а ^б ^c Жоржо, Бертран; Жиро, Оливье; Шепелянский, Дима Л. (25.05.2010). «Спектральные свойства матрицы Google всемирной паутины и других направленных сетей». Физический обзор E. 81 (5): 056109. arXiv:1002.3342. Bibcode:2010PhRvE..81e6109G. Дои:10.1103 / PhysRevE.81.056109. PMID 20866299.

[Ermann2011-2-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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]