Understanding Evolution of Inter-Group Relationships Using Bipartite Networks

In online social systems, users with common affiliations or interests form social groups for discussing various topical issues. We study the relationships among these social groups, which manifest through users who are common members of multiple groups, and the evolution of these relationships as new users join the groups. Focusing on a certain number of the most popular groups, we model the group memberships of users as a subclass of bipartite networks, known as Alphabetic Bipartite Networks (α-BiNs), where one of the partitions contains a fixed number of nodes (the popular groups) while the other grows unboundedly with time (new users joining the groups). Specifically, we consider the evolution of the thresholded projection of the user-group bipartite network onto the set of groups, which accurately represents the inter-group relationships. We propose and solve a preferential attachment based growth model for evolution of α-BiNs, and analytically compute the degree distribution of the thresholded projection. We further investigate whether the predictions of this model can explain the projection degree distributions of user-group networks derived from several real social systems (Livejournal, Youtube and Flickr). The study also shows that the inter-group network is tightly knit, and there is an implicit semantic hierarchy within its structure, that is clearly identified by the method of thresholding. To the best of our knowledge, this is the first attempt to analytically model the dynamical relationships among groups in online social systems.