CheiRank - Википедия - CheiRank

Узлы со ссылками в плоскости PageRank и CheiRank

В CheiRank является собственный вектор с максимальным действительным собственным значением Матрица Google построен для направленной сети с инвертированными направлениями связей. Это похоже на PageRank вектор, который ранжирует узлы сети в среднем пропорционально количеству входящих ссылок, которое является максимальным собственным вектором Матрица Google с заданным начальным направлением ссылок. Из-за инверсии направлений ссылок CheiRank ранжирует узлы сети в среднем пропорционально количеству исходящих ссылок. Поскольку каждый узел принадлежит как CheiRank, так и PageRank векторов ранжирование информационного потока в направленной сети становится двумерный.

Определение

Рисунок 1. Распределение вызовов процедур сети ядра Linux в плоскости вероятности PageRank и вероятность CheiRank для Linux версии 2.6.32 с размером матрицы в , цвет показывает плотность узлов с белым для максимума и синим для минимума, черное пространство не имеет узлов (от Чепелянского)

Для заданной направленной сети матрица Google строится так, как описано в статье. Матрица Google. В PageRank вектор - это собственный вектор с максимальным действительным собственным значением . Он был введен в[1] и обсуждается в статье PageRank. Аналогичным образом CheiRank - это собственный вектор с максимальным действительным собственным значением матрицы построен так же, как но с использованием перевернутого направления ссылок в изначально заданной матрице смежности. Обе матрицы и принадлежат к классу операторов Перрона – Фробениуса и согласно Теорема Перрона – Фробениуса CheiRank и PageRank собственные векторы имеют неотрицательные компоненты, которые можно интерпретировать как вероятности.[2][3] Таким образом, все узлы сети можно упорядочить в порядке убывания вероятности с рангами для CheiRank и PageRank соответственно. В среднем вероятность PageRank пропорционально количеству входящих ссылок с .[4][5][6] Для сети World Wide Web (WWW) показатель степени куда - показатель распределения входящих ссылок.[4][5] Аналогичным образом вероятность CheiRank в среднем пропорциональна количеству исходящих ссылок с с куда - показатель распределения исходящих ссылок WWW.[4][5] CheiRank был представлен для сети вызова процедур программного обеспечения ядра Linux в[7] сам термин употреблялся в Жирове.[8] В то время как PageRank выделяет очень известные и популярные узлы, CheiRank выделяет очень коммуникативные узлы. Узлы Top PageRank и CheiRank имеют определенную аналогию с властями и узлами, фигурирующими в Алгоритм HITS[9] но HITS зависит от запроса, в то время как вероятности ранга и классифицируйте все узлы сети. Поскольку каждый узел принадлежит как CheiRank, так и PageRank, мы получаем двумерное ранжирование сетевых узлов. Ранние исследования PageRank в сетях с перевернутым направлением ссылок.[10][11] но свойства двумерного ранжирования подробно не анализировались.

Рис 2. Зависимость вероятности PageRank (красная кривая) и CheiRank (синяя кривая) от соответствующих индексов ранга и . Прямыми пунктирными линиями показана степенная зависимость с наклоном соответственно, соответствующие (от Жирова)

Примеры

Пример распределения узлов в плоскости PageRank и CheiRank показан на рисунке 1 для сети вызова процедур программного обеспечения ядра Linux.[7]

Рис 3. Распределение плотности английских статей Wikipedia (2009 г.) в плоскости индексов PageRank и CheiRank показаны цветом с синим для минимума и белым для максимума (черный для нуля); зеленые / красные точки показывают 100 лучших личностей из PageRank / CheiRank, желтые плюсы показывают 100 лучших личностей из книги Харта, количество статей (от Жирова)

Зависимость на для сети гиперссылок сеть статей Википедии на английском языке показана на рис.2 от Жирова. Распределение этих статей в плоскости PageRank и CheiRank показано на рисунке 3 от Жирова. Разницу между PageRank и CheiRank ясно видно из названий статей в Википедии (2009 г.) с наивысшим рейтингом. В верхней части PageRank у нас есть 1. Соединенные Штаты, 2. Соединенное Королевство, 3. Франция, в то время как для CheiRank мы находим 1. Портал: Содержание / Обзор знаний / География и места, 2. Список руководителей штатов по годам, 3. Портал: Содержание / Указатель / География и места. Очевидно, что PageRank отбирает первые статьи на широко известную тему с большим количеством входящих ссылок, в то время как CheiRank выбирает первые высоко коммуникативные статьи с множеством исходящих ссылок. Поскольку статьи распределены в 2D, они могут быть ранжированы различными способами в соответствии с проекцией 2D набора на линию. Горизонтальные и вертикальные линии соответствуют PageRank и CheiRank, 2DRank сочетает в себе свойства CheiRank и PageRank, как это обсуждается у Жирова.[8] Он дает лучшие статьи Википедии: 1. Индия, 2. Сингапур, 3. Пакистан.

2D-рейтинг подчеркивает свойства статей Википедии в новой, богатой и плодотворной манере. Согласно рейтингу страницы 100 лучших личностей, описанных в статьях Википедии, относятся к 5 основным категориям деятельности: 58 ​​(политика), 10 (религия), 17 (искусство), 15 (наука), 0 (спорт), и, следовательно, важность политиков сильно переоценен. CheiRank дает соответственно 15, 1, 52, 16, 16, а для 2DRank - 24, 5, 62, 7, 2. Такой тип 2D-ранжирования может найти полезные приложения для различных сложных направленных сетей, включая WWW.

CheiRank и PageRank естественно появляются для мировой торговой сети, или Международная торговля, где они и связаны с потоками экспорта и импорта для данной страны соответственно.[12]

Рассмотрены возможности развития двумерных поисковых систем на основе PageRank и CheiRank.[13] Направленные сети можно охарактеризовать с помощью коррелятора между векторами PageRank и CheiRank: в некоторых сетях этот коррелятор близок к нулю (например, сеть ядра Linux), в то время как другие сети имеют большие значения коррелятора (например, Wikipedia или университетские сети).[7][13]

Пример простой сети

Рис 4. Пример направленной сети
Рис 5. Связанная матрица
Рис 6. Связанная матрица

Простой пример построения матриц Google и , используемый для определения связанных векторов PageRank и CheiRank, приведен ниже. Пример ориентированной сети с 7 узлами показан на рисунке 4. Матрица , построенный по правилам описанным в статье Матрица Google, показан на рисунке 5; соответствующая матрица Google а вектор PageRank - это правый собственный вектор с единичным собственным значением (). Аналогичным образом для определения собственного вектора CheiRank все направления связей на рис.4 инвертируются, тогда матрица построен по тем же правилам, что и для сети с перевернутыми направлениями связи, как показано на рисунке 6. Соответствующая матрица Google а вектор CheiRank является правым собственным вектором с единичным собственным значением (). Здесь - коэффициент демпфирования, принимаемый за обычное значение.

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

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

  1. ^ Brin S .; Пейдж Л. (1998), "Анатомия крупномасштабной гипертекстовой поисковой машины в Интернете", Компьютерные сети и системы ISDN, 30 (1–7): 107, Дои:10.1016 / S0169-7552 (98) 00110-X
  2. ^ Лэнгвилл, Эми Н.; Карл Мейер (2006). PageRank Google и не только. Princeton University Press. ISBN  0-691-12202-4.
  3. ^ Остин, Дэвид (2008). "Как Google находит вашу иглу в стоге сена Интернета". Столбцы характеристик AMS.
  4. ^ а б c Донато Д .; Laura L .; Леонарди С .; Миллоцци С. (2004), "Крупномасштабные свойства веб-графа", Европейский физический журнал B, 38 (2): 239, Bibcode:2004EPJB ... 38..239D, Дои:10.1140 / epjb / e2004-00056-6, S2CID  10640375
  5. ^ а б c Pandurangan G .; Ranghavan P .; Упфаль Э. (2005), «Использование PageRank для характеристики веб-структуры», Интернет-математика., 3: 1, Дои:10.1080/15427951.2006.10129114
  6. ^ Литвак Н .; Шейнхардт W.R.W; Волкович Ю. (2008), Вероятностная связь между In-Degree и PageRank, Конспект лекций по информатике, 4936, п. 72
  7. ^ а б c Чепелянский, Алексей Д. (2010). «К физическим законам для архитектуры программного обеспечения». arXiv:1003.5455 [cs.SE ].
  8. ^ а б Жиров А.О .; Жиров О.В .; Шепелянский Д.Л. (2010), «Двумерный рейтинг статей Википедии», Европейский физический журнал B, 77 (4): 523, arXiv:1006.4270, Bibcode:2010EPJB ... 77..523Z, Дои:10.1140 / epjb / e2010-10500-7, S2CID  18014470
  9. ^ Клейнберг, Джон (1999). «Авторитетные источники в среде с гиперссылками». Журнал ACM. 46 (5): 604–632. Дои:10.1145/324133.324140.
  10. ^ Фогарас, Д. (2003), С чего начать просмотр веб-страниц?, Конспект лекций по информатике, 2877, п. 65
  11. ^ Hrisitidis V .; Hwang H .; Папаконстантину Ю. (2008 г.), «Авторитетный поиск по ключевым словам в базах данных», ACM Trans. База данных Syst., 33: 1, Дои:10.1145/1331904.1331905
  12. ^ Ermann L .; Шепелянский Д.Л. (2011). «Матрица Google мировой торговой сети». Acta Physica Polonica A. 120 (6А): А. arXiv:1103.5027. Bibcode:2011AcPPA.120..158E. Дои:10.12693 / APhysPolA.120.A-158. S2CID  18315654.
  13. ^ а б Ermann L .; Чепелянский А.Д .; Шепелянский Д.Л. (2011). «К двумерным поисковым системам». Журнал физики A: математический и теоретический. 45 (27): 275101. arXiv:1106.6215. Bibcode:2012JPhA ... 45A5101E. Дои:10.1088/1751-8113/45/27/275101. S2CID  14827486.

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