Главная › Новости

Понятие ссылочного графа

Опубликовано: 22.08.2018

Если рассматривать ресурсы сети как вершины графа, а цитирование других ресурсов (ссылочные связи между сайтами) как связи вершин графа (ребра), тогда ссылочный граф можно представить в виде диаграммы, как показано на рисунке.

где А, B, …, F — определенные сайты в индексе поисковой системы;

стрелки изображают направление связей — односторонние либо двусторонние.

Из ссылочного графа (др. название веб-граф) можно определять различные параметры сайтов, такие как: индекс цитируемости, авторитетность ресурса, вероятность нахождения пользователя на том или ином сайте, и другие. Для хранения веб-графа в машинном виде, используют другое представление данных, а именно матрицы смежности и инцидентности и, возможно, матрицу достижимости .

Каждая строка в матрице инциндентности соответствует определенной вершине графа, а столбцы соответствуют его связям. В ячейку на пересечении i-ой строки с j-м столбцом матрицы записывается 1 в случае если связь j «выходит» из вершины i, −1 если связь «входит» в вершину, любое число отличное от 0, 1, -1 если связь является петлей, и 0 во всех остальных случаях. Такой способ представления связей между ресурсами является самым емким и неудобным для хранения, но облегчает нахождение циклов в графе (сателлиты и сайты, участвующие в кольцевом обмене, легко обнаруживаются).

Для приведенного выше примера, матрица инцидентности будет иметь вид:

  (AB) (BC) (BE) (DC) (AD) (DA) (EC) (ED) (AE) A B C D E F

1	0	0	0	1	-1	0	0	1
-1	1	1	0	0	0	0	0	0
0	-1	0	-1	0	0	-1	0	0
0	0	0	1	-1	1	0	-1	0
0	0	-1	0	0	0	1	1	-1
0	0	0	0	0	0	0	0	0

В матрице смежности столбцы и строки соответствуют вершинам графа. В каждой ячейке этой матрицы записывается число, определяющее наличие связи от вершины-строки к вершине-столбцу или наоборот. Для нашего случая матрица смежности будет иметь вид:

  A B C D E F A B C D E F

0	1	0	1	1	0
0	0	1	0	1	0
0	0	0	0	0	0
1	0	1	0	0	0
0	0	1	1	0	0
0	0	0	0	0	0

В случае взвешенного графа каждому ребру присваивается определенный вес w и, соответственно, в матрице смежности вместо единиц будут присутствовать веса связей.

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