The rich set of interactions between individuals in society [1] [2] [3] [4] [5] [6] [7] results in complex community structure, capturing highly connected circles of friends, families or professional cliques in a social network 3, [7] [8] [9] [10] . Thanks to frequent changes in the activity and communication patterns of individuals, the associated social and communication network is subject to constant evolution 7, [11] [12] [13] [14] [15] [16] . Our knowledge of the mechanisms governing the underlying community dynamics is limited, but is essential for a deeper understanding of the development and self-optimization of society as a whole [17] [18] [19] [20] [21] [22] . We have developed an algorithm based on clique percolation 23, 24 that allows us to investigate the time dependence of overlapping communities on a large scale, and thus uncover basic relationships characterizing community evolution. Our focus is on networks capturing the collaboration between scientists and the calls between mobile phone users. We find that large groups persist for longer if they are capable of dynamically altering their membership, suggesting that an ability to change the group composition results in better adaptability. The behaviour of small groups displays the opposite tendency-the condition for stability is that their composition remains unchanged. We also show that knowledge of the time commitment of members to a given community can be used for estimating the community's lifetime. These findings offer insight into the fundamental differences between the dynamics of small groups and large institutions. The data sets we consider are (1) the monthly list of articles in the Cornell University Library e-print condensed matter (cond-mat) archive spanning 142 months, with over 30,000 authors 25 , and (2) the record of phone calls between the customers of a mobile phone company spanning 52 weeks (accumulated over two-week-long periods), and containing the communication patterns of over 4 million users. Both types of collaboration events (a new article or a phone call) document the presence of social interaction between the involved individuals (nodes), and can be represented as (timedependent) links. The extraction of the changing link weights from the primary data is described in Supplementary Information. In Fig. 1a , b we show the local structure at a given time step in the two networks in the vicinity of a randomly chosen individual (marked by a red frame). The communities (social groups represented by more densely interconnected parts within a network of social links) are colour coded, so that black nodes/edges do not belong to any community, and those that simultaneously belong to two or more communities are shown in red. The two networks have rather different local structure: the collaboration network of scientists emerges as a one-mode projection of the bipartite graph between authors and papers, so it is quite dense and the overlap between communities is very significant. In contrast, in the phone-call network the communities are less interconnected and are often separated by one or more inter-community nodes/edges. Indeed, whereas the phone record captures the communication between two people, the publication record assigns to all individuals that contribute to a paper a fully connected clique. As a result, the phone data are dominated by single links, whereas the co-authorship data have many dense, highly connected neighbourhoods. Furthermore, the links in the phone network correspond to instant communication events, capturing a relationship as it happens. In contrast, the co-authorship data considered. a, The co-authorship network. The figure shows the local community structure at a given time step in the vicinity of a randomly selected node. b, As a but for the phone-call network. c, The filled black symbols correspond to the average size of the largest subset of members with the same zip-code, AEn real ae, in the phone-call communities divided by the same quantity found in random sets, AEn rand ae, as a function of the community size, s. Similarly, the open symbols show the average size of the largest subset of community members with an age falling in a three-year time window, divided by the same quantity in random sets. The error bars in both cases correspond to AEn real ae/ (AEn rand ae 1 s rand ) and AEn real ae/(AEn rand ae 2 s rand ), where s rand is the standard deviation in the case of the random sets. d, The AEn real ae/s as a function of s, for both the zip-code (filled black symbols) and the age (open symbols). e, Possible events in community evolution. f, The identification of evolving communities. The links at t (blue) and the links at t 1 1 (yellow) are merged into a joint graph (green). Any CPM community at t or t 1 1 is part of a CPM community in the joined graph, so these can be used to match the two sets of communities.
REF monitor the stability of a community through their stationarity measure, based on the averaging of a custom auto-correlation function processed from the community appearance to its disappearance.
Quantifying social group evolution
Nature
Nature
Medicine Biology Mathematics Physics