Scalable community detection for social networks

Author

Prat Pérez, Arnau

Director

Larriba Pey, Josep Lluís

Codirector

Domínguez Sal, David

Date of defense

2016-03-03

Pages

137 p.



Department/Institute

Universitat Politècnica de Catalunya. Departament d'Arquitectura de Computadors

Abstract

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).


Moltes aplicacions reals es poden modelar de manera intuïtiva mitjançant grafs. on els nodes representen entitats de la xarxa, i les arestes les relacions entre aquestes. D'aquesta manera som capaços d'entendre en detall com les entitats interactuen. Una de les particularitats d'aquests grafs, és que les entitats que els conformen s'organitzen mitjançant comunitats. Una comunitat es defineix informalment com a un conjunt de nodes amb un nombre d'arestes internes molt més gran que les que hi ha entre els nodes de la comunitat i la resta de nodes del grat. Per exemple, en el cas d'una xarxa social, persones amb característiques similars s'agrupen en comunitats. La cerca de comunitats ha adquirit un gran interès en la comunitat científica durant els darrers anys, degut a la infinitat d'aplicacions que tenen. Per exemple, en una xarxa social, les comunitats ens donen informació sobre les persones que les formen, tan sols mirant les relacions que les uneixen. Això s'usa, per exemple, per dirigir campanyes de màrqueting, recomanar productes, predir qui es connectarà amb qui, etc. Degut al seu interès, existeixen una gran quantitat d'algorismes per a la cerca de comunitats en xarxes. Els mes coneguts son aquells basats en una mètrica anomenada modularitat, tot i que també n'hi ha basats en camins aleatoris, o en processos epidèmics. El problema d'aquests algorismes es que estan pensats per a ser genèrics, ignorant les particularitats que conformen cada tipus xarxa. Com a resultat, ens trobem en que sota certes circumstancies, la seva qualitat se’n veu penalitzada, tot trobant conjunts de nodes que no poden ser considerats comunitats. Aquesta tesi proposa una metodologia alternativa, anomenada "disseny específic del domini", alhora de dissenyar algorismes i mètriques per a la cerca de comunitats. La metodologia es centra en definir quines propietats estructurals haurien de tenir les comunitats en una xarxa d'un domini concret, i un seguit de propietats de comportament que haurien de complir els algorismes que les troben. En el nostre cas, ens centrem en les Xarxes socials, i definim tres propietats estructurals (Sensibilitat estructural, Resistència als ponts i Resistència als nodes-tall) i tres propietats de comportament (Adaptiva, Independent de l'escala i Cohesió lineal). Arrel d'aquestes propietats, proposem una mètrica, anomenada Weighted Commuity Clustering (WCC), que ens qualifica com de bona és una classificació de nodes d'un graf en comunitats. La mètrica fa us del triangle com a indicador bàsic de la presència d'una relació forta entre dues persones d'una xarxa social. Es demostra formalment que la mètrica compleix les propietats esmentades, garantint així uns mínims de qualitat, a diferencia de les propostes de l'estat de l'art. Tanmateix, mitjançant un anàlisi empíric, demostrem que les comunitats amb un alt WCC tenen unes característiques estructurals esperades en una bona comunitats per a xarxes socials. Aquesta tesi també proposa un algorisme de cerca de comunitats basat en el WCC, anomenat Scalable Community Detection (SCD). A mes a mes, per tal d'aprofitar els darrers avenços en microprocessadors, l'algorisme esta dissenyat per ser inherentment paral·lel. Demostrem mitjançant una sèrie de grafs reals socials, que SCD es capaç de detectar comunitats amb una qualitat sense precedents, sent un dels algorismes mes ràpids capaç de trobar comunitats en grafs de milers de milions d'arestes en poques hores. La tesi també inclou un estudi estadístic de les característiques estructurals que tenen els grups que formen les entitats en diversos grafs reals, i les comparem amb grafs generats sintèticament per tal de validar la correctesa dels seus generadors, mostrant que alguns d'aquests últims disten molt d'assemblar-s'hi. Finalment es realitza un estudi de com implementar el comptatge de triangles en grafs, en una arquitectura many-core

Subjects

004 - Computer science and technology. Computing. Data processing

Knowledge Area

Àrees temàtiques de la UPC::Informàtica

Documents

TAPP1de1.pdf

3.071Mb

 

Rights

L'accés als continguts d'aquesta tesi queda condicionat a l'acceptació de les condicions d'ús establertes per la següent llicència Creative Commons: http://creativecommons.org/licenses/by/4.0/
L'accés als continguts d'aquesta tesi queda condicionat a l'acceptació de les condicions d'ús establertes per la següent llicència Creative Commons: http://creativecommons.org/licenses/by/4.0/

This item appears in the following Collection(s)