Dynamical origins of the community structure of multi-layer societies Peter Klimek1,†, Marina Diakonova2,†, V´ıctor M. Egu´ıluz2, Maxi San Miguel2, Stefan Thurner1,3,4∗ 1Section for Science of Complex Systems; CeMSIIS; Medical University of Vienna; Spitalgasse 23; A-1090; Austria 2 Instituto de F´ısica Interdisciplinar y Sistemas Complejos IFISC (CSIC-UIB); E07122 Palma de Mallorca; Spain 3IIASA, Schlossplatz 1, A 2361 Laxenburg; Austria 4Santa Fe Institute; 1399 Hyde Park Road; Santa Fe; NM 87501; United States † These authors contributed equally to this work. Social structures emerge as a result of individuals managing a variety of different of social rela- tionships. Societies can be represented as highly structured dynamic multiplex networks. Here we study the dynamical origins of the specific community structures of a large-scale social multiplex network of a human society that interacts in a virtual world of a massive multiplayer online game. 6 There we find substantial differences in the community structures of different social actions, rep- 1 resented by the various network layers in the multiplex. Community size distributions are either 0 similar to a power-law or appear to be centered around a size of 50 individuals. To understand 2 these observations we propose a voter model that is built around the principle of triadic closure. b It explicitly models the co-evolution of node- and link-dynamics across different layers of the mul- e tiplex. Depending on link- and node fluctuation rates, the model exhibits an anomalous shattered F fragmentation transition, where one layer fragments from one large component into many small 9 components. The observed community size distributions are in good agreement with the predicted 2 fragmentation in the model. We show that the empirical pairwise similarities of network layers, in terms of link overlap and degree correlations, practically coincide with the model. This suggests ] that several detailed features of the fragmentation in societies can be traced back to the triadic h closure processes. p - c o I. INTRODUCTION lifetimeoflinks(i.e. thetypicalrateattheyareaddedto s and removed from the network) [5, 6]. Another generic . s featureofsocialnetworksisthatindividualstendtoform c Societiesareorganizeddynamicalpatternsthatemerge communities, i.e. groups of nodes that share more links i s from the social actions of individuals. These arrange an with each other than with nodes outside of the commu- y arrayofdifferenttypesofsocialrelationships(e.g. friend- nity [7, 8]. There is evidence that the organization of h ship,marriage,co-workers,...) toformstablegroups,or- community structure in human societies follows princi- p ganizations, or institutions of various sizes. Each type ples that are deeply rooted in human psychology, such [ of social relation defines a social network of its own. asahierarchicallynestedorganizationofcommunitiesof 2 These networks are not independent of each other but different sizes [9, 10] or Dunbar’s number [11], a hypoth- v co-evolve with the other networks in the society. Soci- esizeduppercognitivelimittothenumberofpeoplewith 6 eties can be understood as the collection of these net- whom humans can share stable social relationships. 7 works and can be represented as a dynamic, co-evolving 5 In this work we investigate the dynamical origins of 1 multiplex network, i.e. a network where a set of nodes the community structure of societies in multiplex net- 0 can be connected by links of more than one type [1–3]. works. Westudyhowthedifferentlayersinthemultiplex . The topological structures of these network layers can 1 influence each other and investigate the resulting conse- 0 vary dramatically, depending on the type of the corre- quences of these interactions for the community struc- 6 sponding social interactions. For example, it has been tures in the individual layers. Community structure will 1 shown that network layers corresponding to cooperative be simply characterized by the community size distribu- : behavior can be characterized by high clustering, high v tions in the different network layers, i.e. the probability Xi reciprocity, and high link overlap, whereas layers encod- for an individual (node) to be part of a community of ingaggressivebehaviorexhibitpronouncedpower-lawde- a given size in a particular layer. As a data set we use r gree distributions [1, 4]. It has also been shown that a the comprehensive dynamic social multiplex network of many characteristics of the individual multiplex layers, the Pardus society [1, 4, 6, 12–14]. This is a virtual so- such as their degree distributions, clustering coefficients, ciety of more than 380,000 players with different social ortheprobabilitiesfornodestoacquirenewlinks,canbe andeconomicinteractionstakingplaceintheopen-ended understood from the assumption that the link dynamics massive multiplayer online game Pardus. We find a sub- innetworksisdrivenbytheprocessoftriadicclosure(i.e. stantial amount of heterogeneity in the community size the tendency that nodes with common neighbors will es- distributions across the different layers. tablish links between themselves) together with a finite Inthisworkwewanttounderstandiftheempiricalob- servationscanbereminiscentofaso-calledfragmentation transition. Fragmentation is the phenomenon in which a ∗Electronicaddress: [email protected] network might undergo a transition from a state where 2 almost all nodes belong to a single giant component to a changeprivate, one-to-onemessagesandtradewitheach fragmented state in which the network breaks into many other in the game. The data can be represented as a dy- smaller components. To this end we propose a new type namicmultiplexnetworkMα(t)wheretheindexαlabels ofvotermodel(VM).VMsintroducedin[15,16]havere- theadjacencymatrixofthenetworkgivenbyinteractions peatedlybeenshowntoexhibitfragmentationtransitions of type α at time t. The multiplex Mα(t) is constructed [17, 18]. In the co-evolutionary VM (CVM) [19] a node for each month (30 days) over one year of data, from can either change its internal state to that of its neigh- Sep 2007 to Sep 2008. Two players are linked in a cor- bor or rewires one of its existing links towards a node responding multiplex layer if they had a friendship link that has the same internal state. Fragmentation transi- (α = friend), traded with each other (α = trade), or ex- tions have been shown to be generic features of rewiring changed a private message (α = communication) within processes and largely independent of the underlying evo- a given month. For a particular t we include all players lution rules for the internal states [20, 21]. CVMs of thathaveatleastonelinkineachofthemultiplexlayers. this kind account for a wide class of phenomena ranging For more information on the topology and structure of from opinion-formation [22–26] to speciation in ecosys- the Pardus multiplex network see [1, 4]. Per construc- tems [27, 28]. In an extension of the CVM to multiplex tion, each layer has the same average number of nodes networks (MCVM) nodes have the same internal states N =3.1(0.2)·103. Numbersinbracketsdenotestandard in each layer and it is assumed that the rewiring dy- deviations. Table I shows results for the average number namics takes place on a different time-scale in each of of links in each layer, Lα. The trade network shows the the layers [29]. This MCVM has an anomalous tran- highest link density, the friendship and communication sition called shattered fragmentation in which one layer network have similar numbers of links. assumes a fragmented state whose topological properties It has been shown that for the given time-span the would be different under the same model parameters in three network layers α are in a stationary state in the a single layer CVM [29]. It has been shown that the sense that links are added and removed with compara- drivingforcebehindthistransitionistheasymmetrybe- ble rates. These rates are orders of magnitude larger tween rewiring rates in different network layers, i.e. the than the rates at which nodes are added or removed, see individual lifetime of links in each of the layers [29]. [6]. The dynamics within the network layers is therefore To reconcile the dynamics of the CVM with the em- dominated by rewiring processes. The rewiring rate p α pirical dominance of triadic closure, where a substantial is defined as the average value of the probabilities that a amountofnewlycreatedlinksinsocialnetworksconnect linkwillbeaddedorremoved,thatisrewired,inlayerα. nodesthatalreadysharecommonneighbors[4,6,30,31], TableIshowsresultsfortherewiringratesp inthethree α weproposeanoveltypeofVMinwhichtherewiringstep layers. p in the friendship network is orders of magni- α is carried out by a triadic closure process, and call it the tude smaller than in the communication and trade net- triadic closure voter model (TCVM). We study the dy- works. This can be understood by the difference in pro- namicsoftheTCVMonasingle-layerandonamultiplex cessesthatgoverntheinteractionsintheselayers. Inthe network(MTCVM).WeshowthattheMTCVMdisplays friendshipnetworkalinkpersistsafterithasbeenformed a novel fragmentation transition that is again different until the link is removed or one of the players leaves the fromshatteredfragmentationintheMCVM.Weinvesti- game. In the message and communication network, on gatewhetherthefragmentationbehavioroftheMTCVM theotherhand,alinkisonlyformedbetweentwoplayers is compatible with the community structure observed in if at least one interaction took place within the consid- Pardus multiplex network data. To understand the ex- ered time interval. This results in a substantially lower tent to which the microscopic dynamics of the model turnover of links in the friendship network than in the multiplex is compatible with the data, we compare re- other layers. We will therefore refer to the friendship sults for pairwise similarity measures of layers in terms layer as being slow and to the trade and message layers ofthepropertiesofnodes(states)andlinks(overlapand as being fast in terms of the average time between two degree). consecutive rewiring events in the given layer. Note that although friendship links have the longest survival time (i.e. lowestturnoverp ), thefriendshipnetworkhasalso α II. DATA AND METHODS the smallest number of links Lα. A. Data B. Community detection The Pardus dataset contains all actions of more than 380,000 players in a massive multiplayer online game. From the network layers Mα(t), for data and The players interact inan virtual, open-ended game uni- model, we identify the communities Cα(t) = verse to connect with other players to achieve self-posed {Cα(1,t),Cα(2,t),...,Cα(Nα,t)}, where the i-th c goals,suchasaccumulatingwealthandinfluence. Players community Cα(i,t) is the set with a number of nα(t) i can engage in three different types of cooperative inter- nodes within community i at time t. We use the actions. They can establish mutual friendship links, ex- OSLOM community detection algorithm [32], which 3 TABLEI:OverviewofcharacteristicsofthePardusmultiplex network layers. For each layer α we show the values of the rewiring probability p and the average number of links Lα. α The rewiring probability p is orders of magnitude smaller α for the friendship network, compared to communication and trade. Each layer has the same average number of nodes, N =3.1(0.2)·103. α friendship trade communication p 0.004(1) 0.27(1) 0.35(2) α Lα 1.5(0.2)·104 5.6(0.2)·104 1.9(0.3)·104 retrieves only statistically significant communities and which does not suffer from the so-called resolution limit problem (failure of the detection of small communities) of other approaches [33]. It also allows to detect the absence of community structure as well as homeless nodes, that do not belong to any community. We use the OSLOM implementation as provided by the authors FIG. 1: Community size distributions for the Pardus mul- for unweighted networks with a coverage parameter of 1 tiplex data (blue dots) for the friendship layer (A and C), and a standard significance threshold of p<0.1, [32]. the trade layer (B), and the communication layer (D). The friendship layer shows a decrease of frequencies of communi- ties show as a function of their size, whereas the trade and message layers show an additional peak at about 50 (dot- ted lines in B and D). These results are compared to the C. Components in the model community size distributions obtained from the model (red squares). For this comparison the three-layer multiplex from To understand the fragmentation behavior of the thedataisdecomposedintotwotwo-layermultiplexnetworks, TCVM we describe the organization of the model- the friendship-trade multiplex (top row) and the friendship- communication multiplex (bottom row). Model community networks into components by the following observables. Nα(t) is the number of components in network layer α sizedistributionsforthefriendshiplayerarecompatiblewith c the data. Note that the model shows a distinct peak for the attimet. WewillrefertothetimeaverageofNα(t)over c trade and communication networks that coincides with the T consecutivetime-stepsbydroppingthedependenceon peaks observed in the data. t, i.e. Nα ≡ 1 (cid:80) Nα(t). The size of the k-largest com- c T t c ponent at t is denoted Sα(t). The time average of the k k-largest component size, Sα, is again denoted by drop- k III. RESULTS ping the dependence on t. A. Community structure in the Pardus multiplex The time-averaged distribution functions for the com- D. Similarity measures munity sizes in the three network layers are shown in figs. 1(A)-(D). There is a clear discrepancy between the The similarity of the sets of links in two layers, distribution observed in the slow friendship layer when Mα(t) and Mβ(t), is measured by the Jaccard coef- compared to the trade and message networks, that are ficient J(α,β,t). Let Eα(β)(t) be the set of links in characterized by substantially larger rewiring rates. For Mα(β)(t). TheJaccardcoefficientisgivenbyJ(α,β,t)= the friendship layer the frequencies of community sizes |Eα(t)∪Eβ(t)|. Let us further denote the degree sequence are clearly a decreasing function in size (roughly follow- |Eα(t)∩Eβ(t)| ing a power-law), whereas there exist distinct peaks in of Mα(β)(t) by kα(β)(t) and the sequence of the ranks the distributions of community sizes in the trade and of the degrees by Rk(kα(β))(t). The degree correla- message layers. In both fast layers these peaks are cen- tion, ρ(kα(t),kβ(t)), is Pearson’s correlation coefficient tered around a community size of 50. betweenthedegreesequenceskα(t)andkβ(t). Similarly, the degree rank correlation, ρ(Rk(kα(t)),Rk(kβ(t))), is Pearson’s correlation coefficient between the degree rank sequences Rk(kα(t)) and Rk(kβ(t)). As before, we re- B. The Triadic Closure Voter Model (TCVM) fer to the time averages of J(α,β,t), ρ(kα(t),kβ(t)), and ρ(Rk(kα(t)),Rk(kβ(t))), by dropping the time depen- The standard binary-state CVM on a single network dence in the variables, respectively. as introduced in [16, 19] is given as follows. Each node, 4 i,isdescribedasatime-dependent,binary,internalstate Coevolving Voter Model with Triadic Closure on a Multiplex σi(t) ∈ {0,1} subject to the following update rule. (i) 2. Evolve layer as the CVM with TC. If as 3. Change state of Pick node i and one of its neighbors, j, at random. If 1. Pick a layer at random a result a node changed state, then.. the corresponding node in other layer the internal states of these nodes differ, σ (t) (cid:54)= σ (t), i j then (iia) with probability p the link between i and j is removed and a link between i and a different node k is formed. k is randomly chosen from the set of all nodes disconnected to, but in the same internal state as node FIG. 2: Schematic representation of the coevolving voter i, σ (t) = σ (t). If no such node k exists, the link is i k modelwithtriadicclosureonamultiplex(MTCVM).Wepick not re-wired. Otherwise, (iib) with probability 1 − p, a layer at random (step 1) and evolve it according to the dy- the state of node i is changed to σ (t). This model has j namics of the CVM with triadic closure (step 2). As a result one parameter, the rewiring rate p, which defines the the state of a node may change in both layers (step 3). preference of a node to re-wire the link over changing its state. We now introduce the triadic closure voter model (TCVM) on a single network. The TCVM is motivated by the empirical fact that links that connect nodes that share common neighbors are more likely to form than thatlayerbyusingtheupdaterulesfromtheTCVM,see links that do not connect such nodes, i.e. the process fig. 2. This introduces a co-evolution of the two layers of triadic closure [6, 30, 31]. In the TCVM the rewiring becausetheformationofnewlinksdependsontheinter- step(iib)oftheCVMisreplacedbythefollowingupdate nal state of nodes which is the same (!) in both layers rule. With the triadic closure probability, p , the new foreachofthenodes. Eachofthelayersthushasitsown tc linkismadebetweennodeiandadifferentnodelthatis re-wiring probability, p1 and p2, respectively. randomly chosen from the set of all nodes that share at least one common neighbor with i (but there is no con- The MTCVM displays a novel fragmentation transi- nectionbetweeniandl,yet). Ifnosuchnodel exists,no tion that is visible in the phase diagrams of the observ- rewiringtakesplace. Otherwise,withprobability1−ptc, ables S1α (size of largest component) and Ncα (number of we follow the rewiring rule from step (iib) of the CVM. components). Fig. 3 shows the phase diagrams of (a) The networkis initialized asa randomgraph withsize S1 and (b) N1 in layer 1 of the TCVM as a function of 1 c N and average degree µ = 4, which results in a net- the rewiring probabilities p and p . The results have 1 2 work that is initially connected. The initial distribution been averaged over 103 realizations of the final (absorb- of internal states is random, so that each node has the ing)configurationsofnetworksofsizeN =250. Consider same probability 1/2 to be in one of the two possible the case where layer 1 is connected to a static layer with states. Results for the dynamics and phase diagrams p =0. Withincreasingp thelargestcomponentoflayer 2 1 of the TCVM on single networks are discussed in the 1shrinkstoavaluearound0.5,similartothesingle-layer supplementary information, where it is shown that the case. N , on the other hand, increases by increasing p c 1 systemundergoesafragmentationtransitionatacritical in the same way as S decreases. This means that with 1 rewiringratepc. Forp<pc,thenetworkfreezesintoone increasingp1nodesleavethelargestcomponentandform giantcomponentwithallnodesinthesamestate,i.e. the smallorisolatedcomponentsoftheirown(andnotasec- system reaches consensus. For p>pc, the network splits ond, large component), i.e. Nc increases. This process into two components of roughly equal size, but differ- has been called shattered fragmentation [29]. From the ing internal states (one component is composed of nodes phase diagrams in fig. 3 it follows by symmetry that in with σi(t)=0, the other with σi(t)=1). In this regime the static layer 2 the nodes remain in one giant compo- theinternalstatesinitiallypresentinthesystemarepre- nent as layer 1 undergoes this shattered fragmentation. served,butthosewhoholdthembecomesegregatedfrom each other. Such fragmentation at high rewiring rates is Note that this fragmentation transition in the typical for a range of dynamical and evolution rules [21]. MTCVM is different from the fragmentation transition For the single layer case, this fragmentation transition is of the MCVM. The MCVM can be recovered by setting largelyindependentofthetriadicclosureprobability,p . tc p = 0 in both layers and by introducing an additional In the following we set p =1. tc tc parameter, the multiplexity q. In the MCVM both lay- ers contain N nodes, but only a fraction qN nodes exist in both layers, i.e. the internal state of the remaining C. The TCVM on multiplex networks (MTCVM) (1−q)N nodes depends only on the dynamics in their own layer. The MCVM also displays a shattered frag- We now study the TCVM on a multiplex network, the mentation transition that is, however, only encountered MTCVM, by joining two networks that both follow the below a critical value of q, q < q < 1. Under triadic c update rules of the TCVM. The multiplex evolves by, closure, partial multiplexing (i.e. q < 1) is no longer first,pickingalayerrandomlyand,secondly,byevolving required to see shattered fragmentation. 5 data,wewouldexpectfromtheMTCVMthatthefriend- ship layer (pfriend = 0.004(1)) shows one large compo- nent whereas the trade (ptrade = 0.27(1)) and commu- nication (pcomm =0.35(2)) layers display fragmentation. Indeed, we observe for the communities in, both, data and model for the friendship layer a roughly power-law- like size distribution with a small number of very large communities, whereasthetradeandmessagelayersfrag- ment into a large number of smaller communities with a (a)S1/N (b)N1/N peak centered at around 50. Data and model show the 1 c same behavior in terms of fragmentation into communi- ties of various sizes. FIG.3: ShatteredfragmentationintheMTCVM.Phasedia- grams for (a) fraction of nodes in the largest component, S1, 1 TostudywhetherthedynamicsoftheMTCVMisable and(b)numberofcomponentsN1 relativetothesystemsize c todescribetheobservedsimilaritiesbetweenpairsofnet- N are shown as a function of the re-wiring probabilities p 1 worklayersinthedata,weintroduceacalibratedversion and p , respectively. The system undergoes a fragmentation 2 of the MTCVM. We model the friendship-trade and the transitionwhere,withincreasingp ,layer1splitsintoalarge 1 number of small components. friend-communicationmultiplexeswithcorrespondingpα and initial conditions that are given by snapshots of the respective data layers at t = 100d. For the friendship- 1 communication multiplex the absorbing state was typi- D. The MTCVM versus Pardus data cally reached after t ∼ 105, the friendship-trade multi- plex did not do so within any reasonable time, i.e. for One of the challenges when comparing the theoretical at least several orders of magnitude of simulation time. results with data is that the data contains three network Therefore the friendship-trade multiplex was compared layers, whereas, for simplicity, the model deals with only tosnapshotstakenattimesrangingoverseveralordersof two layers. We therefore decompose the three-layer mul- magnitude, namely at simulation times t=103,104,105. tiplex network into two two-layer networks. The most In the data we found substantially higher levels of sim- reasonable choices for this decomposition is to consider, ilarity in terms of the Jaccard coefficients, degree corre- both, the friendship-trade and the friendship-message lations, and rank degree correlations than in the model. multiplex networks. Both of these two-layer multiplexes This can be understood by the fact that the MTCVM consistthenofafastandaslowlayerintermsofrewiring doesnotcontainanymechanismthatexplicitlyincreases rates pα. We further assume that the model internal the similarity of layers, such as by copying one link from states, σi(t), encode a hidden propensity of the players one layer to the other. Such an inter-layer link corre- to interact with each other. That is, upon meeting two lation mechanism can be easily added to the MTCVM: playersiandj willbemorelikelytocooperatewitheach In the rewiring step a probability p is introduced to sim other if they have the same internal and not directly ob- re-wire the link to another node in the same state to servable states. which the node is already connected in the other layer. The community size distributions obtained from the We find that by introducing even a small modification model agrees well with the data. In fig. 1 we show the of this type (p = 0.1) we are able to account for the sim frequency of community sizes observed from 1000 real- observed values of the Jaccard similarity, degree corre- izations using N = 3100 and the rewiring rates p of lations, and degree rank correlations, which are shown α the two layers as measured for the respective layers in in fig. 4 for data and model. Although the friendship- the data and compare these results to the data. Re- trade multiplex has not reached its absorbing state in sults are shown for the friendship-trade multiplex (top thesesimulations,thevarianceofthesimilaritymeasures row), namely (A) friendship and (B) trade, and for the shows that they do not considerably change over time. friendship-communication multiplex (bottom row), (C) The model exhibits the same trends as seen in the data, friendship and (D) communication. In both model mul- withtheoverlapbetweendataandmodelbeinghigherin tiplexes the frequencies of community sizes decreases as the friend-trade multiplex than the friend-message mul- a function of their size in strong resemblance to results tiplex, in particular for the degree correlation and the observed in the data. For the trade and communica- degree rank correlation. This shows that the modified tion layers, respectively, we also observe a clear peak in co-evolutionary dynamics of the MTCVM preserves the the frequencies of community sizes that coincides with observed similarities between pairs of layers already for the peaks observed in the data around a community size a very small probability p to “copy” a link from one sim of 50. Note that here we compare communities in the layertotheotherone. Wehaveconfirmedthatthisvalue data to communities in the model (and not to compo- of p is indeed small enough that the community size sim nents). Clearly, the fragmentation behavior into com- distributions are unaltered by this inter-layer link cor- ponents in the model is closely related to its commu- relation modification. This link-copying mechanism has nitystructure. Giventherewiringprobabilitiesp inthe also no substantial impact on the phase diagrams of the α 6 markably, we find that the power-law like distribution of community sizes is found in a layer with a very small re- wiringrate,whereaslayerswiththecentereddistribution are characterized by rates that are orders of magnitude higher. To understand these empirical findings we proposed a generalizationoftheco-evolutionaryvotermodelonmul- tiplex networks which incorporates the process of triadic closure, the MTCVM. This process has been shown to be crucial in modeling the structure formation of indi- vidual layers in the Pardus society [6]. We studied the phase diagram of the new model and found that it ex- hibits an anomalous fragmentation transition for multi- plex networks that makes the model interesting in its ownright. Thistransitionischaracterizedbyabreak-up of the largest component of a network layer into a large number of small components. Intriguingly, the crucial parameters of the model turn out to be the differences oftime-scalesonwhichthelinkre-wiringdynamicstakes place in the individual layers. When the model is cali- FIG. 4: Similarity between pairs of multiplex layers for data brated to mimic the Pardus data on two different two- (blue) and model (red). We show the Jaccard coefficient of layer multiplex networks, community size distributions theedgesetsofthefriendship-communicationmultiplex(left) are perfectly compatible with those found in the data. and the friendship-trade multiplex (right), together with the degree correlation ρ(kα,kβ) and the degree rank correlation In particular the model confirms that slow layers in ρ(Rk(kα),Rk(kβ)). The model follows the similarities found terms of the time-span between two re-wiring events, in the data, with the overlap between data and model being show a power-law-like distribution of community sizes, higher in the friendship-trade multiplex than the friendship- whereasthefastlayersdisplayanadditionalpeakaround communication multiplex. community sizes of 50. This means that the empirical communitystructureofthePardusvirtualsocietyindeed resembles the fragmentation behavior predicted by the model, since the mechanism is similar to a random link- MTCVM. Note that for these results the model layers ingprocess(i.e. atriadicclosureprobability, p , smaller tc only differ in their re-wiring rates (but not, for instance, than one). As already discussed, the phase diagrams are in their degree), so that these results can only be at- largely independent of such small variations of p . tc tributed to the multiplex interaction of dynamics on dif- ferenttime-scales. Wefurtherconfirmedforanextended and calibrated version of the MTCVM that node- and IV. DISCUSSION link-based similarities between two pairs of layers in the data are indeed in good agreement with results from the We investigated the dynamical origins of the commu- model. Theseresultssuggestthatthedynamicaloriginof nity structure of societies represented as dynamical mul- the community structure of societies can be understood tiplex networks. In empirical data from the large-scale through the interplay of triadic closure processes taking online game society Pardus we observed substantial dif- place on different time-scales, which manifests itself in ferences in the community structures of individual net- the phenomenon of shattered fragmentation. Whether work layers of this multiplex. While one layer is char- these results hold for empirical data in real-world soci- acterized by a small number of large communities and eties remains to be seen. a power-law-like distribution of community sizes, in the other layers we find a peak of communities of interme- Acknowledgments: We acknowledge financial support diate size around 50. We found that the time-scales on from FP7 projects LASAGNE, agreement no. 318132, which the link dynamics takes place in the various net- MULTIPLEX, agreement no. 317532, and the Austrian work layers differ by several orders of magnitude. Re- Science Fund FWF, no. KPP23378FW. [1] Szell, M., Lambiotte, R., and Thurner, S. Proc. Natl. Zanin, M. Physics Reports 544, 1–122 (2014). Acad. Sci. USA 107(31), 13636–13641 June (2010). [3] Kivela¨, M., Arenas, A., Barthelemy, M., Gleeson, J. P., [2] Boccaletti, S., Bianconi, G., Criado, R., del Genio, C., Moreno,Y.,andPorter,M.A. Journal of Complex Net- Go´mez-Garden˜es, J., Sendin˜a-Nadal, I., Wang, Z., and works 3(2), 203–271 (2014). 7 [4] Szell, M. and Thurner, S. Social Networks 39, 313–329 [32] Lancichinetti, A., Radicchi, F., Ramasco, J. J., andFor- (2010). tunato, S. PLoS ONE 6, e18961 April (2011). [5] Davidsen, J., Ebel, H., and Bornholdt, S. Physical Re- [33] Fortunato,S.andBarth´elemy,M. Proc. Natl. Acad. Sci. view Letters 88(12), 128701–5 (2002). USA 104, 36–41 (2007). [6] Klimek, P. and Thurner, S. New Journal of Physics [34] Diakonova, M., Egu´ıluz, V. M., and San Miguel, M. 15(6), 063008 (2013). ArXiv e-prints November (2014). [7] Girvan,M.andNewman,M.E.J. Proc.Natl.Acad.Sci. USA 99(12), 7821–7826 (2002). [8] Fortunato, S. Phys. Rep. 486, 75–174 (2010). [9] Hill, R. A. and Dunbar, R. I. M. Human Nature 14, 53–72 (2003). [10] Fuchs, B., Sornette, D., and Thurner, S. Scientific Re- ports 4(6526) (2014). [11] Dunbar, R. I. M. Behavi. and Brain Sci. 16, 681–735 (1993). [12] Szell,M.,Sinatra,R.,Petri,G.,Thurner,S.,andLatora, V. Scientific Reports 2, 457 (2012). [13] Thurner, S., Szell, M., and Sinatra, R. PLoS ONE 7, e29796 (2012). [14] Szell, M. and Thurner, S. Scientific Reports 3, 1214 (2013). [15] Holley, R. A. and Liggett, T. M. Ann. Prob. 3(4), 643– 663 August (1975). [16] Vazquez, F. and Egu´ıluz, V. M. New Journal of Physics 10(6), 063011 (2008). [17] Gross,T.andBlasius,B. Proc.R.Soc.Interface5,259– 271 March (2008). [18] Vazquez,F. InDynamicsOnandOfComplexNetworks, Volume 2, Mukherjee, A., Choudhury, M., Peruani, F., Ganguly, N., and Mitra, B., editors, Modeling and Sim- ulation in Science, Engineering and Technology, 89–107. Springer New York (2013). [19] Vazquez, F., Egu´ıluz, V. M., and San Miguel, M. Phys. Rev. Lett. 100, 108702 March (2008). [20] Zimmermann, M. G., Egu´ıluz, V. M., and San Miguel, M. Economics with Heterogeneous Interacting Agents, volume 503 of Lecture Notes in Economics and Mathe- matical Series, 73–86. Springer (2001). [21] Zimmermann, M. G., Egu´ıluz, V. M., and San Miguel, M. Phys. Rev. E 69, 065102 June (2004). [22] Egu´ıluz,V.M.,Zimmermann,M.G.,Cela-Conde,C.J., and San Miguel, M. Am. J. Sociol. 110(4), 977–1008 (2005). [23] Vazquez,F.,Gonza´lez-Avella,J.C.,Egu´ıluz,V.M.,and SanMiguel,M. Phys.Rev.E76,046120October(2007). [24] Couzin, I. D., Ioannou, C. C., Demirel, G., Gross, T., Torney, C. J., Hartnett, A., Conradt, L., Levin, S. A., and Leonard, N. E. Science 334(6062), 1578–1580 (2011). [25] Zschaler, G., Bo¨hme, G. A., Seißinger, M., Huepe, C., and Gross, T. Phys. Rev. E 85, 046107 Apr (2012). [26] Carro, A., Vazquez, F., Toral, R., and San Miguel, M. Phys. Rev. E 89, 062802 Jun (2014). [27] Dieckmann, U. and Doebeli, M. Nature 400, 354–357 July (1999). [28] Cantor, M. and Whitehead, H. Phil. Trans. R. Soc. B 368, 1618 (2013). [29] Diakonova,M.,Egu´ıluz,V.M.,andSanMiguel,M.Phys. Rev. E 89, 062818 June (2014). [30] Simmel, G. Soziologie: Untersuchungen u¨ber die For- menderVergesellschaftung. Duncker&Humblot,Berlin, (1908). [31] Heider, F. The Journal of Psychology: Interdisciplinary and Applied 21, 107–112 (1946). 8 1.0 0.241.0 1.0 Tmax1.02.40 1.0 N=250 N=2t50imNe=,250plotted in the middle panel of fig. 5. We associate 0.8 00..12810.8 0.8 0.812..8100 0.8 NN==5100000 NN==51i0000t0sNNp==e510000a0k, Tmax, with the finite-size approximation of the absorbing transition. Fig. 5 shows that increasing the 0.6 0.150.6 0.6 0.61.50 0.6 ptc00..24 000p...001tc69200..24 1.C01h.0patcra00c..t24eristicp tc00..24001...692000ptc00..24 NN=2=50250 01..80 Tmax 01..9064 01..80 Tmax 3305 Activity 0.03 0.80.8Time 0.30 NNNN==51==000051000000 0.88 25 0.00.0 0.2 0.4p0.6 0.8 1.0 0.000.00.0 0.2 p0tc.p4tc0.p60.60.60.000.0.8 10..002.00.00.000.400.p.200.00.60.40.20p.80.60.41.0p0.80.6 p1tc.0000.8..46 1.0 00..78p20tc00..46 1250 0.40.4 FIG. 5: Activity in the TCVM monoplex. Activity (left 0.64 10 panel) as measured in the asympt0o.20.t2ic value of the interface 0.2 S1 0.56 0.2 CNoummpboenre noft s 5 densityaveragedoversurvivingrea0.l00i.z0ationsinanensembleof 103 elements,foranetworkwithN 0=.00.0500.020..2 T0.h40.4eppc0h.60.a6ra0.c80.t8er1i.01s.0tic 0.00.0 0.2 0.4 p 0.6 0.8 1.0 0.48 0.00.0 0.2 0.4 p 0.6 0.8 1.0 0 time,i.e. theaveragetimeuntilabsorption,forthesamesys- tem(centerpanel),normalizedbysystemsize. Themaximum FIG. 6: Fragmentation in the TCVM monoplex. Each point (traced in dark circles) is associated with the fragmentation isanaverageoverabsorbingconfigurationsof103 realizations transition. Right panel: The variation of the maximum of ofthenetworkwithN =500. Leftpanel: Fractionofnodesin characteristic time for various system sizes, computed from the largest component, S ; Right panel: the number of com- 1 ensembles with 104 elements. ponents. ThedottedlinedenotedT givesanindicationof max the absorbing/fragmentation transition. V. SUPPLEMENTARY INFORMATION 1. Further Results on the Co-evolving Voter Model with fraction of triadic closure decreases activity, and brings Triadic Closure (TCVM) down the critical rewiring pc. In other words, limiting therangeofrewiringcausessystemstofreezeforaneven lower rewiring range. The right panel of fig. 5, which Triadic closure in the monoplex. A finite mono- traces the effect of system size of p , suggests that the plex with standard, unlimited rewiring range (p = 0) c tc absorbing transition does not exist when p = 1; large always reaches an absorbing state. This holds for the tc systems rewiring with only triadic closure do not sus- TCVM model except for the extreme p = 1,p = 1 tc tain a constant level of activity, and will always reach an case. Here, limiting the rewiring range introduces dy- absorbing state in finite time. namical traps, where ‘active’ links between nodes in dif- feringstatescontinuetoexistastheycannotbechanged. The corresponding fragmentation diagram, overlayed Thishappenswhentheactivelinkbetweeniandj isalso bythetrendofT computedearlier,(fig.6)showsthat max both ith and jth only active link. An isolated node pair for the vast majority of parameters in the TCVM the indifferingstatesisonesuchexample. Clearlyaslongas absorbing and the fragmentation transitions once more p <1 or p=1 this trap is avoided as either one of the coincide: activesystems(p<p )willreachanabsorbing tc c nodesrewirestosomeonefurtheraway,oreventuallyone state with one giant component with all nodes in the ofthenodeschangesstates. Existenceofdynamicaltraps samestate,andfrozensystems(p>p )willsplitintotwo c isjustoneoftheconsequencesofalimitedrewiringrange. components corresponding to the two initially present Another implication is that once a node is isolated, it states (this is corroborated by examining the size of the cannotbebroughtbackintoacomponent,andhencethe second largest component, figure not shown). The novel number of isolated components is non-decreasing. aspect is the different nature of fragmentation observed Activityinthemodelismeasuredbytheinterfaceden- for large values of p , and maximized at p . There the tc c sity, i.e. the fraction of active links which are the ones decreaseinthesizeofthelargestcomponentisnolonger connecting nodes in different states. Figure 5 shows the compensated only by the growth of the second largest activity of the system in terms of asymptotic of the in- component, but is accompanied by an increase in the terface density averaged over surviving runs. When the number of small components that tend to be isolated interface density is zero the system is in an absorbing nodes or pairs of isolated nodes. This is an example state. The p =0 limit corresponds to the CVM ([19]), of shattered fragmentation: topologies with one or two tc where activity decreases with rewiring and falls to zero giant components and a multiplicity of components of around p , defined in the limit of infinite systems. This negligible size. This was first observed in the CVM on a c critical rewiring denotes the absorbing transition and is multiplex [29] for incomplete interlayer connectivity q < accompanied by the critical slowing down of the time it 1, and in [34] for the CVM on a monoplex with noise. takes for the system to reach an absorbing state. The Hereweseethatasimilareffectcanbecausedbylimiting average of such times is identified with the characteristic the scope of rewiring.