Моделирование информационного противоборства в социальных сетях…
7
Алгоритм 1 .
Алгоритм поиска оптимального плана мониторинга
с двумя оракулами.
Вход:
G
Выход:
смешанные стратегии защитника и атакующего
1. Инициализируем M произвольной стратегией (распределением
ресурсов) защитника.
2. Инициализируем S произвольной статегией атакующего.
repeat
m,s CoreLP M,S
DO S
M M
AO M
S S
until
условие сходимости
Условие сходимости выполняется, когда ни один из ораку-
лов DO и AO не может вычислить чистую стратегию, которая была
бы лучше, чем лучшая смешанная стратегия соответствующего игро-
ка при фиксированной текущей лучше стратегии противника.
В качестве подпрограммы CoreLP может использоваться любой
метод решения задачи линейного программирования, например, сим-
плекс-метод. В [27] доказана корректность алгоритма двух оракулов.
Алгоритм поиска чистых стратегий.
Чистые стратегии пред-
ставляют из себя множества вершин либо для атаки, либо для мони-
торинга. Задача поиска этих множеств может быть сведена к задаче о
вершинном покрытии (SCP или VСP), которая является NP-полной,
следовательно необходим эффективный приближенный алгоритм ее
решения. На практике применяются варианты жадного алгоритма
(CELF, LDAG, SimPath). В данной работе предлагается новый под-
ход, основанный на иерархическом представлении графа. Пример та-
кого представления показан на рис. 3. Подход позволяет, во-первых,
существенно ускорить жадный алгоритм, во-вторых, гибко выбирать
компромисс между точностью и скоростью вычислений. Вычисли-
тельные эксперименты показывают, что при потере точности около
1%, алгоритм быстрее CELF в десятки раз.
Алгоритм построения иерархического представления показан в
листинге 2. Основная идея заключается в решении задачи SCP для
графа и создании из полученного решения нового графа, который
служит новым слоем в представлении. Данный процесс продолжает-
