P Systems for Social Networks

P Systems for Social Networks Erzs´ebet Csuhaj-Varj´u1, Marian Gheorghe2, Gy¨orgy Vaszil1, Marion Oswald3 1Computer and Automation Research Institute Hungarian Academy of Sciences H-1111, Budapest, Kende u. 13-17, Hungary {csuhaj,marion,vaszil}@sztaki.hu 2Department of Computer Science University of Sheffield Regent Court, Portobello Street, Sheffield S1 4DP, United Kingdom [email protected] 3Institute for Computer Languages Vienna University of Technology Favoritenstr. 9-11, 1040 Vienna, Austria [email protected] Summary. We introduce some variants of P systems that mimic the behaviour of social networks and illustrate some of the characteristics of them. Other concepts related to social networks are discussed and suitable classes of P systems are suggested. A simple example shows the capabilities of such a P system where the intensity of the communication is modelled with complementary alphabets. 1 Introduction Membrane computing (also called P systems theory) is a new computing paradigm, which in its initial variants was inspired by the structure and functionality of the living cell [19]. Later on some other biological entities have been considered in order to extend the capabilities of this computational model - tissues or special types of cells, like neurons, or colonies of cells, like bacteria. So far, concepts and methods of P systems theory have been successfully employed in solving important problems of computer science and describing various biological phenomena, but, except promising applications in linguistics and natural language processing, only a limited amount of attention has been paid to the suitability of membrane systems in modelling social phenomena. In this paper, we attempt to build a bridge between membrane computing and the theory of social networks, an area of great interest in contemporary computer science and practice. For this reason, we define certain classes of P systems which are suitable for modelling features of social networks and which can be derived from problems in this field, and we formulate various research topics related to 114 E. Csuhaj-Varj´u et al. connections between P systems theory and the theory of social interactions and networks. The underlying mathematical tool set is the theory of formal languages, i.e., our approach to social networks is a purely syntactic one. We note that social phenomena have already been described by different frameworks in formal language theory, our recent aim is to formulate models which combine tools of both membrane computing and formal language theory. In terms of formal grammars, communities of agents interacting with each other and with their dynamically changing environment were modelled by eco-grammar systems, a research field launched in [9]. Population of agents, called networks of (parallel) language processors, with biological and social background were described by rewriting systems in [12, 7]. Another formal language-theoretic model for communities of evolving agents, called evolutionary systems, was introduced in [10]. Multi-agent systems in terms of formal language theory and membrane computing were discussed in [4], [5], [3], and [15]. 2 Social Networks In various formalisms related to the study of social phenomena, interpersonal relationships between individuals are defined as information-carrying connections [14]. These relationships come in various forms, two of them are strong and weak ties. Weak ties seem to be responsible for the embeddedness and structure of social networks and for the communication within these systems [14]. There are other measures that characterise connections between nodes (individuals). Centrality gives an indication of the social power of a node and the strength of its connections. It relies on other measures, betweenness, closeness, degree. Betweenness measures to what extent a node is connected to nodes that have a significant number of neighbours (direct connections). Closeness is the degree describing that a node is close to all other nodes in the network: it counts the number of connections. For the above concepts as well as for other measures of the connections existing in social networks, we refer to [23]. 3 P Systems Capturing Communication Aspects We are focusing now on identifying some classes of P systems that capture communication aspects in social networks. We can consider various types of nodes: ordinary or popular nodes - those that host individuals and allow communication between them; new-born nodes - those that are dynamically created and linked to the existing network; non-visible or extinct nodes - the nodes that are no longer connected to the network or have disappeared; nodes with one way communication, only allowing information to go into, blackholes or allowing only to exit from, whiteholes. Some of these aspects have been already considered in the current research framework of membrane computing; for instance population P systems allow nodes P Systems for Social Networks 115 to be dynamically connected and disconnected [6]; the one-way communication for communicating accepting P systems has been considered in [13]. We can also take into account connections between nodes and look at the volume of communication - the amount of (new) information generated or sent-received by various nodes or groups of nodes; frequency of communicated messages - the number of communication steps related to the evolution (computation) steps; communication motifs - patterns of communication identified throughout the network evolution. In order to capture these phenomena we aim to formally define a generic and flexible framework whereby these concepts can be appropriately accommodated. In this respect we provide the following general definition of a population P system governed by communication, a pgcP system, for short. 4 Preliminaries and Definitions Throughout the paper we assume that the reader is familiar with the basics of membrane computing and formal language theory; for details we refer to [17, 21] and [22]. For an alphabet V, we denote by |V|the cardinality of V, and by V∗ the set of all finite words over V. If λ, the empty word is excluded, then we use the notation V+.As usual in membrane computing, we represent the finite multisets over Vby strings over Vas well, that is, a string and all its permutations correspond to the same multiset. We denote by |w|athe number of occurrences of a symbol a∈Vin a string w∈V∗which is equal to the multiplicity of that object in the represented multiset. We use ∅to denote the empty multiset, and also use V∗to denote the set of finite multisets over an alphabet V. In the following we consider P systems with static underlying graph structure; the notion can easily be extended to a construct capturing dynamically changing underlying graph architecture as well. Definition 1. A population P system governed by communication (a pgcP system, for short), is a construct (Σ, E, ω1, . . . , ωn,(ρ1, R1), . . . , (ρk, Rk)), n, k ≥1, where •Σ=Σ1∪Σ2is a finite alphabet of objects, Σ1is the alphabet of cellular objects, i.e., the objects in the nodes, and Σ2is the set of communication symbols; •E⊆ {1, . . . , n}×{1, . . . , n}is the set of (directed) links between the nodes; •ωi∈Σ∗ 1,1≤i≤n, is a multiset of cellular objects, the initial content of the node iof the system; and •(ρi, Ri),1≤i≤k, are predicate based rule-sets governing the transitions of the system, with –ρi:Σ∗ 2→ {true, false}, a predicate over the multisets of communication symbols, and 116 E. Csuhaj-Varj´u et al. –Ri= (Ri,1, . . . , Ri,n), an n-tuple of sets of rewriting rules, where Ri,j,1≤ j≤n, is the set of rules that are allowed to be applied at node j, and any rule is of the form u→vfor u∈Σ∗ 1,v∈(Σ1∪(Σ1×Σ2×Tar))∗where Tar ={1, . . . n}is a set of target indicators. Definition 2. A configuration of a pgcP system Π= (Σ, E, ω1, . . . , ωn,(ρ1, R1), . . . , (ρk, Rk)), n, k ≥1, is an n+s-tuple for s=|E|, (w1, ..., wn;u1, ..., us), wi∈Σ∗ 1, uj∈Σ∗ 2,1≤i≤n, 1≤j≤s, where multiset wiis the multiset of cellular objects at the i-th node, i.e., the current content of node i,1≤i≤n, and ujis the multiset of communication symbols associated to the communication link ej∈E, 1≤j≤s. The initial configuration of Πis (ω1, . . . , ωn;∅, . . . , ∅). The pgcP system works by changing its configurations. In the following we describe the transition or configuration change: it takes place by rewriting and communication of the cellular objects and recording the performed communication. The rewriting rules are applied to the cellular objects in the maximally parallel manner, i.e., any object can be involved in at most one rule application, and as many rules are applied simultaneously to the cellular objects at the nodes as possible. Definition 3. Let Π= (Σ, E, ω1, . . . , ωn,(ρ1, R1), . . . , (ρk, Rk)),n, k ≥1, be a pgcP system and let c1= (w1, ..., wn;u1, ..., us)and c2= (w0 1, ..., w0 n;u0 1, ..., u0 s)be two configurations of Π. We say that c1changes directly to c2(or c2is obtained from c1with a transition), denoted by c1= (w1, ..., wn;u1, ..., us)⇒(ρi,Ri)c2= (w0 1, ..., w0 n;u0 1, ..., u0 s) for some i∈ {1, . . . , k}, if the following hold: •ρi(u1, . . . , us) = true, •c1is changed to c2by using the rules of Ri= (Ri,1, . . . , Ri,n)as follows: – the rules of Ri,j are applied in the maximal parallel manner in the node j to the multiset wj,1≤j≤n; and – if a rule of the form u→vwhere v=v1v2for v1∈Σ∗ 1and v2∈(Σ1× Σ2×Tar)∗is applied in a node j, then the following holds: ·uis changed to v1v2and all objects in v1remain in node j; ·all symbols of (a, a0, l)∈v2are processed by sending the cellular object a∈Σ1to node land adding the communication object a0∈Σ2to the multiset associated to the link (j, l)∈E,1≤j6=l≤n. P Systems for Social Networks 117 The pgcP system may record information on the communication performed during the whole computation or only on communication during the last configuration change. This is captured in the following definition. Definition 4. Let Π= (Σ, E, ω1, . . . , ωn,(ρ1, R1), . . . , (ρk, Rk)),n, k ≥1, be a pgcP system. We say that Πworks in the •history preserving mode, if for any transition (w1, ..., wn;u1, ..., us)⇒(ρi,Ri)(w0 1, ..., w0 n;u0 1, ..., u0 s) it holds that u0 j=uju00 j,for 1≤j≤s, where u00 jis the multiset of communication symbols sent to link jduring the transition, •non-history preserving mode, if u0 jconsists of the communication symbols sent to link jduring the transition (the communication symbols in ujare forgotten). Definition 5. Let Π= (Σ, E, ω1, . . . , ωn,(ρ1, R1), . . . , (ρk, Rk)),n, k ≥1, be a pgcP system. A derivation (or computation) in Πis a sequence of transitions starting in the initial configuration and ending in some final (possibly halting) configuration. The result of a computation in a pgcP system Πcan be defined in various manners. We may consider the number (vector) of (certain) communication objects going through (certain) communication links or the number (vector) of (certain) cellular objects in (certain) nodes. If we assume distinguished, so called output link(s) or node(s), then we indicate this fact in the notation for the accepted languages of the pgcP system. As usual in membrane computing we consider only halting computations. Definition 6. Let Π= (Σ, E, ω1, . . . , ωn,(ρ1, R1), . . . , (ρk, Rk)), where n, k ≥1, and let Ti⊆Σi,1≤i≤2, be the sets of terminal cellular and communication objects; Out1⊆ {1, . . . , n}and Out2⊆Ebe the sets of output nodes and output links, respectively. •We define Ncell(Π, T1, Out1)(P scell(Π, T1, Out1)) as the number (vector) of terminal cellular objects in the output nodes in a final configuration. •We define Ncom(Π, T2, Out2)(P scom(Π, T2, Out2)) as the number (vector) of terminal communication objects associated to the output links in a final configuration. 5 Complementary Alphabets in pgcP Systems We are focusing now on communication in these networks. In order to characterize its intensity and the fact that the importance of a connection might evolve in time by either increasing or decreasing its value, we would need some sort of symbols that act in this respect. One way to model this is by considering complementary 118 E. Csuhaj-Varj´u et al. communication symbols, whereby the customary (or positive) symbols strengthen a connection, whereas the complementary (negative) ones weaken it. Formally this is achieved by splitting the alphabets Σ1and Σ2as follows: Σi=Σ0 i∪¯ Σ0 i∪Σ00 i where Σ0 iand ¯ Σ0 i,i= 1,2 are dual alphabets.Σ0 iconsists of normal (positive) elements and ¯ Σ0 icontains complementary symbols. The idea of complementary alphabets is not new in the field of natural computing. DNA computing has as a core data structure a double-strand structure consisting of dual elements, the DNA nucleotides, adenine, thymine, cytosine and guanine represented by the four letter alphabet, {A, T, C, G}, respectively; the pairs (A, T) and (C, G) are known as complementary base pairs [20]. In the context of networks of Watson-Crick D0Lsystems, networks of such systems over DNA-like alphabets are introduced and operations relying on complementarity properties are utilised [8, 11]. Active and passive objects have been considered in a similar way with complementary elements. Two types of such objects have been introduced and studied: within components [1] and on membranes [2]. Other membrane systems using complementary features are spiking neural P systems with anti-spikes where a neuron receiving sspikes and tanti-spikes is left with s−tif s≥tor t−swhen t≥s objects [18], and membrane systems with bi-stable catalysts, where the system may switch between two states [17]. To demonstrate the above ideas, we present a simulation of an n-register machine Mwhere the communication is controlled by “Watson-Crick-like” predicates. An n-register machine M= (Q, R, q0, qf, P ), n≥1,is defined as usual, that is, with internal state set Q, registers R= (A1, . . . , An), initial and final states q0, qf∈Q, respectively, and a set of instructions Pof the form (q, Ai+, r, s) or (q, Ai−, r, s), q, r, s ∈Q, q 6=qf, Ai∈R. When an instruction of the first type is performed, then Mis in state q, increases the value of register Aiby one, and enters a state ror s, chosen nondeterministically. When an instruction of the second type is performed, then Mis in state qand it subtracts one from the value of register Aiif it stores a positive number and then enters state r, or it leaves the value of Aiunchanged if it stores zero and then enters state s. There are no instructions for the final state, therefore the machine halts after entering state qf. Mstarts its work in the initial state, q0, with empty registers. Then it performs a sequence of instructions; if the sequence is finite (it ends with halting), then we speak of a computation by M. The result of the computation is the number stored in the output register A1after halting. It is known that 2-register machines are able to compute any recursively enumerable set of numbers [16]. Example 1. Let M= (Q, R, q0, qf, P ), n≥1,be an n-register machine. We construct the pgcP system Πwith n+ 1 nodes simulating Mas follows. Let Π= (Σ, T1, E, w0, w1, . . . , wn,(ρ1, R1),(ρ2, R2), Out) P Systems for Social Networks 119 where Σ=Σ1∪Σ2with Σ1={a, ¯a} ∪ {q, [q, r, s]|q, r, s ∈Q},Σ2={a, ¯a}, and E={(0, i)|1≤i≤n},T1={a},and Out = 1. The initial configuration and the rule sets are defined as follows. Let w0=q0,and wi=∅,1≤i≤n. Moreover, let R1= (R1,0, . . . , R1,n), R2= (R2,0, . . . , R2,n), and let ρ1(u1, . . . , un) : |ui|a≥ |ui|¯afor all 1 ≤i≤n, R1,0={q→[q, r, s](a, a, j)|(q, Aj+, r, s)∈P} ∪ {q→[q, r, s](¯a, ¯a, j)|(q, Aj−, r, s)∈P} ∪ {[q, r, s]→r, [q, r, s]→s|q, r, s ∈Q}, ρ2(u1, . . . , un) : |ui|a<|ui|¯afor some i, 1≤i≤n, R2,0={[q, r, s]→s(a, a, j)|(q, Aj−, r, s)∈P},and finally Rj,k ={a¯a→ε}for all 1 ≤j≤2,1≤k≤n. If Πworks in the history preserving mode, then the difference between the number of symbols aand ¯aon a link (0, j) for some 1 ≤j≤ncorresponds to the value of register j. The result of the computation can be found in node 1 corresponding to the output register A1of Mif the system introduces the symbol qfin node 0 and halts (because there is no rule for the final state in M). Thus, these variants of pgcP systems are computationally complete. The reader may observe that in the above example we have not only complementary alphabets, but through various global predicates, the sets of rules are split into “normal” rules in R1and “recovery” rules in R2. We note that it is possible to simulate a register machine with one active component and nothers receiving values aor ¯a. In a very similar way, we can consider a distributed model where the ncomponents corresponding to registers are used in such a way that each one has its own addition and subtraction rules, similar to R1,0, R2,0. In this case we have to communicate not only aor ¯abut also the label of the next register to the component simulating this register; some other variants of rules can be considered. Regarding these two models, one immediate question, perhaps not difficult to be addressed, is which one is simpler, more efficient - with respect to the number of rules, symbols etc; or are they just the same? What about simulating one with the other one? Furthermore, the example of simulating a register machine suggests the use of dual sets of rules, triggered by predicates, i.e., to have for each rule, r, its dual rule, ¯r, defined in such a way that the complementary rules introduce complementary symbols (only). 120 E. Csuhaj-Varj´u et al. 6 Further Research Topics In the previous sections we introduced the concept of a pgcP system inspired by social networks and made some steps towards identifying the necessary abstract elements related to measuring the intensity of the communication in these systems. In this respect, complementary alphabets and particular variants of pgcP systems have been considered. In the following, we define some further concepts regarding some specific types of pgcP systems, and list some preliminary results for these so-called deterministic and non-cooperative pgcP systems. Definition 7. Let Π= (Σ, E, ω1, . . . , ωn,(ρ1, R1), . . . , (ρs, Rs)),n, s ≥1, be a non-cooperative deterministic pgcP system. Let c(t) = (w1(t), ..., wn(t); u1(t), ..., us(t)), t ≥0, be a computation in Πin the history preserving mode. We define the 1. growth of communication volume on link iat derivation step t,t≥1,by fi:N→Nwhere fi(t) = |ui(t)|−|ui(t−1)|. 2. frequency of communication on link i: hi:N→ {0,1}where hi(t)=0if |ui(t)| − |ui(t−1)|= 0 and hi(t) = 1 if |ui(t)| − |ui(t−1)| ≥ 1; 3. intensity of communication on link i: gi:N→R, where gi(t) = fi(t) t. If Σ2=Σ0 2∪¯ Σ0 2∪Σ00 2, i.e., complementary symbols are considered, then ¯ fi(t) defined over ¯ Σ0 2, and difference functions as fi(t)−¯ fi(t) can also be defined and examined. We note that the above concepts can be extended with suitable modifications to gcpP systems in the general sense; obviously, in this case we speak of relations, instead of functions. These notions have their roots in concepts related to networks of parallel language processors [12] and evolutionary systems [10]. A network of parallel language processors with D0L systems as components (an NLP-D0L system) consists of D0L systems located in nodes of a finite virtual graph (each node has at most one D0L system) which rewrite and communicate multisets of strings present in the nodes according to their own rule sets. A D0L system G= (V, P, ω) is a triplet, where V is an alphabet, Pis a finite set of rules of the form a→αwith a∈V, α ∈V∗and for each a∈Vthere exists exactly one rule in P, and, finally, ω∈V+. For any string x=x1. . . xn,xi∈V, 1≤i≤n, we say that xdirectly derives y=y1. . . yn, if xi→yi∈Pholds for 1 ≤i≤n. (For more details on D0L systems, we refer to [21]). The NLP-D0L system functions with alternating rewriting and communication steps. By rewriting, each string at every node is rewritten in parallel; the D0L systems work in a synchronized manner. By communication, a copy of each string at a node is sent to each other node, given that the string satisfies the sender node’s output context condition (predicate) and the receiver node’s input context condition (predicate). Communication is performed in a parallel and synchronized P Systems for Social Networks 121 manner as well. In [12] it was shown that if the conditions for communication are random context conditions, i.e., they check the presence and /or the absence of certain symbols in the strings to be communicated, then the growth of the number of the strings in the network can be described by a growth function of a D0L system. The growth function of a D0L system orders to the number of derivation steps the length of the string obtained at that step. It was also shown, that the number of strings at specific nodes and the number of communicated strings between nodes can also be obtained from D0Lgrowth functions with suitable homomorphisms. The idea of the proofs comes from the property that in the case of D0Lsystems any string generates only one string and the alphabet of the successor string can be calculated from the alphabet of the predecessor string. The reader may easily notice the close relation between NLP-D0L systems and non-cooperative deterministic pgcP systems: The multisets of different symbols communicated from a node to some other one by an NLP-D0L system at any computation step corresponds to multisets of communication symbols added to the links of an appropriate pgcP system (where the predicates checks the presence/absence of types of objects in the multiset). Therefore, we may describe the growth of the communication volume, the frequency, and the intensity of communication on the links by tools of Lindenmayer systems, in particular the theory of D0L systems. Since D0L systems demonstrate several nice decidability properties, the theory provides efficient tools for characterizing the behaviour of particular types of pgcP systems. The detailed comparison is a topic for future research. In context of social networks and pgcP systems, a number of other general problems can also be formulated. For example, how to describe and characterize other concepts and measures from social networks and how to define and model problems like leaders and clusters emergence. Or, how to dynamically restructure the links and distinguish between good and bad or strong and weak links; what about breaking the links. Finally, how to solve various problems or compute functions with such systems. These and similar questions form the basis of challenging future research. 7 Acknowledgement The work of Erzs´ebet Csuhaj-Varj´u and Gy¨orgy Vaszil was supported in part by the Hungarian Scientific Research Fund, OTKA, Grant no. K75952. The work of Marian Gheorghe was partially done during his visit to the Computer and Automation Research Institute, Hungarian Academy of Sciences, in June 2010, and partially was supported by the grant K75952, Hungarian Scientific Research Fund, OTKA.