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