Communities in Social Networks: Modelling, Analysis, and Detection

The main subject of this thesis is to study the structure of communities in social networks and to develop community detection algorithms that are highly efficient for real-world graphs. In particular, we are interested in understanding the formation process of a community and its emerging structural patterns. With the knowledge of such structures, it becomes possible to devise efficient community detection algorithms that are faster than the conventional clustering algorithms for generic graphs. We propose a mathematical model for information communities where members interact via the production and consumption of content. Each member allocates their time between production and consumption with the objective of maximizing their individual utilization. We define the community as "stable and efficient" when a Nash equilibrium is reached while the social welfare is maximized. We analyze the conditions for forming a stable and efficient community and the results show that the structure with a "small core of celebrity producers" is optimal among all structures considered. Based on the insights from the analysis, we devise a community detection algorithm for user-item graphs, taking advantage of the structure that assumes the existence of cores. Our algorithm exhibits a sub-quadratic time complexity which is significantly lower than the cubic-time complexity of state-of-the-art quasi-clique based algorithms. The algorithm dramatically reduces the amount of time needed to process the entire graph, making it practical for large-scale inputs. The performance of the algorithm is experimentally evaluated with various real-world datasets. As another attempt to study community structures via mathematical modelling, we model the dynamics of the gender ratio in a workforce as a recursive process characterized by two factors: how strongly a potential candidate is influenced by the observed gender ratio (Factor #1) and how strongly an employer prefers one gender over the other (Factor #2). Our analysis results show that, to avoid the gender ratio converging to single-gender dominance, there are specific requirements on the values of Factor #1 and Factor #2. While not attempting to be comprehensive, this analysis provides some fine-grained insights for future studies on related subjects.Ph.D