Advances in Social Circles

Abstract

[EN] Social circles arised out of a need to organize the contacts in personal networks, within the current social networking services. The automatic detection of these social circles still remains an understudied problem, and is currently attracting a growing interest in the research community. This task is related to the classical problem of community detection in networks, albeit it presents some peculiarities, like overlap and hierarchical inclusion of circles. The usual community detection techniques cease to be the most appropiate, due to these characteristics. Prediction is performed from two data sources: the network graph and node attributes corresponding to users’ profile features. In this thesis, new approaches to this task are discussed and the results obtained from a thorough experimentation are presented. We provide a review of the state-of-the-art in the fields of community detection in graphs, community detection in social networks and social circles detection. We describe the datasets employed in our experiments, both retrieved from Facebook, and we design a variety of feature representations, both from the structural network information and the users’ profile information. We define and comment the prediction techniques in which our work is based: multi-assignment clustering, restricted Boltzmann machines and k-means. We describe some evaluation measures that have been proposed for social circles detection, and provide a critical commentary of some of them, as they present some flaws which lead to degenerate optimal performance. The core of this work is the presentation of the experiments that we have designed, along with the obtained results. There are two blocks of experiments, depending on the prediction technique employed: the first block considers multi-assignment clustering, a clustering method allowing for the inclusion of an element into several different clusters; whereas the second block considers a two-step method in which the data samples are mapped by restricted Boltzmann machines before feeding a k-means algorithm. We provide a discussion of the results, which have been satisfactory and have led to the publication of two articles, while a third one is awaiting revision. Our work opens the door to several lines of future work.

[ES] Los círculos sociales han surgido de la necesidad de organizar los contactos en las redes personales, dentro de los servicios actuales de red social. La detección automática de estos círculos sociales es todavía un problema poco estudiado, y actualmente está atrayendo un interés creciente en la comunidad investigadora. Esta tarea está relacionada con el problema clásico de detección de comunidades en redes, aunque presenta ciertas peculiaridades, como el solape y la inclusión jerárquica de círculos. Los métodos habituales de detección de comunidades dejan de ser apropiados debido a estas características. La predicción se obtiene de dos fuentes de datos: el grafo de la red y atributos de nodo correspondientes a características de los perfiles de los usuarios. En esta tesis, se comentan nuevas aproximaciones a la tarea y se presentan los resultados obtenidos a partir de una investigación exhaustiva. Se proporciona una revisión del estado del arte en los campos de detección de comunidades en grafos, detección de comunidades en redes sociales y detección de círculos sociales. Se describen los conjuntos de datos utilizados en los experimentos, ambos extraídos de Facebook, y se diseñan diversas representaciones de los datos, tanto de la información estructural de la red como de la información procedente de los perfiles de los usuarios. Se definen y comentan las técnicas de predicción empleadas en nuestro trabajo: multi-assignment clustering, restricted Boltzmann machines y k-medias. Se describen algunas medidas de evaluación propuestas para la detección de círculos sociales y se incluye un comentario crítico sobre algunas de ellas, puesto que presentan algunos defectos conducentes a un comportamiento óptimo degenerado. El núcleo de este trabajo es la presentación de los experimentos que se han diseñado, junto con los resultados que se han obtenido. Dos grupos de experimentos se han llevado a cabo, dependiendo de la técnica de predicción empleada: en el primer grupo se ha utilizado el multi-assignment clustering, una técnica de análisis de conglomerados que permite la clasificación de un elemento en varios conglomerados diferentes; para el segundo grupo se ha utilizado un método en dos etapas por el que los vectores de datos se proyectan por medio de restricted Boltzmann machines antes de ser clasificados por un algoritmo k-medias. Se facilita un comentario de los resultados, que han sido satisfactorios y han llevado a la publicación de dos artículos, mientras un tercero está esperando la revisión. Nuestro trabajo abre nuevas líneas de trabajo futuro.