Related Works

As we already noted, the paper [1] is the fundamental work in the field of threshold models of collective behavior. In a number of later works, for example [3]–[5], the ideas from [1] were detailed and applied to analysis of various sociological situations.

In [6]–[9] and others it was shown that various phenomena of collective behavior may be studied from the game theory point of view. In particular, equilibrium states [1] in collectives can be considered as Nash equilibria. In this context we would like to mention the work [7] in which the conformity and anticonformity were considered from the game theory positions.

In the paper [10] the influence of thresholds distributions on the genesis and development of several phenomena (in particular, the so called bandwagon effect) in the networks with arbitrary structure is analyzed.

As we said above, synchronous Boolean networks were introduced by S. Kauffman in [2]. In that paper problems of analysis of fixed points and cycles of corresponding discrete functions were considered as important and helpful for the study of dynamics of real gene networks. Apparently, [11] is the first example of application of combinatorial algorithms to the search for cycles of discrete functions specified by Kauffman networks. Later the same authors used the SAT approach for similar purposes [12]. In [13] we considered the problem of search for fixed points of discrete functions specified by networks, in which vertex weight functions take natural values and at the same time act as threshold functions. In order to solve the corresponding problems, we used both SAT and ROBDD approaches. Also in [13] we studied an opposite problem: given fixed points of the function specified by some network, to restore the structure of the network.

In recent years there were published a lot of works about the analysis of structure of big networks and processes that can occur in them. Works [14] and [15] are quite complete reviews of relevant topics.

Synchronous Boolean Networks

A Synchronous Boolean Network (SBN) is defined as a directed graph in which with each vertex there is associated a total function that takes values from at discrete moments of time. Hereinafter we will refer to such functions as vertex weight functions. The value of a weight function for an arbitrary vertex at moment is calculated based on the values of weight functions of some set of network vertices at moment . In SBNs values of all weight functions are updated simultaneously (synchronously). Note that the weight functions can be specified in various ways: by truth tables, Boolean formulas or predicates. Values of weight functions of all vertices at an arbitrary moment , can be considered as a result of computing a value of a discrete function that takes a Boolean vector of length as input and outputs a Boolean vector of length , where is the number of vertices in the network. We denote a Boolean vector consisting of weight functions values at moment as and call it a network state at moment . We will refer to as an initial network state. It is clear that an arbitrary SBN with vertices has different network states.

Thus, more formally, let us assume that is a directed graph with vertices that represents some SBN. Below we will consider only graphs without loops and without multiple arcs. For convenience let us mark vertices by natural numbers from to . With an arbitrary vertex , we associate a weight function , whose values are defined at discrete moments of time . We assume that at each weight function has some initial value. By we denote such a set of network vertices that for each , the graph has an arc . Essentially it means that contains vertices that directly affect . We also call a neighborhood of .

From here on by we mean the set of all possible binary words of length . The rules that specify each weight function , are the same at any moment of time. It means that in total these functions specify a vector function that is defined everywhere in and takes values from . We denote this function as and refer to it as a discrete function defined by network . The transitions between network states, represented by Boolean vectors from , can be naturally illustrated using special graphs called State Transition Graphs (STGs). We denote the STG of network as . An example of a simple SBN with 3 vertices where weight functions are specified by Boolean formulas is displayed in Fig. 1.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Figure 1. An example of a Kauffman network and its State Transition Graph.

The left part shows a simple Kauffman network with 3 vertices. Weight functions are specified by Boolean formulas in the right upper part of the figure. The lower right part demonstrates the state transition graph (STG) for the discrete function specified by this network. It contains one cycle of length 2 and one fixed point.

https://doi.org/10.1371/journal.pone.0115156.g001

As we already noted, the amount of different states of an arbitrary SBN with vertices is , and the rules, according to which the network transitions from one state into another, do not depend on . Therefore, regardless of the network state at moment , there are such and , , that . In this situation we call the sequence of transitions a cycle of length [2]. In some works on the analysis of dynamical properties of gene networks the cycles are called "attractors". The cycle of length 1 is called a fixed point of function . For the network in Fig. 1 it is easy to see that is a fixed point, while a sequence forms a cycle of length 2. Note that the neighborhood of every vertex of the network in Fig. 1 is formed by other two vertices.

Models of Collective Behavior Based on Synchronous Boolean Networks

In this section we introduce and analyze two phenomena of collective behavior that can be observed in the real world. The first one is conforming behavior. It means that an agent agrees with the opinion of some agents from its neighborhood. It is easy to find many examples of conformity in real life: from riots and financial crises mentioned above to presidential elections, etc. The second phenomenon we study is anticonforming behavior. The agent demonstrating anticonforming behavior acts as an opposite to an agent with conforming behavior: it chooses not to act while certain amount of agents from its neighborhood are active and vice versa.

Let us consider an SBN with vertices interpreting agents. We will say that an arbitrary agent , is active (inactive) at moment if (, respectively). We assume that an arbitrary agent is associated with the weight function of one of the following two types: (1)(2)where are called conformity threshold and anticonformity treshold, respectively.

Essentially, (1) means that the agent becomes active at moment only if at least agents from its neighborhood are active at moment . Otherwise becomes inactive at moment . Hereinafter we refer to such agents as conformists. Likewise (2) means that becomes inactive at moment if at least agents from its neighborhood are active at moment and becomes active otherwise. These agents will be refered to as anticonformists. Values and we will call conformity level and anticonformity level, respectively. Further we assume that if then the sum of corresponding weights is .

Let be a conformist with the conformity threshold and . Then it is clear that , i.e. that takes the value of at any moment . It means that agent is active at any moment regardless of decisions of agents in its neighborhood. We will refer to such agents as instigators.

Now let be an anticonformist with anticonformity threshold and . Following the similar reasoning we can conclude that such agent is inactive at any moment of time regardless of decisions of agents from its neighborhood. We call such agents loyalists.

To an arbitrary agent that is neither instigator nor loyalist we will refer as a simple agent. Thus an arbitrary simple agent is either a conformist with or an anticonformist with .

In Fig. 2 we demonstrate the notation that we use below.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Figure 2. Example of an SBN representing a collective with conforming behavior.

This figure shows a network with different types of vertices. Each vertex represents a member of a collective (an agent). Crimson vertices correspond to instigators – agents that are always active. Bright green vertices represent loyalists – agents that are always inactive. The vertex corresponding to simple agent is marked with orange if the agent is active and with blue otherwise. The arcs going from active agents (including instigators) are marked with red. The arcs going from inactive agents (including loyalists) are marked with green. Each simple agent has a conformity level.

https://doi.org/10.1371/journal.pone.0115156.g002

The networks with described types of agents can often be observed in real life. Indeed, for example one can notice that on the early stage of every revolutionary situation there are instigators. Their purpose is to activate as many initially inactive simple agents-conformists as possible. Once they become active, conformists help activating other inactive agents-conformists in the following moments of time. This process gradually involves even agents that are not directly connected to instigators. The goal of loyalists in such situations is to launch the deactivation process aimed at making active simple agents inactive.

It should be noted that the disposition of instigators and loyalists in the network can significantly affect the activation/deactivation of the network. In Fig. 3 we display the behavior of the same network with two different dispositions of instigators at the initial time moment. The considered network does not have loyalists and all its simple agents are conformists. We assume that at the initial moment all the simple agents are inactive (i.e. for every simple agent ). In the first case 5 instigators after 5 moments of time manage to activate only 17 simple agents. In the second case 3 instigators after 5 moments of time activate almost the whole network — 26 simple agents. An important detail here is that in the first case there is more instigators but their disposition is worse.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Figure 3. The behavioral dynamics of the network under the influence of two different dispositions of instigators.

In the initial state all simple agents are inactive. In the first case (left part of the figure), 5 instigators after 5 steps activate 17 simple agents. In the second case (right part of the figure) 3 instigators after 5 steps activate 26 simple agents.

https://doi.org/10.1371/journal.pone.0115156.g003

Further we establish a number of theoretical results regarding the dynamical properties of SBNs with agents of the described types. The main achievement here consists in the justification of the fact that the networks in which all simple agents are conformists and networks where all simple agents are anticonformists can demonstrate significantly different activation/deactivation dynamics.

Conforming Behavior

Consider an arbitrary SBN with agents. We assume that all the simple agents in the network are conformists and that there can be instigators and loyalists. Hereinafter we study two problems that we believe to be interesting from the practical point of view.

In the context of the first problem (to which we will refer below as Problem 1) we consider a network with agents among which there can be , instigators, while all the other agents are simple agents-conformists. We assume that a priori instigators can be arbitrarily placed in the network. Also we assume that at the initial time moment all the simple agents are inactive. The goal is to find such disposition of instigators that starting from the network after some time moments transitions to the state with the majority of active agents.

The second problem (to which we will refer below as Problem 2) consists in the following: we consider the network with a fixed disposition of , instigators and all the other simple agents-conformists are active at the initial moment . We assume that it is possible to replace , arbitrary simple agents by loyalists. We need to find such disposition of these loyalists that starting from the network after some time moments transitions to the state with the majority of inactive simple agents.

Let us show that the following theorem holds.

Anticonforming Behavior

Consider an arbitrary SBN with agents. We assume that all simple agents in are anticonformists and also that the network can contain instigators and loyalists.

On the first glance it may seem that the dynamical processes we studied for the collectives of conformists should have some simple analogues in the collectives of anticonformists. However, more thorough investigation reveals that this is not the case. In particular, assume that is a network in which any agent has a nonempty neighborhood (. Also let this network contain neither instigators nor loyalists. Then it is easy to see that if all the agents in the network are conformists (with non-zero conformity thresholds), then the states and are fixed points. However, if all the agents are anticonformists (with non-zero anticonformity thresholds) then there is the cycle of length : . Indeed, let be the network for which all listed conditions are satisfied, all its simple agents are anticonformists and they are inactive at moment . Let be an arbitrary agent of the network and be its neighborhood. Since (by assumption), then at all the agents from have the state. Therefore for any value of we have: , so at moment the agent will switch its state to . Since is an arbitrary network agent, it means that at moment every agent of the network will switch to the state . Now let us consider what occurs at moment . Let be an arbitrary agent-anticonformist. Then at moment all the agents in are in the state 1. It means that for any the following holds: . In this situation at moment the agent switches to the state . But since is an arbitrary agent, then all the network agents switch to at . Therefore we have the cycle .

The following theorem describes the dynamics of collectives of anticonformists with the initial conditions similar to that in Theorem 1. It can be noted that in this situation, generally speaking, the collective of anticonformists has more complex behavior than that of the collective of conformists. In particular, if the network of anticonformists starts from an initial state in which all simple agents-anticonformists are inactive, then it may not reach an equilibrium state (a fixed point).

Final Remarks

In this part we presented several theoretical results regarding the conforming and the anticonforming behavior. From our point of view these results explain a number of phenomena observed in the real world. In particular, fast activation of a large network by a relatively small number of instigators can be explained not only by the network structure (for example by its strong connectivity) or by small conformity thresholds but also by advantageous disposition of instigators. If there exists such disposition of small number of instigators, that forces the network to transition from the state with inactive simple agents to the state with the majority of active agents, then this network is vulnerable to instigators. To determine the degree of such vulnerability for some particular disposition of instigators it is sufficient to study the behavioral dynamics of the network for at most time moments. This fact is the assertion of the Theorem 1. Evidently, for many real-world networks the vulnerability to instigators is highly undesirable. On the other hand, as it follows from the Corollary 1, even if the network was already activated by instigators, but there is a solution of Problem 2, then, roughly speaking, the situation can be improved by transforming a number of simple agents to loyalists.

Theorem 3 shows that the activation dynamics of collectives of anticonformists can significantly differ from that of the collectives of conformists even for the similar initial conditions. Unfortunately, we could not obtain any analogues of Theorems 1 and 3 for collectives in which simple agents are represented by both conformists and anticonformists. In the section about the experiments we give an example when such network displays more complex behavior.

SAT Approach to the Study of SBN-Based Models of Collective Behavior

Note that in the real world the conforming behavior is spread much more than the anticonforming. On the other hand, the collectives of anticonformists demonstrate more complex behavioral dynamics compared to that of collectives of conformists. It follows from theorems 1 and 3. That is why in our computational experiments we studied the collectives of conformists and concentrated our attention on Problem 1 and Problem 2, formulated above. We would like to point out the fact that the considered problems are combinatorial since they presume the analysis of many possible variants of dispositions of instigators and loyalists. We applied to Problem 1 and Problem 2 the algorithms that are used to solve the Boolean satisfiability problem (SAT). This choice is motivated by the fact, that modern SAT solving algorithms are very powerful computational methods that successfully cope with combinatorial problems from a wide spectrum of practical areas [16].

For an arbitrary Boolean formula the Boolean satisfiability problem (SAT) consists in answering a question if this formula is satisfiable, i.e. if there exists such an assignment to Boolean variables of this formula, that makes the formula true. This problem in the general case can be effectively (in polynomial time on the length of a binary encoding of the considered formula) reduced to the problem of deciding if a Boolean formula in a conjunctive normal form (CNF) is satisfiable. Taking this fact into account, below we consider SAT in the following formulation: for an arbitrary CNF over the set of Boolean variables we need to answer a question if is satisfiable, and if the answer is ‘yes’, to present a corresponding variable assignment that evaluates to . This problem is NP-hard, therefore, it cannot be solved in polynomial time if . Nevertheless, SAT is very important in a practical sense because a lot of industrial problems can be effectively reduced to it and solved using modern algorithms developed during recent 15 years. Basic algorithmic constructions used in solving SAT and main directions of development and applications of SAT approach are described in [16].

The reducibility of an arbitrary NP problem to SAT (in the form of decision problem) follows from the Cook theorem [17]. However, in practice the analysis of specific details of the considered problem makes it possible to significantly decrease the size of the CNF formula produced. A number of general techniques used to reduce combinatorial problems to SAT can be found in [18].

The SAT approach was successfully applied to the search for cycles of functions defined by Boolean networks in [12] and [19]. It should be noted, however, that networks studied in that papers have their own specifics motivated by the source of origin: essentially they are Kauffman networks in which the power of the neighborhood of an arbitrary agent does not exceed some relatively small number (usually ). Also, weight functions used in [12] and [19] are completely different from the ones we use. That is why below we present a relatively detailed description of the SAT encoding process for problems outlined above.

Basic idea that is used to encode many combinatorial problems to SAT, including problems studied in our paper, is to represent the computation process for the considered discrete function (in our case it is ) as a Boolean circuit formed by logical gates from a complete basis (for example ). Formally, circuit is a directed acyclic graph where nodes are labeled as inputs. All other nodes of this graph are called inner nodes. Each inner node corresponds to logical gate from the chosen basis. Usually, nodes that form the output of the considered function are referred to as output gates. In our case circuit has output gates.

Circuit inputs are labeled by Boolean variables . Below we refer to these variables as input variables. An output of each logical gate is marked by an auxiliary variable . By we denote a set of variables corresponding to output gates. We refer to as output variables. Let be the set of all auxiliary variables. Then , . For circuit it is possible to effectively construct (in linear time on the total number of nodes in the circuit) a CNF , using the Tseitin transformations [20] procedure, described below.

Assume is an arbitrary gate in . If is a NOT-gate then it has a single input labeled by variable . Then for NOT-gate we construct a formula where by we mean logical equivalence. The CNF-representation of the Boolean function specified by formula is

If is an AND-gate, and are variables corresponding to its inputs, then for we construct formula and CNF

We say that CNFs constructed this way encode the corresponding logical gates. Then the CNF encoding circuit is

where is a CNF that encodes gate .

Once we have a CNF we can extend it by adding new constraints in the clausal form that specify function properties we are interested in. For example, a CNF in which , specifies a fixed point of function . To be more precise, CNF is satisfiable if and only if function has fixed points. If is satisfiable and its satisfying assignment is obtained, then we can effectively extract the corresponding fixed point: it is sufficient to write down values of the input variables. To make a SAT instance that specifies the problem of finding a cycle of length we need to represent a superposition as Boolean circuit , and construct the CNF of the kind .

Instead of logical gates we actually can use more complex basic Boolean functions, such as predicates over finite sets. In this case elements of the corresponding sets are represented by Boolean vectors. In fact this is what we do to encode functions for networks with weight functions (1) and (2).

Now let us consider an SBN with vertices and weight functions (1) that can have both instigators and loyalists. Assume that the network is functioning for time moments. The decision of agent , at moment we encode with Boolean variable .

We would like to stress out once more that a priori we do not know dispositions of instigators and loyalists in the network and therefore presume that any agent can take one of these roles. To take into account that an arbitrary vertex can be either an instigator, a loyalist or a simple agent, we introduce two additional sets of Boolean variables , . We assume that if , then is an instigator; if , , then it takes the role of a loyalist; if then our vertex represents a simple agent. The situation corresponding to would mean that the vertex is simultaneously an instigator and a loyalist. That is why it is forbidden by means of a clause .

Let be an arbitrary network vertex, and be a conformity level of . We introduce the following predicate (3)

Then from the above we can conclude that the decision of agent at moment is associated with the following formula: (4)

Additional constraints on the initial network state are encoded in a similar fashion. For example a constraint that specifies that an arbitrary agent at the initial state is active only if it is an instigator is equivalent to satisfiability of the following formula: (5)

In fact, all clauses of the kind are added to the result CNF only once.

By applying Tseitin transformations to formulas (4) and (5) we can produce CNFs that are satisfiable if and only if the original Boolean formulas are satisfiable. To do this we need to be able to effectively encode predicate (3). It can be represented as a Boolean circuit implementing a function that counts ones in a Boolean vector and then compares the obtained result with . Such circuit can then be encoded to CNF in accordance with the procedure described above. However, there are algorithms that produce more effective SAT encodings for predicates (3). These algorithms are based on various methods that work with so called cardinality constraints ([21]–[25]). In the present paper we encode predicates (3) using sorting networks. The main idea of the corresponding approach is very simple: we can sort bits in an arbitrary Boolean vector descending from left to right, as we consider them as natural numbers from the set . Let be a result of such sorting. Then it is clear that , if and only if . Essentially, in our work to sort Boolean vectors we used binary variants of Batcher sorting networks [26], [27]. A SAT encoding of such network with input and output requires auxiliary variables and clauses. SAT encodings for the constraints that specify that after time moments the network must contain at least , active agents and the constraints of the kind , are produced in a similar way.

It is easy to see that in the general case, if we encode the evolution of network with vertices during moments of time, then in the CNF obtained the number of variables and clauses will be upper-bounded by . Taking into account the theorems proved above for the combinatorial problems considered we can study only cases when .

We would like to briefly mention algorithms underlying the solvers that we have used to study the proposed models. As we said above, the book [16] is probably the most complete source of information about the algorithms for solving SAT. There are several classes of such algorithms and their effectiveness is justified by their ability to solve real practical problems. To solve SAT instances encoding the combinatorial problems outlined above we used modern CDCL solvers, basic design features of which are described in [28]. This choice is motivated first by the fact that CDCL solvers provide us with exact solutions, and, second, these particular algorithms successfully cope with many hard SAT instances, for example, with instances that encode some cryptanalysis problems.

Computational Experiments

In our computational experiments we constructed networks according to the known models of random graphs. In particular, we used the Gilbert model [29] also known as the Erdos-Renyi model [30] (see also [31]), the Watts-Strogatz model [32] and the Barabasi-Albert model [33].

Informally the process of constructing tests for combinatorial problems outlined above for SBNs in which simple agents are conformists (tests for networks of anticonformists are generated in a similar way) looks as follows.

1. We generate a random oriented simple graph (without loops and without multiple arcs) with vertices, in the form of adjacency matrix where main diagonal is filled with zeros.
2. For each of vertices we generate a conformity threshold that is randomly selected from according to the uniform distribution.
3. For a fixed number of time moments we encode to SAT the problem of search for a disposition of instigators with given constraints on their number (Problem 1).
4. The CNF obtained is given to a SAT solver.
5. If the SAT solver managed to solve the instance, before exceeding the time limit, and found a satisfying assignment, then the corresponding disposition of instigators is extracted.
6. For the instigators disposition obtained we encode the problem of search for a disposition of loyalists with given constraint on their number (Problem 2).
7. The CNF obtained on the previous step is given to a SAT solver.
8. If the SAT solver managed to solve the provided instance and found a satisfying assignment then a corresponding disposition of loyalists is extracted.

Now let us briefly describe random graph models that we used. In fact, original models generate undirected graphs, so we modified them to take into account all features of formulas (1) and (2) (the neighborhood of vertex is formed by vertices in that have arcs going to ).

When generating a graph according to the Gilbert-Erdyos-Renyi model we fix the parameter that is the probability of an arc. Then an arbitrary element , of an adjacency matrix of graph takes the value of with probability and the value of with probability .

An important feature of the original Watts-Strogatz model is that random graphs generated according to this model have the small-world property that can often be observed in real world networks. The parameters of the Watts-Strogatz model include , and . First we generate a regular lattice network with vertices, where each vertex , is connected with an arc with vertices on either side of if is even. If is odd then we can consider and similar arcs . On the second stage of graph generation each arc with probability is rewired to , where is chosen according to the uniform distribution from some subset of in such a way that in the resulting graph there will be no loops and no multiple arcs.

The Barabasi-Albert model is important because it allows one to generate random networks with scale-free property. The construction of a network according to the Barabasi-Albert model can be considered as an iterative process consisting of steps. On the step an initial network with vertices is built. The result of each step is the network which is constructed by adding to one new vertex connected to existing vertices of . The procedure of constructing edges , is probabilistic and is referred to as preferential attachment. According to this procedure for and an arbitrary the edge is added to with probability

Step lasts, i.e. the corresponding probabilistic experiments are repeated, until vertex is connected with vertices of the graph . In our experiments we use the following modification of the Barabasi-Albert model. An open cycle, i.e. a cycle in which an edge connecting the first and the last vertices is removed, is used as an initial network . On each step the probabilistic experiment is carried out for all pairs of the kind where , and as a result of the step new vertex is connected with existing vertices. In the final network every edge is replaced by a pair of arcs and .

Defining the conformity thresholds of agents in real networks is a highly nontrivial task and in each particular case it requires a thorough analysis of the corresponding specifics. Since the main goal of our computational experiments was to test the general applicability of the SAT approach to the study of the considered models, we chose conformity thresholds for each vertex randomly (according to the uniform distribution on ).

In the series of experiments we considered networks with 500 vertices. SAT instances were solved using the Plingeling SAT solver [34] working on 32 threads (two 16-core AMD Opteron 6276 CPUs with 64 GB RAM). The corresponding results are shown in tables 1, 2 and 3.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Table 1. Results of the computational experiments for Barabasi-Albert networks with 500 vertices.

https://doi.org/10.1371/journal.pone.0115156.t001

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Table 2. Results of the computational experiments for Watts-Strogatz networks with 500 vertices.

https://doi.org/10.1371/journal.pone.0115156.t002

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Table 3. Results of the computational experiments for Erdos-Renyi networks with 500 vertices.

https://doi.org/10.1371/journal.pone.0115156.t003

Below we demonstrate several figures that illustrate the dynamics of SBNs with 30 vertices modeling the conforming behavior under the influence of instigators and loyalists. In Fig. 4 the evolution of the network generated according to the Barabasi-Albert model is displayed. In Fig. 5 we show that some networks (the particular network displayed was generated in accordance with the Watts-Strogatz model) are highly vulnerable to the influence of instigators. For the network shown it is sufficient to place one instigator to activate the whole network in steps. However, it is possible to find such disposition of loyalists that transforms the network to a state with the majority of inactive agents.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Figure 4. The behavior of the Barabasi-Albert network with 30 vertices under the influence of instigators and loyalists.

In the upper part of the figure the functioning of the network under the influence of 3 instigators is shown. In the lower part of the figure the functioning of the network under the influence of 3 instigators and 7 loyalists is shown. Dispositions of instigators and loyalists were found as solutions of Problem 1 and Problem 2.

https://doi.org/10.1371/journal.pone.0115156.g004

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Figure 5. The behavior of the Watts-Strogatz network with 30 vertices under the influence of instigators and loyalists.

In the upper part of the figure the functioning of the network under the influence of 1 instigator is shown. In the lower part of the figure the functioning of the network under the influence of 1 instigator and 9 loyalists is shown. Dispositions of instigators and loyalists were found as solutions of Problem 1 and Problem 2.

https://doi.org/10.1371/journal.pone.0115156.g005

Intuitively, one of the most natural strategies of constructing dispositions of instigators is to place them into vertices with the largest number of outgoing arcs. In Fig. 6 (the network is generated according to the Erdos-Renyi model) we show, that even if we forbid instigators to replace agents with the most advantageous positions (in the sense explained above), that does not exclude the existence of other possible variants of dispositions of instigators that transform the network into states with the majority of active agents. The corresponding constraints that forbid instigators and loyalists to take place of particular vertices are quite easily encoded into SAT.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Figure 6. The behavior of the Erdos-Renyi network with 30 vertices under the influence of instigators and loyalists.

In the upper part of the figure the functioning of the network under the influence of 4 instigators is shown. In the lower part of the figure the functioning of the network under the influence of 4 instigators and 6 loyalists is shown. Dispositions of instigators and loyalists were found as solutions of Problem 1 and Problem 2. Instigators could not take place of top 10 vertices with the largest number of outgoing arcs.

https://doi.org/10.1371/journal.pone.0115156.g006

Also we considered optimization variants of Problem1 and Problem2, i.e. to find corresponding dispositions of instigators and loyalists of a minimal cardinality. These problems can also be effectively reduced to SAT using techniques described above. On the current stage we managed to solve corresponding problems for networks with 100–150 vertices.

In tables 1, 2 and 3 we present the information about the size of encodings and about the time required to solve Problems 1 and 2 on determining dispositions of instigators or loyalists. We considered networks with 500 vertices. For each value of parameter in case of Erdos-Renyi networks, combination of values of and in case of Watts-Strogatz networks, and in case of Barabasi-Albert networks we generated 10 different tests. Note, that solving time can greatly vary even within one test series (for a particular random graph model). From our point of view it can be explained by the fact that among randomly generated tests there can appear instances that are very complex for the particular SAT solver. However, such instances appear quite rarely while the majority of tests are solved relatively fast.

Additional Materials

In this section we propose some additional materials. In particular, there are videos that illustrate the dynamics of collectives of conformists under the influence of instigators and loyalists (in the context of Problems 1 and 2 outlined above). Corresponding collectives are represented by SBNs with 200 vertices. On S1 Video we show the behavior of the Barabasi-Albert network under the influence of 29 instigators and 60 loyalists. S2 Video demonstrates the dynamics of the Watts-Strogatz network with 10 instigators and 60 loyalists. On S3 Video the behavior of the Erdos-Renyi network under the influence of 16 instigators and 44 loyalists is shown.

Conclusions and Future Works

In the present paper we introduce the models of collective behavior, that are based on the synchronous Boolean networks, and study several phenomena related to conformity and anticonformity. In the context of the proposed models we formulate several combinatorial problems on the search for dispositions of agents with special properties (instigators and loyalists) in a network. To these combinatorial problems we applied modern algorithms for solving the Boolean satisfiability problem (SAT).

We do not pretend that the results of our paper can be directly applied to practice since all computational experiments were performed for artificially generated networks with a random structure. However, our main goal was to show the principal possibility of solving corresponding combinatorial problems for networks with hundreds of vertices.

We believe that the use of various SAT parallelization techniques will make it possible to develop our approach in such a way that it will be applicable to networks with 1000 and more vertices. The corresponding methods will be useful in the study of networks that represent strongly connected components extracted from the real world networks with a much greater number of vertices. The vulnerability of such strongly connected components to instigators in our opinion can have highly undesirable consequences for the corresponding large networks. To extract strongly connected components from real world networks, one can use methods from [35].

As we mentioned above, determining correct thresholds is probably the hardest stage of construction of any collective behavior model. In our experiments we generated such thresholds randomly. To study real world processes this task should be performed by a specialist in a relevant field of science (such as economy, biology, sociology, psychology, etc.).

Unfortunately we could not obtain the results similar to theorems 1 and 3 for the networks, in which simple agents are represented both by conformists and anticonformists. In Fig. 7 we show how such network starting from the state in which all simple agents are inactive enters the cycle of length 4. It means that these networks display more complex behavior than that described by theorems 1 and 3.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Figure 7. The cycle of length 4 for the network with both conformists and anticonformists.

The agents-conformists are marked with "C" and agents-anticonformists are marked with "A". The network contains 7 instigators (crimson vertices). At the initial time moment all simple agents are inactive.

https://doi.org/10.1371/journal.pone.0115156.g007

Also it should be noted that the key condition in theorems 1 and 3 is that all simple agents must be either all inactive or all active at the initial time moment. If we drop this condition, the corresponding networks can display the behavior different from that described by Theorems 1 and 3. For example in Fig. 8 we demonstrate the cycle of length for the network with instigators, where all simple agents are conformists, but at the initial state there are both active and inactive simple agents.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Figure 8. The nontrivial cycle of length 3 for the network of conformists with instigators.

At the initial state in the network there are both active and inactive simple agents.

https://doi.org/10.1371/journal.pone.0115156.g008

We would like to note that for the models proposed it is possible to study more complex dynamical properties using the formalism of quantified Boolean formulas with two quantification levels (2QBF) [36]. Suppose that is a disposition of instigators and is a disposition of loyalists. Then, for example, the condition that there exists such disposition of instigators, that for any disposition of loyalists the network, starting from the state with inactive simple agents after several time moments transitions to a state in which almost all simple agents are active, can be described using the 2QBF of the following kind:

This condition can be considered as an improved variant of condition describing the vulnerability of the network to instigators. To solve such problems one can use modern 2QBF-solvers [36], [37]. We can also take into account any constraints on the cardinality of and .

Finally, one natural extension of the proposed models is to assign various types of weights to network arcs and modify vertex weight functions accordingly. Arc weights can represent social pressure, authority, etc. for each particular member of a collective. In addition to that, it would be interesting to study the dynamics of networks in which weight function of a vertex can take into account the influence of vertices that are at a distance in from the vertex considered. All the listed aspects can be quite easily implemented into corresponding SAT encodings. We plan to do it in the nearest future.