Матрица Google
![]() | В этой статье есть несколько проблем. Пожалуйста, помогите улучшить его или обсудите эти проблемы на странице обсуждения . ( Узнайте, как и когда удалять эти шаблонные сообщения )
|

Матрица Google — это особая стохастическая матрица , которая используется Google алгоритмом PageRank . Матрица представляет собой граф, ребра которого представляют связи между страницами. PageRank каждой страницы затем может быть сгенерирован итеративно из матрицы Google с использованием метода мощности . Однако для того, чтобы степенной метод сходился, матрица должна быть стохастической, неприводимой и апериодической .
Матрица смежности A и матрица Маркова S [ править ]
Чтобы сгенерировать матрицу Google G , мы должны сначала сгенерировать матрицу смежности A , которая представляет отношения между страницами или узлами.
Предполагая, что страниц N , мы можем заполнить A, выполнив следующие действия:
- Матричный элемент заполняется 1, если узел имеет ссылку на узел и 0 в противном случае; это матрица смежности ссылок.
- Связанная матрица S, соответствующая переходам в цепи Маркова. [ сломанный якорь ] данной сети строится из A путем деления элементов столбца «j» на количество где — общее количество исходящих ссылок от узла j ко всем остальным узлам. Столбцы, имеющие нулевые элементы матрицы, соответствующие висячим узлам, заменяются постоянным значением 1/N . Такая процедура добавляет ссылку из каждого стока, висячее состояние к каждому другому узлу.
- Теперь по построению сумма всех элементов в любом столбце матрицы S равна единице. Таким образом, матрица S математически корректно определена и принадлежит классу цепей Маркова и классу операторов Перрона-Фробениуса. Это делает S подходящим для алгоритма PageRank .
Построение матрицы Google G [ править ]

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

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

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


Матрица Google может быть построена и для других направленных сетей, например, для сети вызова процедур программного обеспечения ядра Linux, представленной в [15]. В этом случае спектр описывается фрактальным законом Вейля с фрактальной размерностью (см. рис.5 из [9] ). Численный анализ показывает, что собственные состояния матрицы локализованы (см. рис.6 с [9] ). Итерационный метод Арнольди позволяет вычислять множество собственных значений и собственных векторов для матриц достаточно большого размера [13]. [5] [9]
Другие примеры матрица включает матрицу Google мозга [17]и управление бизнес-процессами [18], см. также. [1] Применение матричного анализа Google дляПоследовательности ДНК описаны в [20]. Такой матричный подход Google позволяет также анализировать переплетение культур посредством ранжирования многоязычных статей Википедии о людях [21].
Исторические заметки [ править ]
Матрица Google с коэффициентом затухания была описана Сергеем Брином и Ларри Пейджем в 1998 году [22], см. также статьи по истории PageRank [23],[24].
См. также [ править ]
- ЧейРанк
- Итерация Арнольди
- Цепь Маркова
- Оператор трансфера
- Теорема Перрона – Фробениуса
- Поисковые системы в Интернете
Ссылки [ править ]
- ^ Jump up to: Перейти обратно: а б с Эрманн, Л.; Чепелянский А.Д.; Шепелянский, Д.Л. (2011). «На пути к двумерным поисковым системам». Журнал физики А. 45 (27): 275101. arXiv : 1106.6215 . Бибкод : 2012JPhA...45A5101E . дои : 10.1088/1751-8113/45/27/275101 . S2CID 14827486 .
- ^ Jump up to: Перейти обратно: а б с д и Лэнгвилл, Эми Н .; Мейер, Карл (2006). PageRank Google и не только . Издательство Принстонского университета . ISBN 978-0-691-12202-1 .
- ^ Jump up to: Перейти обратно: а б Остин, Дэвид (2008). «Как Google находит вашу иголку в стоге сена в Интернете» . Столбцы функций AMS.
- ^ Ло, Эдит (9 октября 2008 г.). «Лекция 12 о PageRank» (PDF) .
- ^ Jump up to: Перейти обратно: а б с д Фрам, К.М.; Джорджо, Б.; Шепелянский, Д.Л. (01.11.2011). «Всеобщее появление PageRank». Журнал физики А. 44 (46): 465101. arXiv : 1105.1062 . Бибкод : 2011JPhA...44T5101F . дои : 10.1088/1751-8113/44/46/465101 . S2CID 16292743 .
- ^ Донато, Дебора; Лаура, Луиджи; Леонарди, Стефано; Миллоцци, Стефано (30 марта 2004 г.). «Крупномасштабные свойства веб-графа» (PDF) . Европейский физический журнал Б. 38 (2): 239–243. Бибкод : 2004EPJB...38..239D . CiteSeerX 10.1.1.104.2136 . дои : 10.1140/epjb/e2004-00056-6 . S2CID 10640375 .
- ^ Пандуранган, Гопал; Рангхаван, Прабхакар; Упфал, Эли (2005). «Использование PageRank для характеристики веб-структуры» (PDF) . Интернет-математика . 3 (1): 1–20. дои : 10.1080/15427951.2006.10129114 . S2CID 101281 .
- ^ Jump up to: Перейти обратно: а б с Жоржо, Бертран; Жиро, Оливье; Шепелянский, Дима Л. (25 мая 2010 г.). «Спектральные свойства матрицы Google Всемирной паутины и других направленных сетей». Физический обзор E . 81 (5): 056109. arXiv : 1002.3342 . Бибкод : 2010PhRvE..81e6109G . дои : 10.1103/PhysRevE.81.056109 . ПМИД 20866299 . S2CID 14490804 .
- ^ Jump up to: Перейти обратно: а б с д и ж Эрманн, Л.; Чепелянский А.Д.; Шепелянский, Д.Л. (2011). «Фрактальный закон Вейля для архитектуры ядра Linux». Европейский физический журнал Б. 79 (1): 115–120. arXiv : 1005.1395 . Бибкод : 2011EPJB...79..115E . дои : 10.1140/epjb/e2010-10774-7 . S2CID 445348 .
- Серра-Капиццано, Стефано (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) .