A szinkron logikai hálózatok használata a kollektív viselkedés számos jelenségének modellezésére

ISDCT SB RAS, Irkutszk, Oroszország

Sztyepan Kochemazov,
Alekszandr Szemenov

Ábrák

Absztrakt

Idézet: Kochemazov S, Semenov A (2014) A szinkron logikai hálózatok használata a kollektív viselkedés számos jelenségének modellezésére. PLoS ONE 9 (12): e115156. https://doi.org/10.1371/journal.pone.0115156

Szerkesztő: Lars Kaderali, Drezdai Technische Universität, Orvostudományi Kar, Németország

Fogadott: 2014. augusztus 7 .; Elfogadott: 2014. november 19 .; Közzétett: 2014. december 19

Adatok elérhetősége: A szerzők megerősítik, hogy az eredmények alapjául szolgáló összes adat korlátozás nélkül teljes mértékben elérhető. Minden releváns adat megtalálható a dokumentumban és a kiegészítő információkat tartalmazó fájlokban.

Finanszírozás: Ezt a munkát részben támogatta az Orosz Tudományos Akadémia szibériai kirendeltsége a 80. számú „Differenciál-diszkrét és integrodifferenciális egyenletek. Alkalmazás a természettudományok problémáira” interdiszciplináris integrációs projekt keretében, az Orosz Alapkutatásért Alapítvány (projektek 14-07-00403 és 14-07-31172mol) és az Orosz Föderáció elnökének Tanácsa a vezető tudományos iskolák állami fenntartásáért (5007.2014.9. Projekt). A finanszírozóknak nem volt szerepük a tanulmányok tervezésében, adatgyűjtésben és elemzésben, a közzétételre vonatkozó döntésben vagy a kézirat elkészítésében.

Versenyző érdeklődési körök: A szerzők kijelentették, hogy nincsenek versengő érdekek.

Bevezetés

Az utóbbi években jelentősen megnőtt az érdeklődés a kollektív viselkedés különböző jelenségeinek elemzése iránt. Azzal magyarázható, hogy az emberi tevékenység szinte minden területén folyamatok zajlanak információcserével a kollektívákon belül. Az ilyen folyamatok mélyen befolyásolják a kollektív jövőbeli magatartását, és pozitív vagy negatív következményekkel járhatnak nemcsak az érintett kollektívára, hanem egy sokkal nagyobb társadalmi formációra is. Például a részvények intenzív eladása a tőzsdén olyan szereplők részéről, amelyek nagy hatással vannak másokra, a globális gazdasági indexek drasztikus csökkenéséhez vezethet. A zavargások és a forradalmi helyzetek hasonló módon zajlanak, amikor a felbujtók viszonylag kis csoportja olyan sok embert aktivál, hogy az állambiztonsági rendszerek nem képesek megbirkózni ezzel.

A közösségi hálózati szolgáltatások későbbi évekbeli aktív fejlesztése nagymértékben megnövelte a kollektív viselkedésmanipuláció lehetőségeit. Ez a tézis olyan forradalmi jelenségek elemzésével bizonyítható, mint az arab tavasz, a 2011–13-as orosz tiltakozások, az Euromaidan stb. Ezeknek az eseteknek a többségét a szociális hálózatokon keresztül tervezték meg. Érdemes megemlíteni, hogy az ilyen folyamatokat általában kijelölt aktivisták kis csoportjai koordinálják.

A kollektív viselkedés modellezését számos tanulmányban tanulmányozták. Sok más szerző nyomán munkánkat M. Granovetter [1] tanulmányára alapozzuk, amelyben a kollektív viselkedés küszöbmodelljeit vizsgálták. A küszöb viselkedése azt jelenti, hogy a csoport (ügynök) minden tagjának állapota csak akkor változik, ha egy speciális funkció értéke, amely ehhez az ágenshez kapcsolódik, eléri a küszöböt. Az ilyen viselkedésre a legegyszerűbb példa a többség döntésének követése. Granovetter modelljében az ügynököket összekötő hálózatot egy teljes grafikon határozza meg - minden ügynök figyelembe veszi minden más ügynök véleményét. Sok valós helyzetben ez a megközelítés nem használható. Például a valós világ társadalmi hálózataiban az ügynök általában valamilyen szomszédságból származó ügynökök véleményére alapozza a véleményét. Ebben az esetben az ilyen szomszédságon kívüli ügynökök véleménye nem befolyásolja az érintett ügynök véleményét. Hasonló helyzetek figyelhetők meg a genetikában: sok génhálózatban az egyes géneket közvetlenül érintő gének mennyisége kicsi a hálózatban található gének teljes számához viszonyítva.

A dinamikus folyamatok hasonlóságai, amelyek a génhálózatokban és a társadalmi hálózatokban megfigyelhetők, ötlethez vezettek bennünket a kollektív viselkedés Boole-hálózatokon alapuló modelljeinek bevezetésére és elemzésére. A logikai hálózatok apparátusát 50 éve használják a matematikai biológiában. Az alábbiakban az úgynevezett szinkron logikai hálózatokat (SBN) vizsgáljuk, amelyeket először S. Kauffman vezetett be [2] a génhálózatok dinamikai tulajdonságainak elemzése céljából. Megközelítésünkben a kollektívát SBN-nek tekintjük, amelynek speciális funkciói vannak a hálózati csúcsokkal társítva. A mi szempontunkból a logikai hálózatok nyelve alkalmas a kollektív viselkedés számos jelenségének magyarázatára. Például az [1] egyensúlyi állapotai a megfelelő SBN által meghatározott diszkrét függvény rögzített pontjaiként tekinthetők meg. Az ilyen modellek másik fontos jellemzője, hogy az SBN-ek elemzése során felmerülő kombinatorikus problémák megoldására lehetőség nyílik a Boole-egyenletek nagy rendszereinek modern megoldására. Erre a célra a cikkünkben algoritmusokat használunk a Boole-féle elégedettségi probléma (SAT) megoldására.

Kapcsolódó munkák

Mint már megjegyeztük, a tanulmány [1] az alapvető munka a kollektív viselkedés küszöbmodelljei területén. Számos későbbi munkában, például [3] - [5], az [1] ötleteit részletesen bemutatták és különböző szociológiai helyzetek elemzésére alkalmazták.

A [6] - [9] és más cikkekben kimutatták, hogy a kollektív viselkedés különféle jelenségei játékelméleti szempontból tanulmányozhatók. Különösen a kollektívák egyensúlyi állapotai [1] tekinthetők Nash-egyensúlynak. Ebben az összefüggésben szeretnénk megemlíteni azt a munkát [7], amelyben a megfelelőséget és az antikonformitást a játékelméleti pozíciókból vették figyelembe.

A cikkben [10] elemzik a küszöb-eloszlások befolyását számos jelenség (különösen az úgynevezett sávkocsi-hatás) keletkezésére és fejlődésére az önkényes felépítésű hálózatokban.

Mint fentebb említettük, a szinkron logikai hálózatokat S. Kauffman vezette be [2]. Ebben a cikkben a rögzített pontok és a megfelelő diszkrét funkciók ciklusainak elemzésével kapcsolatos problémákat tartották fontosnak és hasznosnak a valós génhálózatok dinamikájának tanulmányozásához. Nyilvánvaló, hogy a [11] az első példa a kombinatorikus algoritmusok alkalmazására a Kauffman-hálózatok által meghatározott diszkrét funkciók ciklusainak keresésére. Később ugyanazok a szerzők hasonló célokra használták a SAT megközelítést [12]. A [13] -ban megvizsgáltuk a hálózatok által meghatározott diszkrét függvények rögzített pontjainak keresési problémáját, amelyben a csúcs súlyfüggvényei természetes értékeket vesznek fel, és egyúttal küszöbfüggvényként is működnek. A megfelelő problémák megoldása érdekében mind a SAT, mind a ROBDD megközelítést alkalmaztuk. Szintén egy ellentétes problémát vizsgáltunk a [13] -ban: adott funkciók adott pontjait adtuk meg valamelyik hálózatnak, hogy helyreállítsuk a hálózat szerkezetét.

Az elmúlt években rengeteg mű jelent meg a nagy hálózatok szerkezetének és a bennük előforduló folyamatok elemzéséről. A [14] és [15] mű a teljes témák átfogó áttekintése.

Modellek

Szinkron logikai hálózatok

A szinkron logikai hálózatot (SBN) egy olyan irányított gráfként definiáljuk, amelyben az egyes csúcsokhoz egy teljes függvény társul, amely értékeket különálló pillanatokban vesz fel. A továbbiakban olyan függvényekre fogunk utalni, mint a csúcs súlyfüggvényei. Egy tetszőleges csúcs súlyfunkciójának pillanatnyi értékét néhány hálózati csúcs halmazának pillanatnyi súlyfüggvényeinek értéke alapján számítják ki. Az SBN-ekben az összes súlyfüggvény értéke egyidejűleg (szinkronosan) frissül. Ne feledje, hogy a súlyfüggvényeket többféleképpen lehet megadni: igazságtáblák, logikai képletek vagy predikátumok segítségével. Az összes csúcs súlyfüggvényeinek értékei tetszőleges pillanatban figyelembe vehetők egy olyan diszkrét függvény értékének kiszámításának eredményeként, amely egy logikai hosszúságú vektort vesz be bemenetként és egy logikai hosszúságú vektort eredményez, ahol a csúcsok száma a hálózat. Jelölünk egy logikai vektort, amely a súlyfüggvények pillanatnyi értékeiből áll, és pillanatnyilag hálózati állapotnak hívjuk. Kezdeti hálózati állapotnak fogjuk nevezni. Nyilvánvaló, hogy egy tetszőleges, csúcsokkal rendelkező SBN-nek különböző hálózati állapota van.

Így formailag tegyük fel, hogy ez egy olyan csúcsokkal ellátott irányított gráf, amely valamilyen SBN-t képvisel. Az alábbiakban csak a hurkok nélküli és több ív nélküli grafikonokat vesszük figyelembe. A kényelem érdekében jelöljük meg a csúcsokat természetes számokkal tól-ig. Egy tetszőleges csúcshoz társítunk egy súlyfüggvényt, amelynek értékeit diszkrét időpillanatokban határozzuk meg. Feltételezzük, hogy minden súlyfüggvénynek van valamilyen kezdeti értéke. Ezzel olyan hálózati csúcsok halmazát jelöljük, amelyek mindegyikének egy íve van. Lényegében azt jelenti, hogy olyan csúcsokat tartalmaz, amelyek közvetlenül hatnak. Környékének is nevezzük .

Innentől kezdve az összes lehetséges bináris hosszúságú szó halmazát értjük. Az egyes súlyfüggvényeket meghatározó szabályok bármely időpontban megegyeznek. Ez azt jelenti, hogy ezek a függvények összességében meghatároznak egy vektorfüggvényt, amelyet mindenhol meghatároznak, és amelyből értékeket vesz fel. Ezt a függvényt jelöljük, és a hálózat által definiált diszkrét függvénynek nevezzük. A hálózati állapotok közötti átmeneteket, amelyeket Boolean-vektorok képviselnek, természetesen speciális, State Transition Graphs (STG) nevű grafikonok segítségével szemléltethetjük. A hálózat STG-jét jelöljük. Az 1. ábra egy egyszerű, 3 csúcsú SBN-re mutat példát, ahol a súlyfüggvényeket logikai képletek határozzák meg.

A bal rész egy egyszerű Kauffman hálózatot mutat, 3 csúccsal. A súlyfüggvényeket logikai képletek határozzák meg az ábra jobb felső részén. A jobb alsó rész az állapotátmenet-grafikont (STG) mutatja a hálózat által meghatározott diszkrét függvényhez. Ez egy 2 hosszúságú ciklust és egy rögzített pontot tartalmaz.

Mint már megjegyeztük, egy tetszőleges SBN csúcsokkal rendelkező állapotainak mennyisége megegyezik, és a szabályok, amelyek szerint a hálózat egyik állapotból a másikba vált át, nem függenek. Ezért a hálózati állapot pillanatától függetlenül vannak ilyenek, és. Ebben a helyzetben az átmenetek sorozatát hosszú ciklusnak nevezzük [2]. A génhálózatok dinamikai tulajdonságainak elemzésével foglalkozó néhány munkában a ciklusokat "vonzónak" nevezik. Az 1 hosszúságú ciklust fix függvénypontnak nevezzük. Az 1. ábra szerinti hálózaton könnyen belátható, hogy ez egy fix pont, míg egy szekvencia egy 2 hosszúságú ciklust képez. Vegye figyelembe, hogy az 1. ábrán a hálózat minden csúcsának szomszédságát másik két csúcs alkotja.

A kollektív viselkedés modelljei szinkron logikai hálózatok alapján

Ebben a részben bemutatjuk és elemezzük a kollektív viselkedés két, a való életben megfigyelhető jelenségét. Az első a megfelelő viselkedés. Ez azt jelenti, hogy egy ügynök egyetért a szomszédságából származó egyes ügynökök véleményével. Könnyű megtalálni a megfelelőség számos példáját a való életben: a fent említett zavargásoktól és pénzügyi válságoktól az elnökválasztásokig stb. A második jelenség, amelyet tanulmányozunk, az antikonformáló magatartás. Az antikonformáló magatartást tanúsító szer ellentétesen viselkedik a megfelelő viselkedésű ágenssel: úgy dönt, hogy nem cselekszik, miközben a szomszédságából bizonyos mennyiségű hatóanyag aktív, és fordítva.

Vegyünk egy SBN-t csúcsokat értelmező ágensekkel. Azt mondjuk, hogy egy tetszőleges ügynök aktív (inaktív), ha (vagy). Feltételezzük, hogy egy tetszőleges ágens társul a következő két típus egyikének súlyfüggvényéhez:.

Lényegében az (1) azt jelenti, hogy a szer csak akkor válik aktívvá, ha legalább a szomszédságából származó ágensek aktívak. Ellenkező esetben inaktívvá válik pillanatnyilag. A továbbiakban az ilyen szereket konformistáknak nevezzük. Hasonlóképpen (2) azt jelenti, hogy pillanatnyilag inaktívvá válik, ha legalább a szomszédságából származó ügynökök aktívak és másképp aktívak. Ezekre a szerekre antikonformistákként hivatkozunk. Értékeket és megfelelőségi szintet, illetve antikonformitási szintet fogunk hívni. Feltételezzük továbbá, hogy ha a megfelelő súlyok összege .

Legyen konformista a megfelelőségi küszöbértékkel és. Akkor világos, hogy, vagyis bármelyik pillanatban veszi az értékét. Ez azt jelenti, hogy az ügynök bármikor aktív, függetlenül a szomszédságában lévő ügynökök döntéseitől. Az ilyen ügynököket felbujtóként fogjuk említeni.

Legyen most antikonformista antikonformitás küszöbértékkel és. A hasonló okfejtést követve arra a következtetésre juthatunk, hogy az ilyen ügynök bármely pillanatban inaktív, függetlenül a szomszédságában lévő ügynökök döntéseitől. Az ilyen ügynököket hűségeseknek hívjuk.

Egy önkényes ügynökre, amely nem ösztönző vagy hűséges, egyszerű ügynöknek fogunk nevezni. Így egy önkényes egyszerű szer vagy konformista, vagy antikonformista .

A 2. ábrán bemutatjuk az alábbi jelölést.