Параллельное моделирование динамики процессов на комплексных сетях

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

Мы умеем генерировать сети, состоящие из миллиардов вершин, одновременно с моделированием распространения процесса на создаваемой сети. В качестве сетевой генеративной модели используются пуассоновские стохастические графы Кронекера, позволяющие воссоздать сеть с требуемым распределением степеней вершин по инициирующей матрице. Моделирование динамики SIRS1-подобного процесса осуществляется при задании доли изначально активированных узлов и вероятности активации соседей за итерацию. Обмен сообщениями о необходимости активации вершин между разными частями сети выполняется в конце каждой итерации с явным выделением мастер-процессов для маршрутизации сообщений. Для эффективного использования вычислительных ресурсов разработан алгоритм балансировки нагрузки с учётом структуры инициирующей матрицы.

В качестве иллюстрации приведен пример моделирования распространения процесса по сети для инициирующей матрицы, оцененной по графу Барабаши-Альберта, при выделении одного узла для маршрутизации сообщений.

1Susceptible – Infected – Removed (Recovered) – Susceptible – обобщенная эпидемиологическая модель, описывающая жизненный цикл индивида при распространении инфекционного заболевания как переход между состояниями «восприимчивый» – «инфицированный» – «удаленный»(«излеченный») – «восприимчивый».

Публикации по теме:

Иванов С.В., Колыхматов И.И., Бухановский А.В. Параллельные алгоритмы моделирования комплексных сетей // Известия высших учебных заведений. Приборостроение. — 2008. — № 51(10) — С 5-12.