Принадлежност ISDCT SB RAS, Иркутск, Русия

синхронни

Принадлежност ISDCT SB RAS, Иркутск, Русия

  • Степан Кочемазов,
  • Александър Семенов

Фигури

Резюме

Цитат: Кочемазов С, Семенов А (2014) Използване на синхронни булеви мрежи за моделиране на няколко феномена на колективно поведение. PLoS ONE 9 (12): e115156. https://doi.org/10.1371/journal.pone.0115156

Редактор: Ларс Кадерали, Технически университет в Дрезден, Медицински факултет, Германия

Получено: 7 август 2014 г .; Прието: 19 ноември 2014 г .; Публикувано: 19 декември 2014 г.

Наличност на данни: Авторите потвърждават, че всички данни, лежащи в основата на констатациите, са напълно достъпни без ограничения. Всички релевантни данни се намират в хартията и нейните поддържащи информационни файлове.

Финансиране: Тази работа беше частично подкрепена от Сибирския клон на Руската академия на науките в рамките на проекта за интердисциплинарна интеграция № 80 "Диференциално-дискретни и интеградиференциални уравнения. Приложение към проблемите на естествените науки", Руската фондация за фундаментални изследвания (проекти № 14-07-00403 и 14-07-31172mol) и Съвета при президента на Руската федерация за държавно поддържане на водещите научни училища (проект № 5007.2014.9). Финансистите не са играли роля в дизайна на проучването, събирането и анализа на данни, решението за публикуване или подготовката на ръкописа.

Конкуриращи се интереси: Авторите са декларирали, че не съществуват конкуриращи се интереси.

Въведение

През последните години интересът към анализа на различни феномени на колективно поведение се увеличи значително. Това може да се обясни с факта, че в почти всички области на човешката дейност има процеси, включващи обмен на информация вътре в колективите. Такива процеси влияят дълбоко на бъдещото поведение на колектива и могат да доведат до положителни или отрицателни последици не само за разглеждания колектив, но и до много по-голяма социална формация. Например интензивната продажба на акции на фондовия пазар от играчи, които имат голямо влияние върху другите, може да доведе до драстичен спад на глобалните икономически индекси. Безредиците и революционните ситуации протичат по подобен начин, когато сравнително малка група подбудители активира толкова голям брой хора, че системите за държавна сигурност не са в състояние да се справят с тях.

Активното развитие на услугите за социални мрежи през по-късните години значително увеличи възможностите за манипулиране на колективно поведение. Тази теза може да бъде доказана чрез анализ на такива революционни явления като Арабска пролет, 2011–13 руски протести, Евромайдан и др. В по-голямата част от тези случаи съответните действия бяха планирани чрез социалните мрежи. Струва си да се спомене, че подобни процеси обикновено се координират от малки групи от определени активисти.

Моделирането на колективно поведение се изучава в голям брой статии. Следвайки много други автори, ние основаваме работата си на статията на М. Грановетер [1], в която са изследвани праговите модели на колективно поведение. Поведението на прага означава, че състоянието на всеки член на група (агент) се променя само когато стойността на специална функция, която е свързана с този агент, достигне някакъв праг. Най-простият пример за такова поведение е следването на решението на мнозинството. В модела на Granovetter мрежата, свързваща агентите, се определя чрез пълна графика - всеки агент взема предвид мнението на всеки друг агент. В много реални ситуации такъв подход не може да се използва. Например в реалните социални мрежи агент обикновено основава мнението си на мнението на агенти от някакъв квартал. В този случай мнението на агенти извън такова съседство не би оказало влияние върху становището на разглеждания агент. Подобни ситуации могат да се наблюдават и в генетиката: в много генни мрежи количеството на гените, които пряко влияят на всеки конкретен ген, е малко спрямо общия брой гени в мрежата.

Приликите на динамичните процеси, които могат да се наблюдават в генните мрежи и социалните мрежи, ни доведоха до идеята да въведем и анализираме модели на колективно поведение, които се основават на булеви мрежи. Апаратите на булевите мрежи се използват в математическата биология от 50 години. По-долу разглеждаме т. Нар. Синхронни булеви мрежи (SBN), въведени за пръв път от S. Kauffman в [2] с цел анализ на динамичните свойства на генните мрежи. В нашия подход ние разглеждаме колектив като SBN със специални функции, свързани с мрежовите върхове. От наша гледна точка езикът на булевите мрежи е много подходящ за обяснение на редица явления на колективно поведение. Например, равновесните състояния от [1] могат да се разглеждат като неподвижни точки на дискретна функция, посочена от съответния SBN. Друга важна характеристика на такива модели е, че за решаване на комбинаторни проблеми, които възникват по време на анализа на SBN, е възможно да се използват съвременни методи за решаване на големи системи от булеви уравнения. За тази цел в нашата статия използваме алгоритми за решаване на задача за логическа удовлетворимост (SAT).

Свързани произведения

Както вече отбелязахме, статията [1] е основната работа в областта на праговите модели на колективно поведение. В редица по-късни трудове, например [3] - [5], идеите от [1] са детайлизирани и приложени за анализ на различни социологически ситуации.

В [6] - [9] и други е показано, че различни явления на колективно поведение могат да бъдат изучавани от гледна точка на теорията на игрите. По-специално, равновесните състояния [1] в колективите могат да се разглеждат като равновесие на Неш. В този контекст бихме искали да споменем работата [7], в която съответствието и антиконформността се разглеждат от позициите на теорията на игрите.

В статията [10] се анализира влиянието на разпределението на праговете върху генезиса и развитието на няколко явления (по-специално, така наречения ефект на бандата) в мрежите с произволна структура.

Както казахме по-горе, синхронните булеви мрежи бяха въведени от S. Kauffman в [2]. В тази работа проблемите за анализ на фиксирани точки и цикли на съответните дискретни функции се считат за важни и полезни за изучаването на динамиката на реалните генни мрежи. Очевидно [11] е първият пример за приложение на комбинаторни алгоритми за търсене на цикли на дискретни функции, определени от мрежите на Кауфман. По-късно същите автори използват подхода SAT за подобни цели [12]. В [13] разгледахме проблема за търсене на фиксирани точки на дискретни функции, определени от мрежи, в които функциите на тежестта на върха приемат естествени стойности и в същото време действат като прагови функции. За да решим съответните проблеми, използвахме както подходи SAT, така и ROBDD. Също така в [13] проучихме противоположен проблем: дадени фиксирани точки на функцията, посочена от някаква мрежа, за възстановяване на структурата на мрежата.

През последните години бяха публикувани много трудове за анализ на структурата на големите мрежи и процесите, които могат да възникнат в тях. Съчинения [14] и [15] са доста пълни рецензии по съответните теми.

Модели

Синхронни булеви мрежи

Синхронната булева мрежа (SBN) се дефинира като насочена графика, в която с всеки връх е свързана обща функция, която приема стойности от в отделни моменти от време. По-нататък ще се позоваваме на такива функции като теглови функции на върха. Стойността на функция на тежестта за произволен връх в момента се изчислява въз основа на стойностите на функции на тежестта на някакъв набор от мрежови върхове в момента. В SBN стойностите на всички функции на тежестта се актуализират едновременно (синхронно). Имайте предвид, че тегловните функции могат да бъдат зададени по различни начини: чрез таблици на истината, булеви формули или предикати. Стойностите на тегловните функции на всички върхове в произволен момент могат да се разглеждат като резултат от изчисляване на стойност на дискретна функция, която приема булев вектор на дължина като вход и извежда булев вектор на дължина, където е броят на върховете в мрежата. Ние обозначаваме булев вектор, състоящ се от стойности на тегловните функции в момента, и го наричаме състояние на мрежата в момента. Ще наричаме първоначално състояние на мрежата. Ясно е, че произволен SBN с върхове има различни състояния на мрежата.

По този начин, по-формално, нека приемем, че е насочена графика с върхове, която представлява някакъв SBN. По-долу ще разгледаме само графики без цикли и без множество дъги. За удобство нека маркираме върховете с естествени числа от до. С произволен връх свързваме функция на тежестта, чиито стойности се дефинират в отделни моменти от време. Предполагаме, че при всяка функция на тежестта има някаква начална стойност. С обозначаваме такъв набор от мрежови върхове, че за всеки графиката има дъга. По същество това означава, че съдържа върхове, които пряко влияят. Наричаме още квартал на .

Оттук нататък имаме предвид множеството от всички възможни двоични думи с дължина. Правилата, които определят всяка функция на тежестта, са едни и същи във всеки момент от времето. Това означава, че общо тези функции указват векторна функция, която е дефинирана навсякъде и взема стойности от. Ние обозначаваме тази функция като и я наричаме дискретна функция, дефинирана от мрежата. Преходите между състоянията на мрежата, представени от булеви вектори от, могат да бъдат естествено илюстрирани с помощта на специални графики, наречени State Transition Graphs (STGs). Ние обозначаваме STG на мрежата като. Пример за прост SBN с 3 върха, където тегловните функции са зададени чрез булеви формули, е показан на фиг. 1.

В лявата част е показана проста мрежа на Кауфман с 3 върха. Тегловните функции са определени с булеви формули в горната дясна част на фигурата. Долната дясна част демонстрира графика за преход на състоянието (STG) за дискретна функция, посочена от тази мрежа. Съдържа един цикъл с дължина 2 и една фиксирана точка.

Както вече отбелязахме, количеството на различни състояния на произволен SBN с върхове е и правилата, според които мрежата преминава от едно състояние в друго, не зависят. Следователно, независимо от състоянието на мрежата в момента, има такива и, това. В тази ситуация наричаме последователността на преходите цикъл с дължина [2]. В някои трудове за анализ на динамичните свойства на генните мрежи циклите се наричат ​​"атрактори". Цикълът с дължина 1 се нарича фиксирана точка на функция. За мрежата на фиг. 1 е лесно да се види, че тя е фиксирана точка, докато една последователност образува цикъл с дължина 2. Имайте предвид, че околността на всеки връх на мрежата на фиг. 1 се формира от други два върха.

Модели на колективно поведение, базирани на синхронни булеви мрежи

В този раздел представяме и анализираме два феномена на колективно поведение, които могат да се наблюдават в реалния свят. Първият е съответстващо поведение. Това означава, че агентът е съгласен с мнението на някои агенти от неговия квартал. Лесно е да се намерят много примери за съответствие в реалния живот: от размирици и финансови кризи, споменати по-горе, до президентски избори и др. Второто явление, което изследваме, е антиконформиращо поведение. Агентът, демонстриращ антиконформиращо поведение, действа като противоположност на агент с конформно поведение: той избира да не действа, докато определено количество агенти от неговия квартал са активни и обратно.

Нека разгледаме SBN с вершини, интерпретиращи агенти. Ще кажем, че произволен агент е активен (неактивен) в момента, ако (съответно). Предполагаме, че произволен агент е свързан с тегловната функция на един от следните два типа: (1) (2) където се наричат ​​съответно праг на съответствие и праг на несъответствие.

По същество (1) означава, че агентът става активен в момента само ако в момента са активни поне агенти от неговия квартал. В противен случай става неактивен в момента. По-нататък ние наричаме такива агенти като конформисти. По същия начин (2) означава, че става неактивен в момента, ако поне агенти от неговия квартал са активни в момента и става активен в противен случай. Тези агенти ще бъдат наричани антиконформисти. Стойности и ние ще наречем съответно ниво на съответствие и ниво на несъответствие. Освен това приемаме, че ако тогава сумата на съответните тегла е .

Позволявам да бъде конформист с прага на съответствие и. Тогава е ясно, че това е, което приема стойността на всеки момент. Това означава, че агентът е активен по всяко време, независимо от решенията на агентите в неговия квартал. Ще наричаме такива агенти като подбудители.

Сега нека бъдем антиконформист с праг на антиконформност и. Следвайки подобни разсъждения, можем да заключим, че такъв агент е неактивен по всяко време, независимо от решенията на агенти от неговия квартал. Ние наричаме такива агенти лоялисти.

За произволен агент, който не е нито подбудител, нито лоялен, ще се отнасяме като прост агент. По този начин произволен прост агент е или конформист с, или антиконформист с .

На фиг. 2 демонстрираме обозначението, което използваме по-долу.