ЧейРанк

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

CheiRank . — это собственный вектор с максимальным действительным собственным значением матрицы Google $G^{*}$ построен для направленной сети с инвертированными направлениями связей. Он аналогичен вектору PageRank , который ранжирует узлы сети в среднем пропорционально количеству входящих ссылок, являющемуся максимальным собственным вектором матрицы Google. $G$ с заданным начальным направлением ссылок. За счет инверсии направлений каналов CheiRank ранжирует узлы сети в среднем пропорционально количеству исходящих каналов. Поскольку каждый узел принадлежит как векторам CheiRank, так и векторам PageRank , ранжирование информационного потока в направленной сети становится двумерным .

Определение

Рис1. Распределение вызовов процедур сети ядра Linux в плоскости вероятности PageRank $x=\log _{10}P_{i}$ и вероятность CheiRank $y=\log _{10}{P}_{i}^{*}$ для Linux версии 2.6.32 с размером матрицы $N=285509$ в $\alpha =0.85$, цвет показывает плотность узлов: белый — максимум, синий — минимум, в чёрном пространстве узлов нет (из Чепелянского)

Для заданной направленной сети матрица Google строится способом, описанным в статье Матрица Google . Вектор PageRank — это собственный вектор с максимальным действительным собственным значением. $\lambda =1$. Оно было введено в и обсуждается в статье PageRank . Аналогичным образом CheiRank — это собственный вектор с максимальным действительным собственным значением матрицы $G^{*}$ построен так же, как $G$ но с использованием инвертированного направления связей в изначально заданной матрице смежности . Обе матрицы $G$ и $G^{*}$ принадлежат классу операторов Перрона–Фробениуса и согласно теореме Перрона–Фробениуса CheiRank $P_{i}^{*}$ и PageRank $P_{i}$ собственные векторы имеют неотрицательные компоненты, которые можно интерпретировать как вероятности. Таким образом, все $N$ узлы $i$ сети можно упорядочить в порядке убывания вероятности с рангами $K_{i}^{*},K_{i}$ для CheiRank и PageRank $P_{i}^{*},P_{i}$ соответственно. В среднем вероятность PageRank $P_{i}$ пропорциональна количеству входящих ссылок с $P_{i}\propto 1/{K_{i}}^{\beta }$. Для сети World Wide Web (WWW) показатель степени $\beta =1/(\nu -1)\approx 0.9$ где $\nu \approx 2.1$ — показатель распределения входящих ссылок. Аналогичным образом вероятность CheiRank в среднем пропорциональна количеству исходящих ссылок с $P_{i}^{*}\propto 1/{K_{i}^{*}}^{\beta ^{*}}$ с $\beta ^{*}=1/(\nu ^{*}-1)\approx 0.6$ где $\nu ^{*}\approx 2.7$ — показатель распределения исходящих ссылок WWW. CheiRank был введен для сети вызова процедур программного обеспечения ядра Linux в: сам термин использовался у Жирова. В то время как PageRank выделяет очень известные и популярные узлы, CheiRank выделяет очень коммуникативные узлы. Узлы Top PageRank и CheiRank имеют определенную аналогию с авторитетными источниками и хабами, появляющимися в алгоритме HITS. но HITS зависит от запроса, а вероятности ранга $P_{i}$ и $P_{i}^{*}$ классифицировать все узлы сети. Поскольку каждый узел принадлежит как CheiRank, так и PageRank, мы получаем двумерный рейтинг узлов сети. Ранние исследования PageRank в сетях с перевернутым направлением ссылок проводились. но свойства двумерного ранжирования подробно не анализировались.

Рис2. Зависимость вероятности PageRank $P$ (красная кривая) и CheiRank $P^{*}$ (синяя кривая) на соответствующих индексах ранга $K$ и $K^{*}$. Прямые пунктирные линии показывают степенную зависимость с наклоном $\beta =0.92;0.57$ соответственно, что соответствует $\beta =1/(\nu -1)$ (from Zhirov)

Примеры

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

Рис3. Распределение плотности англоязычных статей Википедии (2009 г.) в плоскости индексов PageRank и CheiRank $0<\ln K,\ln K^{*}<\ln N$ показано цветом: синий — минимум, белый — максимум (черный — ноль); зеленые/красные точки обозначают 100 лучших личностей по данным PageRank/CheiRank, желтые плюсы показывают 100 лучших личностей из книги Харта, количество статей. $N=3282257$ (from Zhirov)

Зависимость $P,P^{*}$ на $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, как это обсуждается у Жирова. Он дает лучшие статьи Википедии 1.Индия, 2.Сингапур, 3.Пакистан.

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

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

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

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

Рис4. Пример направленной сети

Рис5. Связанная матрица $S$

Рис6. Связанная матрица $S^{*}$

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

См. также

• PageRank , алгоритм HITS , матрица Google
• Цепи Маркова , Оператор Трансфера , Теорема Перрона–Фробениуса
• Поиск информации
• Поисковые системы в Интернете

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

• Двумерный рейтинг статей Википедии
• Мировая торговля: CheiRank против PageRank
• На пути к двумерным поисковым системам
• Лучшие люди Википедии