Modeling online social networks using Quasi-clique communities

[摘要] ENGLISH ABSTRACT: With billions of current internet users interacting through social networks, the needhas arisen to analyze the structure of these networks. Many authors have proposedrandom graph models for social networks in an attempt to understand and reproducethe dynamics that govern social network development.This thesis proposes a random graph model that generates social networks usinga community-based approach, in which users' affiliations to communities are explicitlymodeled and then translated into a social network. Our approach explicitlymodels the tendency of communities to overlap, and also proposes a method fordetermining the probability of two users being connected based on their levels ofcommitment to the communities they both belong to. Previous community-basedmodels do not incorporate community overlap, and assume mutual members ofany community are automatically connected.We provide a method for fitting our model to real-world social networks and demonstratethe effectiveness of our approach in reproducing real-world social networkcharacteristics by investigating its fit on two data sets of current online social networks.The results verify that our proposed model is promising: it is the firstcommunity-based model that can accurately reproduce a variety of important socialnetwork characteristics, namely average separation, clustering, degree distribution,transitivity and network densification, simultaneously.

[发布机构] Stellenbosch University