Если рассматривать ресурсы сети как вершины графа, а цитирование других ресурсов (ссылочные связи между сайтами) как связи вершин графа (ребра), тогда ссылочный граф можно представить в виде диаграммы, как показано на рисунке.
где А, B, …, F — определенные сайты в индексе поисковой системы;
стрелки изображают направление связей — односторонние либо двусторонние.
Из ссылочного графа (др. название веб-граф) можно определять различные параметры сайтов, такие как: индекс цитируемости, авторитетность ресурса, вероятность нахождения пользователя на том или ином сайте, и другие. Для хранения веб-графа в машинном виде, используют другое представление данных, а именно матрицы смежности и инцидентности и, возможно, матрицу достижимости.
Каждая строка в матрице инциндентности соответствует определенной вершине графа, а столбцы соответствуют его связям. В ячейку на пересечении i-ой строки с j-м столбцом матрицы записывается 1 в случае если связь j «выходит» из вершины i, −1 если связь «входит» в вершину, любое число отличное от 0, 1, -1 если связь является петлей, и 0 во всех остальных случаях. Такой способ представления связей между ресурсами является самым емким и неудобным для хранения, но облегчает нахождение циклов в графе (сателлиты и сайты, участвующие в кольцевом обмене, легко обнаруживаются).
Для приведенного выше примера, матрица инцидентности будет иметь вид:
| (AB) | (BC) | (BE) | (DC) | (AD) | (DA) | (EC) | (ED) | (AE) | |
|---|---|---|---|---|---|---|---|---|---|
| A | 1 | 0 | 0 | 0 | 1 | -1 | 0 | 0 | 1 |
| B | -1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| C | 0 | -1 | 0 | -1 | 0 | 0 | -1 | 0 | 0 |
| D | 0 | 0 | 0 | 1 | -1 | 1 | 0 | -1 | 0 |
| E | 0 | 0 | -1 | 0 | 0 | 0 | 1 | 1 | -1 |
| F | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
В матрице смежности столбцы и строки соответствуют вершинам графа. В каждой ячейке этой матрицы записывается число, определяющее наличие связи от вершины-строки к вершине-столбцу или наоборот. Для нашего случая матрица смежности будет иметь вид:
| A | B | C | D | E | F | |
|---|---|---|---|---|---|---|
| A | 0 | 1 | 0 | 1 | 1 | 0 |
| B | 0 | 0 | 1 | 0 | 1 | 0 |
| C | 0 | 0 | 0 | 0 | 0 | 0 |
| D | 1 | 0 | 1 | 0 | 0 | 0 |
| E | 0 | 0 | 1 | 1 | 0 | 0 |
| F | 0 | 0 | 0 | 0 | 0 | 0 |
В случае взвешенного графа каждому ребру присваивается определенный вес w и, соответственно, в матрице смежности вместо единиц будут присутствовать веса связей.
Что касается поисковых систем, то при составлении ссылочных графов и расчете зависимых показателей они не учитывают ряд немодерируемых ресурсов, таких как линкопомойки, гостевые книги, сетевые конференции, каталоги и другие сайты, где кто угодно может добавлять ссылки без контроля со стороны владельца ресурса и, таким образом, влиять на итоговый ссылочный граф, который позволяет находить ряд параметров сайтов, являющимися факторами ранжирования в поисковой системе.
7 Ответов
Terehoff
Декабрь 29, 2008 at 11:31
1Вот это уже интереснее, ближе к моей научной тематике. В принципе тут зашита хорошая философия, которую можно красиво формализовать и написать на эту тему даже целую диссертацию!
Marat
Январь 6, 2009 at 23:09
2Для моих гуманитарных мозгов, что-то сложновато. Три раза перечитал, понял на половину. Точнее не понял ваши таблицы.
Возникли вопросы:
1. Получается продвигается сайт С?
2. Почему сайт F вообще не задействован?
3. У вас пример с 6 сайтами, есть пример перелинковки от 30 сайтов?
Devaka
Январь 7, 2009 at 00:14
3Смысл был в том, чтобы показать, что такое ссылочный граф, для чего он нужен и как используется. На картинке всего-лишь пример, вы можете придумать любой другой сами. Про продвижение какого-либо из сайтов речь не идет, также не идет речь о перелинковке.
xo4uuu
Январь 9, 2009 at 14:10
4Для чего применяется ссылочныйграф? Возможно ли предсказывать с определенной степенью точности значение ПР?
plaintext
Январь 16, 2009 at 20:20
5Наврят ли про графы можно дисертацию написать)
используются они везде для визуализации взаимосвязей.
А что касается ПМ, кто их знает как и в каком виде хранятся данные у них ))
Единственное, что интересно – моделирование естественных связей, например при поднятии сети своих саттелитов.
Вообщем как всегда борьба алгоритомов =))
ярослав
Сентябрь 2, 2009 at 09:18
6Спасибо, наконец-то встретил нормальное научное объяснение того, как поисковые системы обсчитывают свои параметры
Александр
Октябрь 5, 2011 at 15:01
7Интересно как ПС хранят матрицы смежности таких размеров.
Ответить