## Abstract

We study a process of opinion formation in a population of agents whose interaction pattern is defined on the basis of randomly distributed groups of three agents (triplets), in contrast to networks, which are defined on the basis of agent pairs. Results for the time needed to reach full consensus are compared between a triplet-based structure with a given number of triplets and a random network with the same number of triangles. The full-consensus time in the triplet structure is systematically lower than in the network. This discrepancy can be ascribed to differences in the shape of the probability distribution for the number of triplets and triangles per agent in each interaction pattern.

## 1. Introduction

The representation of interaction patterns as graphs-or, as they are usually called, networks–is a widespread paradigm in science. Networks lie at the basis of the description of a broad class of systems, ranging from intra-cellular molecular reactions and neural tissues, to artificial objects such as the internet (Boccaletti *et al.* 2006; Newman *et al.* 2006). These systems are conceived as populations of active agents (chemicals, neurons, computers), each of them occupying a network node. A link between two agents represents the possibility that they interact, mutually affecting their individual dynamics. Binary interactions, in fact, are an implicit assumption within the network picture. The inherent binary-like nature of all physical interaction laws may explain why, from the viewpoint of physicists, networks provide such a satisfactory conceptual framework for applications of statistical physics to other branches of knowledge.

It is not always possible, however, to reduce the dynamical laws of a multi-agent system to binary interactions. Examples are found, for instance, in social dynamics (Starkey *et al.* 2000; Johnson 2008). Imagine a group of five people—A, E, I, O and you–who meet to discuss and make a decision on a given issue. As soon as A exposes her views, your own opinion begins to react to them, perhaps changing a little, or being reinforced. Most probably, however, before your reaction to A’s views is definitively settled, you are already listening to E’s. These have been influenced by A’s speech and, in turn, are expected to modify both your pre-existing opinion and the way it is affected by A’s. As successive views are presented and overlap with each other, the intricacy of their mutual effect grows. The group’s final decision will hardly be describable as the outcome of a sequence of binary events, each involving just two people. In other words, from the viewpoint of the group’s dynamics, a representation in terms of a mere collection of binary links joining its members seems unsuitable. The intricate overlapping of the involved elementary processes suggests that the group should be considered as a single entity, subject to dynamical rules that are able to give an overall description of the relation between the group’s states and its possible outcomes.

In this paper, we consider a process of opinion formation in a population whose interaction pattern is defined in terms of randomly distributed groups of three agents, or triplets. Emphasis is placed on comparison with the same process running on a random Erdős–Rényi network, where the role of triplets is replaced by triangles, each of them formed by three mutually linked nodes. The Erdős–Rényi network is built in such a way that the number of triangles equals, on average, the number of triplets in the triplet-based structure. We find that the time needed to reach full consensus in this structure is systematically shorter than in the network, in spite of the fact that the number of triplets per agent in the former is the same as the number of triangles per agents in the latter. This leads us to compare, in more detail, the statistics of triplets or triangles in each interaction pattern. The analysis discloses the different effects of the two patterns on the dynamical process taking place in the population.

## 2. Multiplet-based populations

From the several possible ways in which a network can be characterized (Newman *et al.* 2006), the one that is most suitable for the generalization we discuss in this paper is the traditional definition given by graph theory (Gross & Yellen 1999). A graph is defined as a set of vertices—or nodes, which we associate with the members or agents in a population—and a list of edges—or links, which represent the potential interaction between agents. Each edge is effectively defined by the pair of vertices that it connects. In other words, for a given population, a network is completely characterized by listing the pairs of nodes connected by links. Over the population, thus, a network is a collection of node pairs.

This characterization of the structure of a population can be immediately generalized. Instead of a collection of node pairs (duplets), we specify a collection of node groups (multiplets), each group containing a certain number of nodes, *m* (*m*-plet). In this way, agents are aggregated into groups of different sizes. In networks, an agent may participate in several interaction pairs, depending on its connectivity. Similarly, in the mutiplet-based population, a given agent can belong to more than one multiplet. Multiplets are conceived to replace network links as the basic units associated with the elementary interactions between agents (Johnson 2008).

Figure 1 gives two instances of small multiplet-based populations. In figure 1*a*, we have a six-agent population whose interaction structure is defined by a duplet (1,2), a triplet (1,3,5) and a quintuplet (2,3,4,5,6). Agents 1, 2, 3 and 5 belong to more than one multiplet. Figure 1*b* shows a six-agent population structured into three triplets (1,2,3), (2,4,5) and (3,5,6).

Is there, however, a genuine difference between a multiplet-based structure and a network? Would not each multiplet be equivalent to a fully connected group of vertices—a clique (Newman *et al.* 2006) or simplex (Johnson 2008)—in an ordinary network? Comparison of figure 1*b*,*c* shows, by means of a simple example, that this is not the case. In figure 1*c*, each triplet of figure 1*b* has been replaced by the links that interconnect its three agents. In the resulting network, however, the triangle formed by agents 2, 3 and 5 turns out to be equivalent, from the viewpoint of its interaction pattern, to the triangle formed, for instance, by 1, 2 and 3. In the structure of figure 1*b*, on the other hand, (1,2,3) is indeed one of the triplets in the population, while (2,3,5) does not exist as such.

A full appraisal of the implications of extending networks to multiplet-based structures must, in any case, be sought through its effects on the collective dynamics of the population. In the next section, we consider a process of opinion formation (Krapivsky & Redner 2003; Boccaletti *et al.* 2006; Galam 2008) and compare results for the time needed to reach full consensus in networks and in triplet-based structures. Differences can be ascribed to rather non-trivial statistical properties of both kinds of interaction pattern.

## 3. Opinion dynamics in triplet structures

The dynamical processes that may require a representation of the population in terms of multiplets—for instance, the case of decision-making discussed in §1—need not be the same as those that work on networks, such as, for instance, peer-to-peer information transmission. For the sake of comparison between the effects that these two different interaction patterns have on dynamics, however, we analyse, in this section, the same process of opinion formation running both on a network and on a triplet-based structure.

Consider a population of *N* agents where, at each time *t*, the opinion *s*_{i}(*t*) of each agent *i* adopts one of the two given values, say, *s*_{i}(*t*)=+1 or −1. At each evolution step, three agents *i*, *j* and *k* are chosen, and they adopt the opinion of the majority among them, i.e.
3.1
The choice of the three agents is performed according to the structure of the population, as explained in the following.

First, we consider an *N*-node Erdős–Rényi random network (Newman *et al.* 2006), where each of the *N*(*N*−1)/2 possible links is effectively present with probability *p*. Thus, for large *N*, the expected number of links is *L*=*p**N*^{2}/2. In this network, we define a triangle as a set of three mutually connected nodes. The expected number of triangles is Δ=*p*^{3}*N*^{3}/6. On this network, the three agents chosen at each evolution step of the process of opinion formation must form a triangle.

Second, we consider what could be called an Erdős–Rényi triplet-based structure, where each of the *N*^{3}/6 possible triplets in the *N*-agent population is effectively present with probability *q*. Consequently, the expected number of triplets is *T*=*q**N*^{3}/6. In the process of opinion formation running on this structure, the three agents chosen at each step must belong to the same triplet. Taking *q*=*p*^{3}, we have, on average, *T*=Δ. With this choice, the dynamics on the network and on the triplet structure can be quantitatively compared.

We study the process of opinion formation on these two interaction patterns by means of numerical simulations. We focus on the time needed to reach full consensus, when all the agents share the same opinion. Three stages contribute to the full-consensus time in a finite population. If, in the initial condition, the two opinions are more or less balanced over the population, the first stage corresponds to the escape from the vicinity of the state where opinions are equally frequent, to a region where the inbalance between opinions is of order *N*. In this stage, the dynamics is equivalent to a symmetric random walk. Therefore, the evolution of the number of agents with either opinion is, with respect to the following stage, relatively slow. In the second stage, during which the prevalence of the majority opinion over the dissenters increases monotonically, the dynamics is fast and essentially deterministic. Finally, when only a few dissenters remain, the dynamics is stochastically driven by the now-infrequent events where dissenters are chosen and converted to the majority opinion. This is again a relatively slow process. In our numerical simulations, we skip the first stage by taking an initial number of dissenters equal to *N*/4, so that 75 per cent of the population is already consensual. The initial dissenters are distributed at random.

The numerical construction of the two interaction patterns is as follows: we first fix the number *T* of triplets, and choose at random the corresponding *T* groups of three agents. Two or more triplets containing the same three agents are avoided. With this procedure, the triplet-based structure is completely defined. Then, we construct a random network with *L*=*N*(3*T*/4)^{1/3} links. Multiple links between any two agents are forbidden. The expected number of triangles for that number of links is, precisely, *T*. For a given realization of the random network with *L* links, the number of triangles Δ—which is close, but not necessarily equal to *T*—is determined by simple counting. The full-consensus time *t*_{c}, measured in evolution steps, is determined as a function of Δ in the network, and of *T* in the triplet structure. Results for fixed networks and triplet structures, with given values of Δ and *T*, are averaged over 10^{4} realizations for different initial opinion distributions.

Figure 2 shows *t*_{c} as a function of Δ and *T* for a population of *N*=1000 agents. Empty and full circles, respectively, correspond to results for the network (*t*_{c} versus Δ) and the triplet structure (*t*_{c} versus *T*), for the number of triangles and triplets ranging from 2500 to 5000. We find that the number of evolution steps needed to reach consensus on the network is more disperse and systematically larger than in the triplet-based structure. In the range displayed, the two values of *t*_{c} differ by a factor of almost two. For larger values of Δ and *T*, as may be expected, the full-consensus times for the two interaction patterns approach each other. In fact, in the limit where all the possible links and all the possible triplets are present, Δ=*T*=*N*^{3}/6, the two times must be identical. Conversely, they are increasingly different as the interaction patterns become more sparse. Consistent results were obtained for systems of various sizes.

What is the origin of the difference between the full-consensus times in the network and in the triplet structure? In view of the fact that the dynamical rules of opinion formation are identical for the two populations, the answer is to be found in their interaction patterns. In the next section, we provide evidence that an excess of network nodes belonging to a small number of triangles with respect to the agents belonging to the same number of triplets explains the difference. This requires detailed analyses for each kind of pattern, the distribution of triangles or triplets over the population.

## 4. Statistics of triangles and triplets

In our numerical simulations, we have compared the full-consensus times in a network and in a triplet structure constructed in such a way that the number Δ of triangles in the former is, on average, the same as the number *T* of triplets in the latter. This implies, in particular, that the average number of triangles per agent, 3Δ/*N*, equals the average number of triplets per agent, 3*T*/*N*. In the following, we show that these two coincident averages correspond, however, to different distributions. More specifically, the fraction of agents that belong to a certain number of triangles in the network is, in general, different to the fraction of agents that belong to a certain number of triplets in the triplet-based structure.

The fraction of nodes that belong to exactly δ triangles in an *N*-node Erdős–Rényi network can be evaluated by first considering the probability *P*_{n} that a generic node is connected to exactly *n* of the possible *N*−1 neighbours, which is given by the binomial distribution
4.1
where *p* is the probability that a network link is effectively present (see §3). The *n* neighbours form *n*(*n*−1)/2 pairs, some of which can, in turn, be joined by links, thus forming triangles. The probability *P*_{δ}(*n*) that the node with *n* neighbours belongs to δ of those triangles is
4.2
The total probability *P*_{δ} that, irrespective of the number of neighbours, a node belongs to exactly δ triangles is given by the total contribution over the different values of *n*,
4.3
A little algebra shows that, as advanced, the average number of triangles per agent is, in the limit of large *N*, 〈δ〉=*p*^{3}*N*^{2}/2=3Δ/*N*. The width of the distribution can be computed by approximating *P*_{n} by a Gaussian, yielding for the variance
4.4
Which term dominates this expression for large *N* depends on how *p* is assumed to depend on *N* in that limit, as discussed below.

The probability distribution *P*_{τ} of the number of triplets per agent τ in the *N*-agent population with *T* triplets is found, more straightforwardly, to be the binomial
4.5
The mean value, as predicted, is 〈τ〉=3*T*/*N*. For large *N*, the variance is .

Figure 3 shows the probability distributions *P*_{δ} and *P*_{τ} for a population of *N*=1000 agents with 4500 triangles or triplets. Curves stand for the analytical expressions of equations (4.3) and (4.5), and dots correspond to the numerical evaluation of the probabilities, which turn out to be in full agreement with the analytical results. The average number of triangles or triplets per agent is the same for both distributions, 〈δ〉=〈τ〉=13.5. Regarding their shapes and widths, on the other hand, the two functions are substantially different. For the triplet structure, we recognize the symmetric binomial distribution of equation (4.5). The distribution of triangles per agent, in contrast, is clearly asymmetric, with a rather long tail for large δ. Since, moreover, the maximum of *P*_{δ} is sensibly lower than that of *P*_{τ}, for small values of δ and τ, the probability of triangles per agent is higher than that of triplets per agent. In other words, the fraction of agents that belong to a small number of triangles in the network is larger than the fraction of agents belonging to the same number of triplets in the triplet-based structure.

The difference between *P*_{δ} and *P*_{τ} for small values of their variables provides an explanation for our observation in §3 that the full-consensus time in the network is systematically larger than in the triplet structure. Once the quasi-deterministic stage of the opinion formation process has elapsed, only a few dissenters remain in the population. These last non-consensual agents are expected to belong, on average, to a small number of triangles or triplets. In fact, those agents belonging to a relatively large number of triangles or triplets have had more opportunities of being selected during the preceding stage, thus reaching consensus earlier. For a given number of agents in the left end of the distributions *P*_{δ} and *P*_{τ}, however, the average number of triplets per agent is larger than the corresponding number of triangles. Consequently, the last dissenters have a larger probability per evolution step to be chosen, and their opinion thus changed, in the triplet-based structure. The final evolution stage will therefore elapse faster than in the network.

We end our discussion on the distributions *P*_{δ} and *P*_{τ} by comparing their limits for large populations, . As advanced above, to effectively perform the limit, it is necessary to specify how the interaction pattern changes as *N* grows. We consider three cases: (i) constant total number of triangles or triplets, (ii) constant average number of triangles or triplets per agent, and (iii) constant fraction of effectively present triangles or triplets. In case (i), Δ and *T* are independent of *N*, and the probability *p* of the Erdős–Rényi network scales as *p*∼*N*^{−1}. In case (ii), both Δ and *T* must be proportional to *N*, while *p*∼*N*^{−2/3}. In case (iii), Δ and *T* scale as *N*^{3}, and *p* remains constant.

It is clear that, since in case (i) the number of triangles or triplets is kept constant as the population grows, the distributions *P*_{δ} and *P*_{τ} in the limit of large *N* are trivial. They both collapse to delta functions, with vanishing mean value and variance. Case (ii) is more interesting. In this case, as *N* grows, the mean values 〈δ〉 and 〈τ〉 and the variances and approach constant values. By construction, the limiting values of 〈δ〉 and 〈τ〉 are identical. Also, the two variances turn out to be identical in the limit. Interestingly, however, their mutual approaching for large *N* is very slow, with
4.6
where *k* is a constant. This suggests that the dynamical effects of the difference between *P*_{δ} and *P*_{τ}, such as the different duration of the process of opinion formation discussed in §3, may be perceivable even in very large populations. Finally, in case (iii) the limiting distributions are drastically different. In fact, for the network, the variance grows as , while for the triplet structure, we find .

## 5. Conclusion

Multiplet-based structures are expected to replace networks as a representation of the interaction pattern underlying a population when the relevant dynamical processes cannot be assimilated to sequential binary interactions. This paper, however, has been focused on a comparison of the dynamical effects of the two kinds of pattern on the same process of opinion formation, driven by a majority rule in groups of three agents. By means of numerical simulations, we have determined the time needed to reach full consensus, on the one hand, in a population structured on the basis of randomly distributed triplets and, on the other hand, on a population of the same size whose interactions are described by a random Erdős–Rényi network forming as many triangles as the number of triplets in the triplet-based structure. In spite of the strong similarity between the two versions of the opinion formation process, there is a noticeable difference in the full-consensus time measured on both interaction patterns. We have shown that the difference can be ascribed to higher-order statistical properties in the distribution of triangles or triplets per agent in each pattern. This conclusion points out the significant effect of the kind of underlying interaction pattern in the collective dynamics of the population.

The present results should be considered as a preliminary step in the study of the dynamical effects of multiplet-based structures. Further work may address dynamical processes more specific to this kind of structure, for which networks do not provide a suitable representation of interactions. Besides multi-agent opinion formation and decision-making, we can mention competition for resources, coalition formation and multi-player games. The possibility that, in a given structure, the size of multiplets is not homogeneous, but varies according to a prescribed distribution; the extension of the network-specific notion of degree distribution to multiplets; and the consideration of small-world or scale-free multiplet structures are, among other issues, worth investigating.

## Acknowledgements

The author acknowledges financial support from grants PIP 5114 (CONICET, Argentina) and PICT 17/943/04 (ANPCyT, Argentina).

## Footnotes

One contribution of 14 to a Theme Issue ‘Topics on non-equilibrium statistical mechanics and nonlinear physics’.

- © 2009 The Royal Society