Quantifying social group evolution Gergely Palla1, Albert-László Barabási2 and Tamás Vicsek1,3 1Statistical and Biological Physics Research Group of HAS, Pázmány P. stny.1A, H-1117 Budapest, Hungary, 2Center for Complex Network Research and Department. of Physics, University of Notre Dame, IN 46566, USA. 3Department. of Biological Physics, Eötvös University, Pázmány P.stny.1A, H-1117 Budapest, Hungary. The rich set of interactions between individuals in the 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-optimisation of the society as a whole [17,18,19,20,21,22]. We have developed a new algorithm based on clique percolation [23,24], that allows, for the first time, to investigate the time dependence of overlapping communities on a large scale and as such, to uncover basic relationships characterising 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 longer if they are capable of dynamically altering their membership, suggesting that an ability to change the composition results in better adaptability. The behaviour of small groups displays the opposite tendency, the condition for stability being that their composition remains unchanged. We also show that the knowledge of the time commitment of the members to a given community can be used for estimating the community's lifetime. These findings offer a new view on the fundamental differences between the dynamics of small groups and large institutions. The data sets we consider contain the monthly roster of articles in the Los Alamos cond-mat archive spanning 142 months, with over 30000 authors [25], and the complete 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 type 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 (time-dependent) links. The extraction of the changing link weights from the primary data is described in the 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: due to its bipartite nature, the collaboration network is quite dense and the overlap between communities is very significant, whereas in the phone-call network the communities are less interconnected and are often 1separated by one or more inter-community nodes/edges. Indeed, while 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 is dominated by single links, while the co-authorship data has 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 records the results of a long term collaboration process. These fundamental differences suggest that any common features of the community evolution in the two networks represent potentially generic characteristics of community formation, rather than being rooted in the details of the network representation or data collection process. The communities at each time step were extracted using the Clique Percolation Method [23,24] (CPM). The key features of the communities obtained by the CPM are that (i) their members can be reached through well connected subsets of nodes, and (ii) the communities may overlap (share nodes with each other). This latter property is essential, since most networks are characterised by overlapping and nested communities [6,23]. As a first step, it is important to check if the uncovered communities correspond to groups of individuals with a shared common activity pattern. For this purpose we compared the average weight of the links inside communities, wc, to the average weight of the inter-community links, wic. For the co-authorship network wc/wic is about 2.9, while for the phone-call network the difference is even more significant, since wc/wic≈5.9, indicating that the intensity of collaboration/communication within a group is significantly higher than with contacts belonging to a different group [26,27,28]. While for co-authors the quality of the clustering can be directly tested by studying their publication records in more detail, in the phone-call network personal information is not available. In this case the zip-code and the age of the users provide additional information for checking the homogeneity of the communities. According to Fig.1c the <nreal>/<nrand> ratio is significantly larger than 1 for both the zip-code and the age, indicating that communities have a tendency to contain people from the same generation and living in the same neighbourhood (<nreal> is the size of the largest subset of people having the same zip code averaged over time steps and the set of available communities, while <nrand> represents the same average but with randomly selected users). It is of specific interest that <nreal>/<nrand> for the zip-code has a prominent peak at s≈35, suggesting that communities of this size are geographically the most homogeneous ones. However, as Fig.1d shows, the situation is more complex: on average, the smaller communities are more homogeneous in respect of both the zip-code and the age, but there is still a noticeable peak at s≈30-35
View Full Document
Unlocking...