Scalable Community Detection for Social Networks

Download or read book Scalable Community Detection for Social Networks written by Arnau Prat Pérez and published by . This book was released on 2016 with total page 137 pages. Available in PDF, EPUB and Kindle. Book excerpt: Many applications can be modeled intuitively as graphs, where nodes represent the entities and the edges the relationships between them. This way, we are able to better understand them and how they interact. One particularity of these graphs is that their entities are organized in modules called communities. A community is informally defined as a set of nodes more densely connected internally than externally. For instance, in the case of a social network, persons with similar characteristics are grouped forming communities. Community detection has become a hot topic in the research community during the last years, due to its amount of applications. For instance, in social networks, communities give information about the persons forming them, by just looking at the relationships linking them. This is used in directing marketing campaigns, recomendation systems or in link prediction. Because of the relevance of the problem, many community detection algorithms exist, which follow different strategies. Most of them are based on the well known modularity metric, though other techniques based on random walks and epidemics spreading also exist. The problem of existing algorithms is that they have been designed to be generic, completely ignoring the particularities of the graphs belonging to different domains. As a result and under certain circumstances, these algorithms tend to find groups of nodes with a lack of a community structure. This thesis, overcomes this issues by proposing a novel community detection algorithm design methodology, called Domain Specific Community detection. This methodology is based on defining a set of structural properties communities of a given domain should fulfill, as well a set of behavioral properties to be fulfilled by a community detection algorithm or metric. Based on this methodology, we propose a set of properties for the specific domain of social networks, consisting of three structural properties (Internal structure sensitive, Bridges resistant and Cut-Vertex resistant) and three behavioral properties (Scale independent, Adaptive and Lineal community cohesion). Based on the aforementioned properties, we design a novel community detection metric, called the Weighted Community Clustering (WCC), which takes the presence of a triangle as an indicator of a strong relation between two persons in a social network. We formally prove that WCC fulfills the proposed properties, thus guaranteeting that communities resulting from maximizing WCC have a minimum degree of quality. Moreover, we prove this last statement by performing an empirical analysis on communities from real graphs, showing that WCC is able to correclty rank these well. In this thesis we also propose an algorithm called Scalable Community Detection (SCD), based on the maximization of WCC. SCD is also designed with parallelism in mind, in order to take advantage of current many-core architectures. We show that SCD is to detect communities with an unprecedented quality, being its execution time faster than most of existing proposals, being able to process billion edge graphs in a few hours This thesis also includes a statistical study about the structural characteristics of the meta-groups found in several real graphs, comparing these to graph from two different synthetic graph generators. We show that communities produced by a synthetic graph generator commonly used in community detection research are very dissimilar to those found in real graphs. Finally, this thesis includes a study on how to implement a triangle counting algorithm on a modern many core architecture, more concretely the Intel Single Chip Cloud Computer (Intel SCC).