УДК 004.9 Сигов А.С., Обухова А.Г., Алёшкин А.С., Жуков Д.О. Московский технологический университет (МИРЭА), г. Москва, Россия МОДЕЛИРОВАНИЕ ПРОЦЕССОВ ГРУППОВОГО ПОВЕДЕНИЯ И ВЫБОРА С ПОМОЩЬЮ СТОХАСТИЧЕСКОГО КЛЕТОЧНОГО АВТОМАТА С ПАМЯТЬЮ С УЧЕТОМ И БЕЗ УЧЕТА ВНЕШНЕГО ВОЗДЕЙСТВИЯ Аннотация В данной статье рассматривается созданная авторами модель стохастических клеточных автоматов с памятью. После проведенного анализа модели становится понятно, что динамика изменения состояний в системах такого типа имеет очень сложный и неочевидный характер. Это направление требует дальнейшего изучения. Объекты данного типа можно отнести к новому классу клеточных автоматов. Среда, в которой моделируются связи между ячейками клеточного автомата на дифференцируемых шагах процесса перехода, рассматривается, как имеющая случайную структуру, учет памяти в поведении ячеек описывается наборами изменяющихся правил. Для проведения исследования разработанной модели были разработаны алгоритмы и программное обеспечение. Имитационное моделирование показало, что разработанная модель клеточных автоматов с памятью подходит для описания группового поведения в социальных системах. В эту категорию входит групповой выбор во время электоральных кампаний. Ключевые слова Случайная сеть; клеточный автомат; реализация памяти. Sigov A.S., Obukhova A.G., Alyoshkin A.S., Zhukov D.O. Moscow Technological University (MIREA), Moscow, Russia MATHEMATICAL SOLUTIONS OF SOFTWARE FOR PREDICTING GROUP BEHAVIOR IN A SOCIAL SYSTEM BASED ON STOCHASTIC CELLULAR AUTOMATA WITH MEMORY Abstract In provided article are considered the model of stochastic cellular automata with memory. After analysis of the model, it becomes clear that the dynamics of state changes in systems of this type is very complex and non-obvious. This direction requires further study. Objects of this type can be attributed to a new class of cellular automata. The environment in which the connections between cells of the cellular automaton was modeled in differentiated steps of the transition process is considered as having a random structure, the memory accounting in the behavior of cells describes by sets of changing rules. To conduct research on the developed model, were developed algorithms and software were developed. Simulation modeling showed that the developed model of cellular automata with memory is suitable for describing group behavior in social systems. This category includes group selection during electoral campaigns. Keywords Random network; cellular automaton; memory implementation. Введение Задача разработки моделей выбора групповых процессов поведения и направления действий в социальных и экономических системах интересна и занимает важную роль. Групповые процессы взаимодействия в социальных и экономических отношениях играют очень важную роль. Сети знаний компаний, логистика поставок товаров, процессы передачи информации, политические выборы, выражение поведения и взглядов в социальных сетях пользователями и так далее. Групповые процессы взаимодействия можно определить как совокупность информационных каналов (связи сети или ребра в графе) каждого человека (узлы сети или вершины графа), связывающих его с 175 другими членами сообщества, а также средств массовой информации (то есть, не только взаимодействие между членами определенной группы в социальной сети). Средства массовой информации (радио, телевидение, интернет ресурсы, социальные сети и т.д.) а также книги, газеты, журналы оказывают существенное влияние на состояние отдельных узлов социальной сети (выбор предпочтений и поведенческие реакции людей), которое может меняться с течением времени, как за счет информационной среды, так и взаимодействия пользователей между собой. В связи с этим возникает ряд вопросов. Во-первых, как может происходить изменение в системе доли узлов, находящихся в том или ином состоянии. Во-вторых, как эти узлы связываются между собой в подгруппы (кластеризация сети). В-третьих, как информационные процессы зависят от всей сети в целом для различных состояний узлов и как они развиваются во времени. За последние десять лет интерес исследователей к моделированию явлений, происходящих в экономических и социальных системах, значительно вырос. В связи с этим, очень трудно указать явных лидеров в данной области знаний. Для описания подобных явлений все чаще применяются различные модели на основе поведения машин клеточных автоматов, которые в общем случае можно представить, как набор взаимодействующих ячеек, состояния которых и переходы между которыми определяются наборами правил взаимодействия. Краткий обзор применения моделей клеточных автоматов для описания процессов в социальных и экономических системах J. Hay и D. Flynn изучали влияние структуры сетей (случайные структуры, маленькие миры, цикл, колесо, звезда, иерархическая), в которых функционируют клеточные автоматы и правил их поведения на динамику процессов в социальных сетях, результаты исследования описаны в работе [1]. Было показано, что при одинаковых правилах взаимодействия клеток динамика процессов сильно зависит от топологии сети (неупорядоченные структуры оказывают тормозящее влияние и наибольшая скорость наблюдается в регулярных структурах). В работе [2] авторов J. Hay (из DepartmentofChemicalandBiochemicalEngineering, WesternUniversity, London, ON, Canada) и D. Flynn (King’sUniversityCollege, London, ON, Canada) теория клеточных автоматов была применена к описанию процессов в социальных системах. Согласно их теории поведение социальной системы зависит от свойств внешней среды и структуры поведения, которая может быть описана с помощью четырех параметров в поведении: разнообразие, связность, взаимозависимость, и адаптируемость. В этой статье было показано, что поведение становится более упорядоченным и целенаправленным при увеличении взаимозависимости и адаптивности. В работе [3] на основе модели клеточных автоматов были проанализированы процессы, происходящие на фондовом рынке с учетом правил транзакций, принятых в Китае. J. Ding, Q. Li (CollegeofComputerSci. andEng., ShanghaiUniversity, Shanghai, China) и Z. Li (DerivativesDepartment, DonghaiSecuritiesLtd, Shanghai, China) на основе как технического анализа, так и стадного поведения описали правила переходов между состояниями клеточных автоматов и исследовали макроскопическую динамику рынка. Моделирование взаимодействия между клиентами и поставщиками услуг с помощью сотовой модели клеточных автоматов было осуществлено в работе [4]. R.A. Zimbres (UniversidadePresbiterianaMackenzie, CentrodeCiênciasSociais e Aplicadas, SaoPaulo, Brazil) и P.P.B. deOliveira (UniversidadePresbiterianaMackenzie, FaculdadedeComputação e Informática, SaoPaulo, Brazil) на основе интервью с клиентами и поставщиками услуг с интервалом времени в четыре месяца было проведено шесть исследований качества обслуживания, на основе которых были установлены правила переходов между состояниями клеточных автоматов. Модель клеточных автоматов достигает точности 73,80%, что существенно выше, чем дает модель линейной регрессии качества обслуживания. Моделирование позволило авторам понять, какие виды поведения, принятые поставщиками и клиентами, создают улучшенное восприятие качества услуг. Эволюционная динамика социальных сетей с использованием моделей клеточных автоматов для исследования статистических характеристик процессов кластеризации (разделение на плохо связанные группы), например, таких как степень разделения, была исследована в работе [5]. J. Li и Z. Chen (CollegeofScience, BeijingForestryUniversity, Beijing, China) и T. Qin (SchoolofEconomicsandManagement, BeijingForestryUniversity, Beijing, China) рассмотрели три вида факторов в поведении, названных ими себялюбие, взаимность, и альтруизм, которые необходимы для построения социальной сети и анализа их влияния на её рост. Результаты моделирования показали, что принцип взаимности и альтруизм способствовать росту числа объединенных узлов в социальной сети, а эгоизм тормозит рост. Исследователи A. Wang, J. Chen (College of Computer Science and Technology, Taiyuan University of Technology, Taiyuan, Shanxi, China) и W. Wu (Department of Computer Science, University of Texas at Dallas, Richardson, TX, United States) построили сотовую модель клеточных автоматов для распространения слухов в социальных сетях [6]. Экспериментальное моделирование проводилось при периодических граничных ограничениях в процессе распространения слухов. Результат показал, что модель клеточных 176 автоматов способна охарактеризовать реально наблюдаемое поведение распространения слухов в социальной сети. На основании полученных результатов о влиянии граничных условий на распространение слухов авторы работы предложили эффективную стратегию иммунизации сети для их подавления. Стохастические и перколяционные модели процессов, протекающих в социальных системах были рассмотрены в работах [7-10], а кинетические модели в статье [11]. Заметим, что рассмотренные модели не могут считаться полностью решающими вопрос описания динамики социальных и экономических процессов. На основании этого можно прийти к выводу, что необходимо разработать новые модели описания процессов распространения информации в сетях социальных связей, которые будут основаны на базе междисциплинарного подхода. Предлагается рассмотреть модель стохастических клеточных автоматов с памятью. Среда, в которой моделируется связь между ячейками клеточных автоматов, может рассматриваться, как имеющая случайную структуру, учет памяти в поведении ячеек может описываться изменяющимся набором правил, в данном случае. Построение модели стохастического клеточного автомата с памятью Клеточный автомат является дискретной динамической системой. Каждый элемент автомата находится в регулярной пространственной сетке, клетке, и может находиться в одном из конечных состояний, возможных у клетки. Состояния клеток изменяются в соответствии с локальным правилом, то есть состояние ячейки в данный момент времени зависит от состояния одной и той же ячейки, и состояния соседних ячеек в предыдущий момент. Состояния всех клеток обновляются одновременно в синхронном режиме. Клеточные автоматы можно рассматривать как абстрактные динамические системы, которые играют роль в дискретной математике, сравнимой с частными производными дифференциальными уравнениями в непрерывных математиках. Клеточным автоматом, обладающим памятью, называют автомат, если его ячейки помнят о своих более ранних состояниях. Если выбор будущего состояния (правило перехода) 𝑥𝑖 (𝑡 + (ℎ + 1)) в момент времени (t+(h+1)) определяется состоянием 𝑥𝑖 (𝑡 + ℎ) в момент времени (t+h), состоянием соседей ∑𝑖 /∈𝐺(𝑖) 𝑥𝑖 / (𝑡 + ℎ) в этот момент времени и своим более ранним состоянием в момент времени (t+h-1), то ячейка “помнит один шаг назад”: 𝑥𝑖 (𝑡 + (ℎ + 1)) = 𝐹{𝑥𝑖 (𝑡 + ℎ), 𝑥𝑖 (𝑡 + (ℎ − 1)), ∑𝑖 /∈𝐺(𝑖) 𝑥𝑖 / (𝑡 + ℎ)}. Более сложный характер перехода будет наблюдаться в случае зависимости функции величины группы соседей от времени G(i, t), характер перехода будет иметь следующий вид: 𝑥𝑖 (𝑡 + (ℎ + 1)) = 𝐹{𝑥𝑖 (𝑡 + ℎ), ∑𝑖 /∈𝐺(𝑖,𝑡+ℎ) 𝑥𝑖 / (𝑡 + ℎ)}. Модель усложняется, если к возможности изменения величины группы соседей добавить реализацию частичной памяти: 𝑥𝑖 (𝑡 + (ℎ + 1)) = 𝐹{𝑥𝑖 (𝑡 + ℎ), 𝑥𝑖 (𝑡 + (ℎ − 1)), ∑𝑖 /∈𝐺(𝑖,𝑡+ℎ) 𝑥𝑖 / (𝑡 + ℎ)}. Правила перехода, определяемые состояниями 𝑥𝑖 (𝑡 + ℎ), 𝑥𝑖 (𝑡 + (ℎ − 1)) и ∑𝑖 /∈𝐺(𝑖) 𝑥𝑖 / (𝑡 + ℎ), также могут иметь зависимость от шага h, это может усложнить модель поведения клеточного автомата. Число возможных различных состояний (M) клеточного автомата в данных случаях будет значительно больше, чем для детерминированных клеточных автоматов с конечным числом состояний. В случае стохастического поведения, при случайном характере переходов вместо функции F, заданной набором правил, следует ввести функцию 𝑊{𝑥𝑖 (𝑡 + (ℎ + 1))| 𝑥𝑖 (𝑡 + ℎ), ∑𝑖 /∈𝐺(𝑖) 𝑥𝑖 / (𝑡 + ℎ)}, которая задаёт набор вероятностей переходов. Функция W отвечает за вероятность перехода i элемента на шаге (t+(h+1)) из состояния 𝑥𝑖 (𝑡 + ℎ) на предыдущем шаге (t+h) в состояние 𝑥𝑖 (𝑡 + (ℎ + 1)), при условии, что состояние ближайших соседей∑𝑖 /∈𝐺(𝑖) 𝑥𝑖 / (𝑡 + ℎ). Начальное число ячеек каждого типа, каждому из которых могут быть поставлены в соответствие определенные свойства, задается перед запуском клеточного автомата в момент времени t=0. Необходимо учесть, что ячейки клеточного автомата в социальных и экономических системах будут обладать памятью в течение некоторого времени. Стохастичность клеточного автомата в модели определяется структурой среды его функционирования. В рассматриваемой модели на каждом шаге процесса ячейки автомата случайно перестраивают сеть связей с другими ячейками. На каждом шаге между узлами в системе устанавливается новая сеть случайных связей, минимальное и максимальное число связей выбирается из заданного диапазона. Это и делает сеть стохастической на каждом шаге процесса моделирования. Соответственно, можно моделировать процесс взаимодействия между различных клеток, допустим, избирателей во время предвыборных кампаний. Избиратели предпочитаютразличных кандидатов и на каждом шаге процесса могут влиять друг на друга. В течение некоторого периода времени они убеждают друг друга голосовать 177 за того или иного кандидата, это может привести к изменению взглядов. В усложненных случаях, с усложнением характера, например, при наличии множества различных кандидатов или партий, в первичный момент времени задается отношение клеток определенного типа (для краткости описания присвоим им цветовые значения: красный, оранжевый, желтый, зеленый, голубой, синий, фиолетовый). Следующим шагом является задание правил перехода между состояниями, что учитывается в памяти. Один из вариантов – в момент времени t=0 узлу каждого типа или цвета присваивается числовой параметр, это устанавливает число шагов, в течение которого он будет сохранять свой тип (цвет). Сохранение памяти о состоянии для каждой ячейки в течение некоторого числа шагов может быть задано в виде целого положительного числа при запуске клеточного автомата, либо математической функцией распределения. Память может быть свойством типа ячеек или непосредственно выбранного узла, т.е., не завися от его типа. Также память можно задать с помощью вероятностей. Учитывая статистические свойства большинства социальных процессов, можно предположить, что распределение ячеек клеточного автомата по глубине памяти (при описании социальных процессов) может иметь близкий вид к нормальному распределению. Глубина памяти может принимать дискретные значения в диапазоне множества от 1 до заданного в модели значения N, то соответственно для нормированной вероятности того, что данная ячейка обладает памятью, 𝑥𝑖 можно записать следующим образом: 𝑝(𝑥, 𝑎, 𝜎) = (𝑥 −𝑎)2 (𝑥 −𝑎)2 𝑥𝑖=1 exp [− 2𝜎 2 ] , a и σ –константы модели ( 𝜎 > 0 ), общие для всех ячеек, если ] / ∑𝑁 𝑖 𝑖 exp [− 2𝜎 2 рассматривать память как свойство узла. Если память является свойством “цвета”, то константы задаются для каждого “цвета”. На каждом шаге процесса строится новая сеть случайных связей между узлами в системе, при этом минимальное и максимальное число связей каждого узла выбирается из некоторого, в том числе и заранее заданного, диапазона моделирования. Это обуславливает построение стохастической сети на каждом шаге процесса. Правила переходов, учитывающие память в системе, могут иметь различный вид, например, для узла любого из типов (цветов) считаем на протяжении определенного заданного числа шагов (глубина памяти) суммарное число узлов разного типа с которыми он был связан на этих шагах. Спустя число шагов, равное глубине памяти происходит его переход в тот тип, который имел максимальное значение своей суммы (такой тип перехода можно условно назвать: “цвет победитель” – забирает всё). Поясним это правило примером. Пусть красный узел (ячейка) на протяжении 4–х шагов суммарно был связан с 3–мя оранжевыми, 6–тью желтыми, 2–мя зелеными, 10–тью голубыми, 1–им синим, 12 – фиолетовыми и 10 – красными (свой собственный тип тоже учитывается). В данном примере произойдет переход в тип узла “фиолетовый”. Если бы связей с “красными” узлами было больше всех остальных, то он остался бы в своем собственном типе. Если будет более одного максимальных значений сумм связей для двух или более типов, то переход будет происходить в ближайший по спектру цвет, например. Заметим, что для каждого из типов узлов можно задавать свою глубину памяти. Более жесткое условие перехода между состояниями будет, если, например, переход происходит в случае, когда максимальное значение суммы должно отличаться от ближайшего меньшего значения на определенный заданный процент. При этом переходы между состояниями должны происходить за большее число шагов, что кинетика процесса сделает более протяженной во времени. Изучение влияния этого процента различий – интересная кинетическая задача. Так же есть тип, в котором переходы между состояниями (цветами) узлов описываются вероятностной моделью. Функция 𝜓𝑖 (ℎ, 𝑗) – вероятность перехода конкретной ячейки i – “цвета” в j “цвета”, на шаге h: ∑ℎ 𝑦𝑖,𝑗(𝑙) 𝜓𝑖 (ℎ, 𝑗) = ∑𝑙=1 ℎ , где 𝑦𝑖 (𝑙) – общее число связей рассматриваемой ячейки i – “цвета” с ячейками 𝑙=1 𝑦𝑖 (𝑙) абсолютно всех цветов (в том числе сам себя) на шаге l; ∑ℎ𝑙=1 𝑦𝑖 (𝑙) – сумма всех связей рассматриваемой ячейки i – “цвета” с ячейками всех цветов (так же и собственный) за все шаги h (h – глубина памяти данной ячейки); 𝑦𝑖,𝑗 (𝑙) – количество связей рассматриваемой ячейки i – “цвета” с ячейками, у которых цвет j на шаге l; ∑ℎ𝑙=1 𝑦𝑖,𝑗 (𝑙) – сумма всех связей данной ячейки i – “цвета” с ячейками цвета j во время всех шагов h (h – глубина памяти рассматриваемой ячейки). ∑𝑖 𝜓𝑖 (ℎ, 𝑗) = 1 . Есть 2 варианта развития событий послеперехода, первый – ячейка забывает все предыдущие взаимодействия, второй – не забывает. Для каждого шага можно задать с помощью матрицы вероятностей переходов действие внешних факторов на изменения типов узлов, так же можно предусмотреть и механизм целенаправленного изменения доли узлов определённого типа. Матрица вероятностей переходов (между состояниями ячеек клеточного автомата) может описывать воздействие внешних случайных факторовна переход, а не взаимодействие между самими ячейками. В более сложном случае можно генерировать матрицу переходов на каждом шаге, для каждого состояния. Для этого можно использовать следующий подход. Обозначим через N число состояний 178 (“цветов") ячеек. Вероятность перехода на текущем шаге из данного состояния в любое другое 𝑃𝑖 (ℎ, 𝑗) определим как: 1 𝑃𝑖 (ℎ, 𝑗) = (ℎ) 𝑓(𝑖, 𝑗), 𝑁𝑗 где 𝑁𝑗 (ℎ) – возможное число “цветов" (состояний), на шаге перехода h; 𝑓(𝑖, 𝑗) – нормированная функция, определяющая вероятность перехода (от 0 до 1) из рассматриваемого состояния i (“цвета") в любое другое состояние j на шаге h. Вероятность остаться в исходном состоянии определим следующим образом: 1 𝑗 𝑃𝑗 (ℎ, 𝑗) = 1 − 𝑁 (ℎ) ∑𝑖=1,𝑖≠𝑗 𝑓(𝑖, 𝑗). 𝑗 Пусть, на шаге h=3 в системе имеется 𝑁𝑗 (ℎ) = 4 отличных (по числу ячеек) от нуля состояний “красное", “оранжевое", “синие" и “зеленое". Соответственно переход, например, “красного" в “синее" будет определяться следующим образом: 1 𝑃𝑖="красное" (ℎ = 3, 𝑗 = "синие") = 4 𝑓(𝑖 = "красное", 𝑗 = "синие"). Аналогичным образом определяются вероятности переходов из “красного" в “оранжевое" и “красного" в “зеленое". Тогда, вероятность остаться в состоянии “красное" будет равна единица минус сумма переходов в другие состояния. Функции вероятности 𝑓(𝑖, 𝑗) принимают случайные значения от 0 до 1 и выбираются исходя из методологии описания процессов, с учетом конкретной ситуации и представлений о свойствах системы. В качестве примера рассмотрим распределениеПуассона. Функция вероятности в данном случае будет 𝑥𝑘 иметь вид 𝑓(𝑖, 𝑗) = 𝑝(𝑘, 𝑥𝑖→𝑗 ) = 𝐶 𝑒 −𝑥 , где k=0,1,2,…; 𝑥𝑖→𝑗 > 0 , C – нормировка. Величина 𝑥𝑖→𝑗 𝑘! определяется величиной перехода между i и j “цветами” (состояниями). Будем считать, что все состояния или цвета могут быть пронумерованы целыми положительными числами от 0 до R, а расстояние между 𝑘 𝑗 𝑁 (ℎ) |𝑅𝑗 −𝑅𝑖 | близлежащими состояниями равно 1. Тогда 𝑥𝑖→𝑗 = |𝑅𝑗 − 𝑅𝑖 | , 𝐶 = 1/ ∑𝑗=1 𝑒 −|𝑅𝑗−𝑅𝑖| для данного 𝑘! 𝑘 |𝑅𝑗 −𝑅𝑖 | −|𝑅 −𝑅 | 𝑒 𝑗 𝑖 заданного числа k. В общем виде 𝑓(𝑖, 𝑗) = 𝑘! 𝑘 . 𝑁 (ℎ)|𝑅𝑗 −𝑅𝑖| −|𝑅 −𝑅 | ∑ 𝑗 𝑒 𝑗 𝑖 𝑗=1 𝑘! Имеют место быть несколько сценариев учета влияния внешних факторов и взаимодействия ячеек между собой: - учитывается матрица переходов между состояниями, глубина памяти ячеек определенного типа не запоминается; - учитывается заданная глубина памяти ячеек клеточного автомата, учитывается матрица переходов. В последнем случае встает вопрос выбора приоритетности действий и выбирается для каждой системы самостоятельно. Следует упомянуть случайный порядок изменения принадлежности узла – узел может тяготеть к особому ему цвету или состоянию. Наиболее существенное применение теории клеточных автоматов – проведение моделирования поведения и самоорганизации. Модель стохастического клеточного автомата идеально подходит для описания групповых процессов взаимного влияния в группе, например, для моделирования поведения людей в социальных сетях или отслеживания и прогнозирования реакций во время предвыборных кампаний. Стоит вниманияразбор процесса «забывания» информации. Продолжая описанный выше пример, можно обратить внимание на сам шаг перехода. Будет ли в момент перехода узел отбрасывать предыдущий накопленный опыт, то есть забывать взаимодействия, случавшиеся ранее, до момента перехода, или же память сохраняется и предыдущие взаимодействия влияют на узел на каждом шаге? Отдельного моделирования заслуживает случайный порядок изменения принадлежности узла. В данном случае, даже с учетом накопленного опыта связанности узла, он может тяготеть к тому или иному «цвету». Существует разделение свойств отдельных ячеек на моменте их создания во время запуска автомата и приобретенных в процессе моделирования поведения. К примеру, для начала моделирования поведения мы задали значения емкость памяти, число шагов взаимодействий, которые помнит узел, для красных «5», а для синих «8». В процессе моделирования часть узлов изменяет свою принадлежность и переходит из состояния «красный» в состояние «синий» и наоборот. Это означает что появятся «синие» узлы с емкостью памяти «5» и красные узлы с емкостью памяти «8». Моделирование групповых процессов. Стохастические клеточные автоматы с памятью, без учета внешнего воздействия Для проведения моделирования групповых процессов влияния внутри группы с помощью 179 стохастического клеточного автомата, был принят ряд допущений: продолжительность шага принята равной одной условной единице (день, неделя, месяц); в течение одного шага каждая ячейка клеточного автомата может иметь заданное в некотором диапазоне случайной число связей, то есть контакт, во время которого ячейки могут влиять друг на друга; для каждого типа ячеек задается глубина памяти, определяющая правило перехода; при моделировании можно рассматривать различные сценарии поведения при переходе между состояниями клеточного автомата. С помощью созданного нами ранее программного обеспечения было проведено моделирование поведения стохастических клеточных автоматов с различными наборами параметров, результаты которых были экспортированы и обработаны в Excel (полученные результаты представлены в таблицах 1 – 2 (см. рис. 1 и 2). Моделирование показывает, что динамика изменения состояния имеет достаточно сложный вид. В таблице 1 (на рисунках 1а – 1г) представлены результаты моделирования системы при различном среднем числе связей, состоящей из одинакового числа ячеек трех типов: “красные” – 333 штуки с глубиной памяти 4 шага; “синие”– 333 штуки с глубиной памяти 5 шагов; “голубые”– 333 штуки с глубиной памяти 3 шага. Таблица 1. Моделирование поведения стохастического клеточного автомата при одинаковом числе ячеек, разной глубине памяти и со сценариями сохранения памяти о предыдущих взаимодействиях после изменения состояния После перехода в другое состояние (“цвет”), ячейки После перехода в другое состояние (“цвет”), сохраняют информацию о взаимодействиях на ячейки не сохраняют информацию о предыдущих шагах. взаимодействиях на предыдущих шагах. Рис. 1 а. Число связей ячейки на одном шаге от 2- х до 4 -х Рис. 1 в. Число связей ячейки на одном шаге от 2- х до (среднее 3) 4 -х (среднее 3) Рис. 1б. Число связей ячейки на одном шаге от 5 до 10 Рис. 1г. Число связей ячейки на одном шаге от 5 до 10 (среднее 7,5) (среднее 7,5) Полученные результаты показывают, что независимо от того, была ли сохранена или не сохранена 180 память о состояниях на предыдущих шагах, после изменения “цвета”, то есть состояния ячейки, увеличение среднего числа связей клеток автомата приводит к тому, что его стационарное состояние достигается за меньшее число шагов. Забывание информации о состояниях клетки на предыдущих шагах после перехода в новое состояние, приводит к тому, что стационарное состояние клеточного автомата достигается за большее число шагов. Результаты можно наглядно наблюдать, попарно сравнивая рисунки 3а и 3в, а также 3б и 3г.Однако при увеличении среднего числа связей от 3 до 7,5 достижение стационарного состояния замедляется, что говорит о нелинейном характере влияния среднего числа связей на скорость изменения числа различных состояний клеточного автомата. Так же интересной задачей исследования поведения стохастического клеточного автомата является изучение влияния соотношения ячеек различного типа на характер наблюдаемых процессов. Ячейки клеточного автомата, обладающие большей глубиной памяти, могут в определенный момент времени становиться доминирующими, однако доминирование ячеек определенного типа зависит не только от глубины памяти, но и от их первоначального соотношения. В таблице 2 представлены результаты моделирования поведения стохастического клеточного автомата при различном числе связей одной ячейки и сценариях сохранения памяти о предыдущих взаимодействиях после изменения состояния при одинаковом среднем числе связей от3 до 10, различном соотношении числа ячеек двух типов: “красные” и “голубые”, при различных соотношениях глубины памяти. Таблица 2. Моделирование поведения стохастического клеточного автомата, состоящего из ячеек двух типов при их различном числе, разным соотношением глубины памяти и сценариями её сохранения после изменения состояния ячейки После перехода в другое состояние (“цвет”), После перехода в другое состояние (“цвет”), ячейки сохраняют информацию о ячейки не сохраняют информацию о взаимодействиях на предыдущих шагах. взаимодействиях на предыдущих шагах. Рис. 2а. Число ячеек “красные” – 450 (память 4 шага); Рис. 2в. Число ячеек “красные” – 440 (память 4 шага); “голубые” – 550 (память 3 шага). “голубые” – 560 (память 3 шага). Рис. 2б. Число ячеек “красные” – 440 (память 4 шага); Рис. 2г. Число ячеек “красные” – 430 (память 4 шага); “голубые” – 560 (память 3 шага). “голубые” – 570 (память 3 шага). 181 Результаты проведенного моделирования показывают, что в зависимости от соотношения числа “красных” и “голубых” ячеек, но независимо от сценария перехода, то есть с сохранением или без сохранения памяти о состояниях на предыдущих шагах, после изменения “цвета” (состояния ячейки), существует точка инверсии, выше значения которой начинают “побеждать ячейки с меньшей глубиной памяти (попарно сравнить рисунки 2а и 2б, а также 2в и 2г). Чем больше различие между глубиной памяти, тем выше значение величины точки инверсии. При глубине памяти “красных” ячеек 4 шага, а “голубых” – 3 шага, точка инверсии составляет примерно 0,445, это при сохранении памяти о состояниях на предыдущих шагах, после изменения “цвета” и 0,435, если память о состояниях на предыдущих шагах, после изменения “цвета” не сохраняется. При глубине памяти “красных” ячеек 6 шагов, а “голубых” – 3 шага, точка инверсии составляет примерно 0,375, при сохранении памяти о состояниях на предыдущих шагах, после изменения “цвета” и 0,385, если память о состояниях на предыдущих шагах, после изменения “цвета” не сохраняется. Моделирование групповых процессов выбора. Стохастические клеточные автоматы с памятью с учетом внешнего воздействия Помимо описания свойств памяти и стохастичности рассматриваемого класса клеточных автоматов нужно рассмотреть моделирование случайного действия внешних факторов, влияющих для каждого шага процесса на переход между различными по своим свойствам типами ячеек. Для этого нужно задать матрицу вероятностей переходов, которая может описывать воздействие на переход внешних случайных факторов (например, влияние масс-медиа). Возможно несколько сценариев учета этого влияния. Первый сценарий: учитывается только матрица переходов между состояниями без учета глубины памяти ячеек определенного типа. Второй сценарий: учитывается матрица переходов и заданная глубина памяти ячеек клеточного автомата. На рисунке 3 представлены результаты моделирования переходов клеточного автомата с учетом лишь внешних воздействий, то есть без учета взаимодействия ячеек, описываемых матрицей вероятностей 1. Среднее число связей одной ячейки клеточного автомата в данном случае не имеет значения. Число “красных” ячеек автомата – 540 штук; “синих”– 340 штуки; “голубых”– 120 штук. Матрица 1. Величины вероятностей переходов за один шаг при действии случайных внешних факторов Красный Синий Голубой Красный 0,783 0,072 0,145 Синий 0,035 0,825 0,140 Голубой 0,200 0,270 0,530 Из данных на рисунке 3 можно понять, что отсутствие взаимодействия ячеек клеточного автомата приводит к “гладкой” кинетике изменения состояний, с релаксацией к равновесным состояниям (“красное” – около 300; “синее” – около 480; “голубое” – около 220) при наличии небольшого случайного шума. Рис. 3. Моделирование переходов клеточного автомата под влиянием только внешних факторов Наличие памяти о взаимодействиях между ячейками и её влияние на переходы было рассмотрено ранее (см. рис. 1 – 2). Не менее интересным является моделирование совместного влияния внешнего воздействия, что 182 можно задать матрицей переходов, и взаимодействия между ячейками на динамику поведения клеточного автомата. В таблице 3 (на рисунках 4а – 4г) в графическом виде представлены результаты моделирования поведения системы при различном среднем числе связей ячеек, с учетом из взаимодействия и внешнего воздействия с вероятностями переходов, указанными в матрице 1. Автомат состоит из ячеек трех типов: “красные” – 540 штук с глубиной памяти 5 шагов; “синие”– 340 штук с глубиной памяти 4 шага; “голубые”– 120 штук с глубиной памяти 3 шага. Данные на рисунке 4 показывают, что совместное влияние внешнего воздействия, которое можно задать матрицей переходов 1, и взаимодействие между ячейками, существенно усложняют динамику процессов. Если ячейки сохраняют информацию о взаимодействиях на предыдущих шагах после перехода в другое состояние (“цвет”), то ячейки, имеющие состояние, характеризующиеся как “красное”, увеличивают свое число и начинают доминировать над ячейками других типов (см. рис. 4а, 4в и 3), имеющими меньшую (“синие” – 4 шага; “голубые” 3 шага) глубину памяти, в независимости от среднего числа связей, приходящегося на одну ячейку. Хотя при этом только при учете внешнего воздействия (матрица 1) число “красных” ячеек должно было бы уменьшиться. Таблица 3. Моделирование поведения стохастического клеточного автомата, состоящего из ячеек трех типов при их различном числе, разной глубиной памяти, среднем числе связей одной ячейки и сценариях сохранения памяти о предыдущих взаимодействиях, после изменения состояния После перехода в другое состояние (“цвет”), После перехода в другое состояние (“цвет”), ячейки сохраняют информацию о ячейки не сохраняют информацию о взаимодействиях на предыдущих шагах. взаимодействиях на предыдущих шагах. Рис. 4а. Среднее число связей одной ячейки от 3–х до 7–ми Рис. 4б. Среднее число связей одной ячейки от 3–х до 7–ми Рис. 4в. Среднее число связей одной ячейки от 2–х до 4–х Рис. 4г. Среднее число связей одной ячейки от 2 – х до 4 – х Динамика процессов сильно усложняется под влиянием внешнего воздействия и взаимодействия между ячейками.Если ячейки сохраняют информацию о взаимодействиях на предыдущих шагах после перехода в другой “цвет”, то ячейки, имеющие состояние, характеризующиеся как “красное”, увеличивают 183 свое число и начинают доминировать над ячейками других типов, имеющими меньшую глубину памяти, таким образом можно допустить, что за счет поддержки группы может быть значительно уменьшена степень воздействия внешнего влияния. Если после перехода в другое состояние (“цвет”), ячейки не сохраняют информацию о взаимодействиях на предыдущих шагах (например, группа с неустойчивыми связями), то групповое воздействие остается доминирующим, снижается при взаимодействии ячеек (см. рис. 4б, 4г и 3). Заключение Анализ модели стохастических клеточных автоматов с памятью показывает, что динамика изменения состояний в таких системах имеет сложный и интересный характер, который требует дальнейшего изучения, а сами подобные объекты можно отнести к новому классу клеточных автоматов. Модель стохастических клеточных автоматов с памятью может быть применена для описания любой избирательной кампании, например, во время выборов на пост президента США Трамп-Клинтон в 2015- 2016 годах. Учитывая незначительный характер влияния среднего числа связей, приходящихся на одну ячейку, на процессы переходов при смене состояний, вызванные взаимодействием ячеек между собой, что было рассмотрено ранее, среднее число связей любой ячейки клеточного автомата на каждом шагу процесса принимается равным от 3–х до 7–ми, что примерно соответствует числу обсуждений политических тем в течение одного месяца одного рассматриваемого человеком с другими. На рисунке 5а представлены результаты опроса предпочтений избирателей, проводившегося в США на протяжении 500 дней, с 1 июля 2015 года по 7 ноября 2016 года во время президентской кампании 2016 года (данные взяты с ресурса: http://www.realclearpolitics.com/epolls/2016/president/us/general_election_trump_vs_clinton- 5491.html#polls). Во избежание путаницы следует заметить, что представленные на рисунке 5а данные относятся к разным масштабным шкалам. Данные для Клинтон и Трампа следует относить к левой шкале ординат (вертикальная шкала), а данные по неопределившимся избирателям к правой шкале ординат. Мы не будем обсуждать особенности избирательной системы США, в которой окончательное решение остается за коллегией выборщиков, а победитель в любом из штатов получает в конечном итоге голоса всех выборщиков, однако заметим, что в абсолютных цифрах Клинтон (в целом по США) набрала на несколько миллионов голосов больше, чем Трамп. Представленные на рисунке 4а данные имеют трендовую и колебательную составляющие. Для успешного анализа колебаний и определения времен изменения взглядов избирателей необходимо разделить тренд и колебания без потери существенной информации о процессе. Часто для этого используется разложение в ряд Фурье, однако, его эффективное применение ограничено в силу того, что механизм формирования колебаний представляет собой суперпозицию гармонических колебаний, в то время как реальные нелинейные процессы, по механизмам их формирования, могут не соответствовать этому условию. Несоответствие исследуемого процесса гармоническим колебаниям компенсируется в спектральном анализе увеличением числа гармонических компонент, но это еще больше затрудняет интерпретацию получаемых результатов. В результате, разложение в ряд Фурье может давать значимую систематическую ошибку из-за несоответствия методов обработки свойствам реальных данных. В данном случае использование метода почти – периодических функций является более предпочтительным, чем традиционные методы гармонического анализа, основанные на Фурье – преобразованиях, это объясняется целым рядом причин. Основная причина – наличие в социальных процессах человеческого фактора, что приводит к нечеткости, неопределенности и недетерминированности характеристик процессов. С другой стороны, наблюдаемые данные, представленные на рисунке 6а, показывают существование колебаний в предпочтении избирателей, что хорошо согласуется с идеями, заложенными в методику использования почти – периодических функций [12]. Поскольку, величина почти–периода, определяемая по данным, представленным на рис. 5а, в колебаниях настроений избирателей Трампа и неопределившихся составляла 86 дней, а для избирателей Клинтон наблюдалось два почти–периода в 50 и 86 дней, то глубину памяти избирателей Хиллари Клинтон было решено принять равным одному шагу (50 дней), а избирателей Дональда Трампа и неопределившихся – двум шагам, так как почти–период для Клинтон меньше. Соответственно, длительность одного шага – 50 дней, а всей 500-дневной избирательной кампании – 10 шагов моделирования. Матрица 2. Величины вероятностей переходов за один шаг при действии случайных внешних факторов для избирательной кампании Трамп – Клинтон Красный Синий Голубой Красный 0,765 0,035 0,200 Синий 0,072 0,768 0,160 Голубой 0,300 0,250 0,450 184 В матрице 2 представлены принятые для моделирования вероятности переходов между состояниями под действием внешних факторов на каждом шаге работы клеточного автомата. Согласно данным, полученным из рис. 5а, примем начальное число ячеек «за Хиллари Клинтон» (“красные”) равным 54% от общего количества; за Дональда Трампа 34% (“синие”); неопределившихся 12% (“голубые”). На рисунке 5б представлены результаты моделирования с указанным выше набором параметров в матрице 2 переходов между состояниями, и без сохранения ячейкой информации о взаимодействиях с другими ячейками на предыдущих шагах, после перехода в новое состояние. Рис. 5а. Предпочтения избирателей США во время Рис. 5б. Моделирование предпочтений избирателей США во президентской кампании 2016 г (Трамп, Хиллари и время президентской кампании 2016 г (Трамп, Хиллари и неопределившиеся с выбором избиратели) неопределившиеся с выбором избиратели)с помощью стохастического клеточного автомата Результаты моделирования описанного примера, учитывая масштаб рисунков 5а и 5б, показывают, что стохастические клеточные автоматы, при соответствующем подборе параметров, могут хорошо согласовываться с данными, наблюдаемыми в ходе избирательной кампании данных. Благодарности Работа выполнена при финансовой поддержке РФФИ, грант № 16-29-09458 офи_м «Разработка перколяционных топологических моделей описания виртуальных социальных систем, процессов кластеризации их участников по группам настроений, стохастической динамики распространения влияния и управления переходами». Acknowledge This paper was supported by the Russian Foundation for Basic Research (RFBR), grant No. 16-29-09458.ofi_m «Development of percolation topological models of describing virtual social systems, processes of clustering their participants by mood groups, stochastic dynamics of influence propagation and control of transitions». Литература 1. Hay, J., Flynn, D. The effect of network structure on individual behavior. Complex Systems., 2014, 23 (4), pp. 295-311. 2. Hay, J., Flynn, D. How external environment and internal structure change the behavior of discrete systems. Complex Systems., 2016, 25 (1), pp. 39-49. 3. Ding, J., Li, Q., Li, Z. Social conformity and price fluctuation in artificial stock market. Proceedings – 2008 Pacific-Asia Workshop on Computational Intelligence and Industrial Application, PACIIA 2008. 4. Zimbres, R.A., de Oliveira, P.P.B. Dynamics of Quality Perception in a Social Network: A Cellular Automaton Based Model in Aesthetics Services. Electronic Notes in Theoretical Computer Science, 2009, 252, pp. 157-180. 5. Li, J., Chen, Z., Qin, T. Document Using cellular automata to model evolutionary dynamics of social network. IET Conference Publications, 2013(644 CP), pp. 200-205. 6. Wang, A., Wu, W., Chen, J. Social network rumors spread model based on cellular automata., 2014, Proceedings – 2014 10th International Conference on Mobile Ad-Hoc and Sensor Networks, MSN 2014. 7. Lesko, S.A., Zhukov, D.O. Percolation models of information dissemination in social networks. Proceedings – 2015 IEEE International Conference on Social Computing and Networking, SocialCom 2015, DOI: 10.1109/SmartCity.2015.73 8. T. Khvatova, M. Block, D. Zhukov, S. Lesko. Studying the Structural Topology of the Knowledge Sharing Network. / 11th European Conference on Management Leadership and Governance, Military Academy, Lisbon, Portugal, 12-13 November 2015., ECMLG 2015., E Book ISBN: 978-1-91081-077-4, Book version ISBN: 978-1-91081-076-7, p. 20-27. 9. T. Khvatova, M. Block, D. Zhukov, S. Lesko. How to measure trust: the percolation model applied to intra-organizational knowledge sharing network. Journal of Knowledge Management. 2016, Vol. 20, Issue 5, pp.918 – 935. 10. Dmitry Zhukov, Tatiana Khvatova, Anastasia Zaltcman. Stochastic Dynamics of Influence Expansion in Social Networks and Managing Users’ Transitions from One State to Another. / Proceedings of the 11th European Conference on Information Systems 185 Management, ECISM 2017, The University of Genoa, Italy, 14 -15 September, 2017, pp. 322-329. 11. Zhukov D.O., Alyoshkin A.S., Obukhova A.G. Modelling to be based on Systems of Differential Kinetic Equations to Processes Gr oup Selection Voters during the Electoral Campaign of Trump-Clinton 2015 – 2016. Proceeding The 7th International Conference on Information Communication and Management ICICM’17, August 28-30, 2017, Moscow, Russian Federation, ACM ISBN 978-1-4503- 5279-6/17/08, DOI: http://dx.doi.org/10.1145/3134383.3134400 12. Б. М. Левитан. Почти – периодические функции., М., 1953 References 1. Hay, J., Flynn, D. The effect of network structure on individual behavior. Complex Systems., 2014, 23 (4), pp. 295-311. 2. Hay, J., Flynn, D. How external environment and internal structure change the behavior of discrete systems. Complex Systems., 2016, 25 (1), pp. 39-49. 3. Ding, J., Li, Q., Li, Z. Social conformity and price fluctuation in artificial stock market. Proceedings – 2008 Pacific-Asia Workshop on Computational Intelligence and Industrial Application, PACIIA 2008. 4. Zimbres, R.A., de Oliveira, P.P.B. Dynamics of Quality Perception in a Social Network: A Cellular Automaton Based Model in Aesthetics Services. Electronic Notes in Theoretical Computer Science, 2009, 252, pp. 157-180. 5. Li, J., Chen, Z., Qin, T. Document Using cellular automata to model evolutionary dynamics of social network. IET Conference Publications, 2013(644 CP), pp. 200-205. 6. Wang, A., Wu, W., Chen, J. Social network rumors spread model based on cellular automata., 2014, Proceedings – 2014 10th International Conference on Mobile Ad-Hoc and Sensor Networks, MSN 2014. 7. Lesko, S.A., Zhukov, D.O. Percolation models of information dissemination in social networks. Proceedings – 2015 IEEE International Conference on Social Computing and Networking, SocialCom 2015, DOI: 10.1109/SmartCity.2015.73 8. T. Khvatova, M. Block, D. Zhukov, S. Lesko. Studying the Structural Topology of the Knowledge Sharing Network. / 11th Europea n Conference on Management Leadership and Governance, Military Academy, Lisbon, Portugal, 12-13 November 2015., ECMLG 2015., E Book ISBN: 978-1-91081-077-4, Book version ISBN: 978-1-91081-076-7, p. 20-27. 9. T. Khvatova, M. Block, D. Zhukov, S. Lesko. How to measure trust: the percolation model applied to intra-organizational knowledge sharing network. Journal of Knowledge Management. 2016, Vol. 20, Issue 5, pp.918 – 935. 10. Dmitry Zhukov, Tatiana Khvatova, Anastasia Zaltcman. Stochastic Dynamics of Influence Expansion in Social Networks and Managing Users’ Transitions from One State to Another. / Proceedings of the 11th European Conference on Information Systems Management, ECISM 2017, The University of Genoa, Italy, 14 -15 September, 2017, pp. 322-329. 11. Zhukov D.O., Alyoshkin A.S., Obukhova A.G. Modelling to be based on Systems of Differential Kinetic Equations to Processes Group Selection Voters during the Electoral Campaign of Trump-Clinton 2015 – 2016. Proceeding The 7th International Conference on Information Communication and Management ICICM’17, August 28-30, 2017, Moscow, Russian Federation, ACM ISBN 978-1-4503- 5279-6/17/08, DOI: http://dx.doi.org/10.1145/3134383.3134400 12. B.M. Levitan, Pochtiperiodicheckiefuncthii, M., 1953. Об авторах: Сигов Александр Сергеевич, академик РАН, доктор физико-математических наук, президент, Московский технологический университет (МИРЭА), assigov@yandex.ru Обухова Анна Гуламовна, аспирант кафедры автоматизированных систем управления института комплексной безопасности и специального приборостроения, Московский технологический университет (МИРЭА), nsmych@yandex.com Алёшкин Антон Сергеевич кандидат технических наук, доцент, доцент кафедры автоматизированных систем управления института комплексной безопасности и специального приборостроения, Московский технологический университет (МИРЭА), antony@testor.ru Жуков Дмитрий Олегович доктор технических наук, профессор, заместитель по научной работе директора института комплексной безопасности и специального приборостроения, Московский технологический университет (МИРЭА), zhukovdm@yandex.ru Note on the authors: Sigov Alexander S. academician of the Russian Academy of Sciences, Doctor of Physics and Mathematics, President, Moscow Technological University (MIREA), assigov@yandex.ru Obukhova Anna G., PhD student, Moscow Technological University (MIREA), nsmych@yandex.com Aleshkin Anton S., Candidate of Science (PhD) in technology, associate professor, Moscow Technological University (MIREA), antony@testor.ru Zhukov Dmitry O., Doctor of Science in technology, professor, Moscow Technological University (MIREA), zhukovdm@yandex.ru 186