Навігація
Головна
ПОСЛУГИ
Авторизація/Реєстрація
Реклама на сайті
 
Головна arrow Інформатика arrow Моделирование сложных сетей
< Попередня   ЗМІСТ   Наступна >

Алгоритм Salsa

Алгоритм ранжирования Salsa (Stochastic Approach for Link-Structure Analysis - Стохастический Алгоритм Анализа Структуры Связей) был предложен Ш. Мораном (Sh. Moran) и Р. Лемпелем (R. Lempel) как некоторый симбиоз алгоритмов PageRank и HITS, позволяющий сократить последствия образования так называемых TKC (Tightly-Knit Community) - тесно связанных сообществ". Этот эффект заключается в наличии в выдаче посковой системы множества документов, тесно связанных между собой, тематика которых несколько отличается от информационной потребности пользователя, т.е. наблюдается эффект "сдвига" тематики (topic draft) при отображении результатов, часть из которых может отклоняться от доминирующей тематики.

Lempel R. and Moran S. The stochastic approach for link-structure analysis (SALSA) and the TKC effect. In Proc. of the 9th International WWW Conference, Amsterdam, The Netherlands, 2000. - pp. 387-401.

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

  • 1. Из произвольного узла v, пользователь случайным образом возвращается к узлу u, - случайно выбранному из множества узлов, ссылающихся на v. Выбор v делается случайно (при этом узлы v и u принадлежат сети).
  • 2. Из узла u наугад осуществляется переход к узлу w, если существует связь (u, w).

Веб-граф G (рис. 2.3.6 а) может быть преобразован в двудольный ненаправленный граф

(рис. 2.3.6 б) и определен как совокупность

где h, обозначает посредников, совокупность узлов- посредников (тех, из которых исходят ссылки), a - авторов, - совокупность узлов-авторов (тех, на которые ведут ссылки).

Salsa: конструкция двудольного графа

Рис. 2.3.6 - Salsa: конструкция двудольного графа

Необходимо отметить, что одни и те же узлы могут быть одновременно и авторами и посредниками.

Каждый неизолированный узел s е G представлен в GbPp одним или двумя узлами sh и sa. В этом двудольном графе Salsa реализует два разных случайных перехода. При каждом переходе возможно "посещение" узлов только из одной из двух долей графа GbPp .

Каждый путь длины два в GbPp представляет собой обход одной гиперсвязи (при прохождении от доли посредников к доле авторов в Gb p ), и отход вдоль гиперсвязи (при прохождении в обратном направлении). Это движение в обратном направлении напоминает танец сальса, который ассоциируется с названием данного алгоритма.

Так как посредники и авторы, относящиеся к теме t должны быть явно выражены в Gb p (доступны из многих узлов благодаря прямым ссылкам или коротким путям), предполагается что авторы из Va и посредники из Vh, относящиеся к теме t, будут наиболее часто посещаемыми при случайных "блужданиях" пользователей.

В алгоритме Salsa исследуются две различных цепи Маркова, которые ассоциируются с этими случайными блужданиями: цепь на стороне авторов GbPp (цепь авторов), и цепь на стороне посредников GbPp .

Такой подход позволяет ввести две стохастические матрицы перехода цепей Маркова, которые определяются следующим образом: строится матрица инциденций W ориентированного графа G. Обозначим как Wr матрицу, полученную делением каждого ненулевого элемента W на сумму значений соответствующей строки, а через Wc -матрицу, полученную делением каждого ненулевого элемента W на сумму элементов в соответствующем столбце. Тогда, матрица H, соответствующая посредникам будет состоять из ненулевых строк и столбцов WrWT, а матрица авторов A, соответственно, будет состоять из ненулевых строк и столбцов WjWr. В рамках алгоритма Salsa игнорируются строки и столбцы матриц A и H, которые состоят полностью из нулей, так как по определению, все узлы Gbip

имеют не менее одной связи. В результате матрицы A и H используются для вычисления рангов тем же путем, что и в алгоритме HITS.

Сходящиеся в процессе итерационного процесса вероятность перехода к узлу v как к автору, имеет очень простую форму:

а вероятность возврата к узлу u как к посреднику:

где С1 и с2 - некоторые константы, а InDegree и OutDegree - это количество исходящих и входящих ссылок, соответственно.

Р. Лемпель и С. Моран продемонстрировали, что алгоритм Salsa менее чувствителен к эффекту тесно связанных сообществ, чем HITS, но при условиях, что вручную в документах удаляются ссылки, не относящиеся к исследуемой теме. Это требование на практике ведет к большим издержкам, в результате чего авторам пока не известно случаев использования этого алгоритма ранжирования в реально работающих системах.

Многие из реальных сложных сетей являются контентными, т.е. такими, в узлах которых хранятся текстовые документы (веб-страницы, сообщения блогов, официальные документы и т.п.). Поэтому остановимся детально на методах группирования, а именно на задачах их классификации и кластеризации. Эти методы позволяют объединять различные узлы сети в категории, что существенно влияет на сокращение количества различных содержательных объектов в сетях. При дальнейшем изложении будем называть все объекты документами, а параметры объектов - терминами, что не ограничивает общность последующих выводов.

 
Якщо Ви помітили помилку в тексті позначте слово та натисніть Shift + Enter
< Попередня   ЗМІСТ   Наступна >
 
Дисципліни
Агропромисловість
Банківська справа
БЖД
Бухоблік та Аудит
Географія
Документознавство
Екологія
Економіка
Етика та Естетика
Журналістика
Інвестування
Інформатика
Історія
Культурологія
Література
Логіка
Логістика
Маркетинг
Медицина
Менеджмент
Нерухомість
Педагогіка
Політологія
Політекономія
Право
Природознавство
Психологія
Релігієзнавство
Риторика
РПС
Соціологія
Статистика
Страхова справа
Техніка
Товарознавство
Туризм
Філософія
Фінанси
Інші