Матрица Google

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

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

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

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

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

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

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

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

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

$G_{ij}=\alpha S_{ij}+(1-\alpha ){\frac {1}{N}}\;\;\;\;\;\;\;\;\;\;\;(1)$

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

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

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

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

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

состояния G матрицы

Рис3. Спектр собственных значений матрицы Google Кембриджского университета из рис.2 при $\alpha =1$, синие точки показывают собственные значения изолированных подпространств, красные точки показывают собственные значения основного компонента (из )

Для $0<\alpha <1$ существует только одно максимальное собственное значение $\lambda =1$ с соответствующим правым собственным вектором, имеющим неотрицательные элементы $P_{i}$ которое можно рассматривать как стационарное распределение вероятностей. Эти вероятности, упорядоченные по убыванию значений, дают вектор PageRank. $P_{i}$ с PageRank $K_{i}$используется поиском Google для ранжирования веб-страниц. Обычно для Всемирной паутины имеется такое $P\propto 1/K^{\beta }$ с $\beta \approx 0.9$. Количество узлов с заданным значением PageRank масштабируется как $N_{P}\propto 1/P^{\nu }$ с показателем $\nu =1+1/\beta \approx 2.1$. Левый собственный вектор в $\lambda =1$имеет постоянные матричные элементы. С $0<\alpha$ все собственные значения движутся как $\lambda _{i}\rightarrow \alpha \lambda _{i}$ кроме максимального собственного значения $\lambda =1$, который остается неизменным. Вектор PageRank варьируется в зависимости от $\alpha$ но другие собственные векторы с $\lambda _{i}<1$ остаются неизменными из-за их ортогональности постоянному левому вектору при $\lambda =1$. Разрыв между $\lambda =1$ и другое собственное значение $1-\alpha \approx 0.15$ дает быструю сходимость случайного начального вектора к PageRank примерно после 50 умножений на $G$ матрица.

Рис4. Распределение собственных значений $\lambda _{i}$ матриц Google в комплексной плоскости при $\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 г.) (из )

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

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

Рис5. Распределение собственных значений $\lambda$ в комплексной плоскости для матрицы Google $G$ ядра Linux версии 2.6.32 с размером матрицы $N=285509$ в $\alpha =0.85$, единичный круг показан сплошной кривой (от )

Рис.6. Грубое распределение вероятностей собственных состояний матрицы Google для ядра Linux версии 2.6.32. Горизонтальные линии показывают первые 64 собственных вектора, упорядоченных по вертикали по формуле $|\lambda _{i}|$ (от )

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

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

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

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

См. также

• ЧейРанк
• Итерация Арнольди
• Цепь Маркова
• Оператор трансфера
• Теорема Перрона – Фробениуса
• Поисковые системы в Интернете

Ссылки

• Серра-Капиццано, Стефано (2005). «Иорданская каноническая форма матрицы Google: потенциальный вклад в вычисление PageRank». СИАМ Дж. Матричный анал. Приложение . 27 (2): 305. дои : 10.1137/s0895479804441407 . hdl : 11383/1494937 .
• Улам, Станислав (1960). Сборник математических задач . Межнаучные трактаты по чистой и прикладной математике. Нью-Йорк: Межнаучный. п. 73.
• Фройланд Г.; Падберг К. (2009). «Почти инвариантные множества и инвариантные многообразия — соединение вероятностных и геометрических описаний когерентных структур в потоках». Физика Д. 238 (16): 1507. Бибкод : 2009PhyD..238.1507F . дои : 10.1016/j.physd.2009.03.002 .
• Шепелянский Д.Л.; Жиров О.В. (2010). «Матрица Google, динамические аттракторы и сети Улама». Физ. Преподобный Е. 81 (3): 036213. arXiv : 0905.4162 . Бибкод : 2010PhRvE..81c6213S . дои : 10.1103/physreve.81.036213 . ПМИД   20365838 . S2CID   15874766 .
• Эрманн Л.; Шепелянский Д.Л. (2010). «Матрица Google и сети Улама карт перемежаемости». Физ. Преподобный Е. 81 (3): 036221. arXiv : 0911.3823 . Бибкод : 2010PhRvE..81c6221E . дои : 10.1103/physreve.81.036221 . ПМИД   20365846 . S2CID   388806 .
• Эрманн Л.; Шепелянский Д.Л. (2010). «Метод Улама и фрактальный закон Вейля для операторов Перрона-Фробениуса». Евро. Физ. Дж. Б. 75 (3): 299–304. arXiv : 0912.5083 . Бибкод : 2010EPJB...75..299E . дои : 10.1140/epjb/e2010-00144-0 . S2CID   54899977 .
• Фрам К.М.; Шепелянский Д.Л. (2010). «Метод Улама для стандартного отображения Чирикова». Евро. Физ. Дж. Б. 76 (1): 57–68. arXiv : 1004.1349 . Бибкод : 2010EPJB...76...57F . дои : 10.1140/epjb/e2010-00190-6 . S2CID   55539783 .
• Чепелянский, Алексей Д. (2010). «К физическим законам архитектуры программного обеспечения». arXiv : 1003.5455 [ cs.SE ].
• Шепелянский Д.Л.; Жиров О.В. (2010). «К матрице мозга Google». Физ. Летт. А. ​ 374 (31–32): 3206. arXiv : 1002.4583 . Бибкод : 2010PhLA..374.3206S . дои : 10.1016/j.physleta.2010.06.007 .
• Абель М.; Шепелянский Д.Л. (2011). «Гугл-матрица управления бизнес-процессами». Евро. Физ. Дж. Б. 84 (4): 493. arXiv : 1009.2631 . Бибкод : 2011EPJB...84..493A . дои : 10.1140/epjb/e2010-10710-y . S2CID   15510734 .
• Кандия, Вивек; Шепелянский, Дима Л. (2013). «Матричный анализ последовательностей ДНК Google» . ПЛОС ОДИН . 8 (5): e61519. arXiv : 1301.1626 . Бибкод : 2013PLoSO...861519K . дои : 10.1371/journal.pone.0061519 . ПМК   3650020 . ПМИД   23671568 .
• Эом, Ён-Хо; Шепелянский, Дима Л. (2013). «Выявление переплетения культур посредством ранжирования многоязычных статей Википедии» . ПЛОС ОДИН . 8 (10): е74554. arXiv : 1306.6259 . Бибкод : 2013PLoSO...874554E . дои : 10.1371/journal.pone.0074554 . ПМЦ   3789750 . ПМИД   24098338 .
• Брин С.; Пейдж Л. (1998). «Анатомия крупномасштабной гипертекстовой поисковой системы в Интернете». Компьютерные сети и системы ISDN . 30 (1–7): 107. doi : 10.1016/s0169-7552(98)00110-x . S2CID   7587743 .
• Массимо, Франческо (2010). «PageRank: стоим на плечах гигантов». arXiv : 1002.2858 [ cs.IR ].
• Винья, Себастьяно (2010). «Спектральный рейтинг» (PDF) .

Внешние ссылки

• Матрица Google в Scholarpedia
• Google PR закрылся
• Видеолекции на семинаре IHES «Матрица Google: фундамент, приложения и не только», октябрь 2018 г.