Modeling online social networks using Quasi-clique communities
Date
2011-12
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Stellenbosch : Stellenbosch University
Abstract
ENGLISH ABSTRACT: With billions of current internet users interacting through social networks, the need
has arisen to analyze the structure of these networks. Many authors have proposed
random graph models for social networks in an attempt to understand and reproduce
the dynamics that govern social network development.
This thesis proposes a random graph model that generates social networks using
a community-based approach, in which users’ affiliations to communities are explicitly
modeled and then translated into a social network. Our approach explicitly
models the tendency of communities to overlap, and also proposes a method for
determining the probability of two users being connected based on their levels of
commitment to the communities they both belong to. Previous community-based
models do not incorporate community overlap, and assume mutual members of
any community are automatically connected.
We provide a method for fitting our model to real-world social networks and demonstrate
the effectiveness of our approach in reproducing real-world social network
characteristics 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 first
community-based model that can accurately reproduce a variety of important social
network characteristics, namely average separation, clustering, degree distribution,
transitivity and network densification, simultaneously.
AFRIKAANSE OPSOMMING: Met biljoene huidige internet-gebruikers wat deesdae met behulp van aanlyn sosiale netwerke kommunikeer, het die analise van hierdie netwerke in die navorsingsgemeenskap toegeneem. Navorsers het al verskeie toevalsgrafiekmodelle vir sosiale netwerke voorgestel in ’n poging om die dinamika van die ontwikkeling van dié netwerke beter te verstaan en te dupliseer. In hierdie tesis word ’n nuwe toevalsgrafiekmodel vir sosiale netwerke voorgestel wat ’n gemeenskapsgebaseerde benadering volg, deurdat gebruikers se verbintenisse aan gemeenskappe eksplisiet gemodelleer word, en dié gemeenskapsmodel dan in ’n sosiale netwerk omskep word. Ons metode modelleer uitdruklik die geneigdheid van gemeenskappe om te oorvleuel, en verskaf ’n metode waardeur die waarskynlikheid van vriendskap tussen twee gebruikers bepaal kan word, op grond van hulle toewyding aan hulle wedersydse gemeenskappe. Vorige modelle inkorporeer nie gemeenskapsoorvleueling nie, en aanvaar ook dat alle lede van dieselfde gemeenskap vriende sal wees. Ons verskaf ’n metode om ons model se parameters te pas op sosiale netwerk datastelle en vertoon die vermoë van ons model om eienskappe van sosiale netwerke te dupliseer. Die resultate van ons model lyk belowend: dit is die eerste gemeenskapsgebaseerde model wat gelyktydig ’n belangrike verskeidenheid van sosiale netwerk eienskappe, naamlik gemiddelde skeidingsafstand, samedromming, graadverdeling, transitiwiteit en netwerksverdigting, akkuraat kan weerspieël.
AFRIKAANSE OPSOMMING: Met biljoene huidige internet-gebruikers wat deesdae met behulp van aanlyn sosiale netwerke kommunikeer, het die analise van hierdie netwerke in die navorsingsgemeenskap toegeneem. Navorsers het al verskeie toevalsgrafiekmodelle vir sosiale netwerke voorgestel in ’n poging om die dinamika van die ontwikkeling van dié netwerke beter te verstaan en te dupliseer. In hierdie tesis word ’n nuwe toevalsgrafiekmodel vir sosiale netwerke voorgestel wat ’n gemeenskapsgebaseerde benadering volg, deurdat gebruikers se verbintenisse aan gemeenskappe eksplisiet gemodelleer word, en dié gemeenskapsmodel dan in ’n sosiale netwerk omskep word. Ons metode modelleer uitdruklik die geneigdheid van gemeenskappe om te oorvleuel, en verskaf ’n metode waardeur die waarskynlikheid van vriendskap tussen twee gebruikers bepaal kan word, op grond van hulle toewyding aan hulle wedersydse gemeenskappe. Vorige modelle inkorporeer nie gemeenskapsoorvleueling nie, en aanvaar ook dat alle lede van dieselfde gemeenskap vriende sal wees. Ons verskaf ’n metode om ons model se parameters te pas op sosiale netwerk datastelle en vertoon die vermoë van ons model om eienskappe van sosiale netwerke te dupliseer. Die resultate van ons model lyk belowend: dit is die eerste gemeenskapsgebaseerde model wat gelyktydig ’n belangrike verskeidenheid van sosiale netwerk eienskappe, naamlik gemiddelde skeidingsafstand, samedromming, graadverdeling, transitiwiteit en netwerksverdigting, akkuraat kan weerspieël.
Description
Thesis (MSc)--Stellenbosch University, 2011
Keywords
Social network analysis, Network modeling, Quasi-clique, Random graph models, Dissertations -- Computer science, Theses -- Computer science, Dissertations -- Mathematics, Theses -- Mathematics