CheiRank - CheiRank

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

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

Определение

Рисунок 1. Распределение вызовов процедур сети ядра Linux в плоскости вероятности PageRank

{ Displaystyle х = журнал _ {10} P_ {я}}

и вероятность CheiRank

{ displaystyle y = log _ {10} {P} _ {i} ^ {*}}

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

{ displaystyle N = 285509}

в

{ displaystyle alpha = 0,85}

, цвет показывает плотность узлов с белым для максимума и синим для минимума, черное пространство не имеет узлов (от Чепелянского)

Для заданной направленной сети матрица Google строится так, как описано в статье. Матрица Google. В PageRank вектор - это собственный вектор с максимальным действительным собственным значением ${ displaystyle lambda = 1}$ . Он был введен в^[1] и обсуждается в статье PageRank. Аналогичным образом CheiRank - это собственный вектор с максимальным действительным собственным значением матрицы ${ displaystyle G ^ {*}}$ построен так же, как ${ displaystyle G}$ но с использованием перевернутого направления ссылок в изначально заданной матрице смежности. Обе матрицы ${ displaystyle G}$ и ${ displaystyle G ^ {*}}$ принадлежат к классу операторов Перрона – Фробениуса и согласно Теорема Перрона – Фробениуса CheiRank ${ displaystyle P_ {i} ^ {*}}$ и PageRank ${ displaystyle P_ {i}}$ собственные векторы имеют неотрицательные компоненты, которые можно интерпретировать как вероятности.^[2]^[3] Таким образом, все ${ displaystyle N}$ узлы ${ displaystyle i}$ сети можно упорядочить в порядке убывания вероятности с рангами ${ displaystyle K_ {i} ^ {*}, K_ {i}}$ для CheiRank и PageRank ${ displaystyle P_ {i} ^ {*}, P_ {i}}$ соответственно. В среднем вероятность PageRank ${ displaystyle P_ {i}}$ пропорционально количеству входящих ссылок с ${ Displaystyle P_ {я} propto 1 / {K_ {i}} ^ { beta}}$ .^[4]^[5]^[6] Для сети World Wide Web (WWW) показатель степени ${ Displaystyle бета = 1 / ( nu -1) приблизительно 0,9}$ куда ${ displaystyle nu приблизительно 2,1}$ - показатель распределения входящих ссылок.^[4]^[5] Аналогичным образом вероятность CheiRank в среднем пропорциональна количеству исходящих ссылок с ${ displaystyle P_ {i} ^ {*} propto 1 / {K_ {i} ^ {*}} ^ { beta ^ {*}}}$ с ${ displaystyle beta ^ {*} = 1 / ( nu ^ {*} - 1) приблизительно 0,6}$ куда ${ displaystyle nu ^ {*} приблизительно 2,7}$ - показатель распределения исходящих ссылок WWW.^[4]^[5] CheiRank был представлен для сети вызова процедур программного обеспечения ядра Linux в^[7] сам термин употреблялся в Жирове.^[8] В то время как PageRank выделяет очень известные и популярные узлы, CheiRank выделяет очень коммуникативные узлы. Узлы Top PageRank и CheiRank имеют определенную аналогию с властями и узлами, фигурирующими в Алгоритм HITS^[9] но HITS зависит от запроса, в то время как вероятности ранга ${ displaystyle P_ {i}}$ и ${ displaystyle P_ {i} ^ {*}}$ классифицируйте все узлы сети. Поскольку каждый узел принадлежит как CheiRank, так и PageRank, мы получаем двумерное ранжирование сетевых узлов. Ранние исследования PageRank в сетях с перевернутым направлением ссылок.^[10]^[11] но свойства двумерного ранжирования подробно не анализировались.

Рис 2. Зависимость вероятности PageRank

{ displaystyle P}

(красная кривая) и CheiRank

{ Displaystyle P ^ {*}}

(синяя кривая) от соответствующих индексов ранга

{ displaystyle K}

и

{ displaystyle K ^ {*}}

. Прямыми пунктирными линиями показана степенная зависимость с наклоном

{ displaystyle beta = 0,92; 0,57}

соответственно, соответствующие

{ Displaystyle бета = 1 / ( ню -1)}

(от Жирова)

Примеры

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

Рис 3. Распределение плотности английских статей Wikipedia (2009 г.) в плоскости индексов PageRank и CheiRank

{ Displaystyle 0 < пер К, пер К ^ {*} < пер N}

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

{ displaystyle N = 3282257}

(от Жирова)

Зависимость ${ displaystyle P, P ^ {*}}$ на ${ displaystyle K, K ^ {*}}$ для сети гиперссылок сеть статей Википедии на английском языке показана на рис.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. Связанная матрица

{ displaystyle S}

Рис 6. Связанная матрица

{ Displaystyle S ^ {*}}

Простой пример построения матриц Google ${ displaystyle G}$ и ${ displaystyle G ^ {*}}$ , используемый для определения связанных векторов PageRank и CheiRank, приведен ниже. Пример ориентированной сети с 7 узлами показан на рисунке 4. Матрица ${ displaystyle S}$ , построенный по правилам описанным в статье Матрица Google, показан на рисунке 5; соответствующая матрица Google ${ Displaystyle G = альфа S + (1- альфа) ее ^ {T} / N}$ а вектор PageRank - это правый собственный вектор ${ displaystyle G}$ с единичным собственным значением ( ${ displaystyle GP = P}$ ). Аналогичным образом для определения собственного вектора CheiRank все направления связей на рис.4 инвертируются, тогда матрица ${ Displaystyle S ^ {*}}$ построен по тем же правилам, что и для сети с перевернутыми направлениями связи, как показано на рисунке 6. Соответствующая матрица Google ${ Displaystyle G ^ {*} = альфа S ^ {*} + (1- альфа) ее ^ {T} / N}$ а вектор CheiRank является правым собственным вектором ${ displaystyle G ^ {*}}$ с единичным собственным значением ( ${ Displaystyle G ^ {*} P ^ {*} = P ^ {*}}$ ). Здесь ${ displaystyle alpha приблизительно 0,85}$ - коэффициент демпфирования, принимаемый за обычное значение.

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

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

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

[Donato-4] а ^б ^c Донато Д .; Laura L .; Леонарди С .; Миллоцци С. (2004), "Крупномасштабные свойства веб-графа", Европейский физический журнал B, 38 (2): 239, Bibcode:2004EPJB ... 38..239D, Дои:10.1140 / epjb / e2004-00056-6, S2CID 10640375

[Pandurangan-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

[Chepelianskii-7] а ^б ^c Чепелянский, Алексей Д. (2010). «К физическим законам для архитектуры программного обеспечения». arXiv:1003.5455 [cs.SE ].

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

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

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]