|
Эта публикация цитируется в 5 научных статьях (всего в 5 статьях)
Математическое моделирование и прикладная математика
Прикладные аспекты использования алгоритмов ранжирования для ориентированных взвешенных графов (на примере графов социальных сетей)
В. В. Печенкинa, М. С. Королёвa, Л. В. Димитровb a Саратовский государственный технический университет имени Гагарина Ю.А.
b Технический университет - София
Аннотация:
Рассматриваются прикладные аспекты использования предварительного ранжирования вершин ориентированного взвешенного графа. Особое внимание уделяется широкому использованию такого приема в разработке эвристических алгоритмов дискретной оптимизации. Задача ранжирования имеет непосредственное отношение к проблеме определения центральности в социальных сетях, обработке больших массивов данных реального мира, но как показано в статье, явно или косвенно используется при разработке алгоритмов решения прикладных задач в качестве начального этапа построения решения. Приводятся примеры использования предварительного ранжирования, в которых продемонстрировано повышение эффективности решения некоторых прикладных задач, имеющих широкое применение в математических методах оптимизации. Дано описание структуры первой фазы вычислительного эксперимента, которая связана с получением тестовых наборов данных. Полученные данные представлены взвешенными графами, которые соответствуют нескольким группам социальной сети ВКонтакте с числом вершин в диапазоне от 9000 до 24 тысяч участников. Показано, что структурные характеристики полученных графов по числу компонент связности существенно различаются. Продемонстрированы некоторые характеристики центральности (распределения степенных последовательностей), которые имеют экспоненциальный характер. Основное внимание уделяется анализу трех алгоритмов построения иерархии ранжирования вершин графов, предлагаются новые подходы к вычислению рангов вершин с использованием информации об активности пользователей в социальных сетях. Проводится сравнение распределений полученных совокупностей рангов. Вводится понятие сходимости алгоритмов ранжирования вершин графов, а также обсуждаются различия их использования при рассмотрении данных большой размерности и необходимости построения решения в случае учета только локальных изменений.
Ключевые слова:
ранжирование, ориентированный граф, взвешенный граф, инкрементальный алгоритм, локальный алгоритм.
Поступила в редакцию: 21.08.2018
Образец цитирования:
В. В. Печенкин, М. С. Королёв, Л. В. Димитров, “Прикладные аспекты использования алгоритмов ранжирования для ориентированных взвешенных графов (на примере графов социальных сетей)”, Тр. СПИИРАН, 61 (2018), 94–118
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/trspy1033 https://www.mathnet.ru/rus/trspy/v61/p94
|
Статистика просмотров: |
Страница аннотации: | 159 | PDF полного текста: | 54 |
|