Departamento de Computación

Las comunidades son grupos de nodos densamente conectados y son estudiadas de manera estructural, sin embargo las redes sociales reales contienen atributos. Si se consideran ambos tipos de datos, un nodo pertenece a la misma comunidad que sus vecinos y estos son similares. Además los nodos pertenecen a múltiples grupos por lo que existen algoritmos enfocados a las comunidades sobrepuestas. Trabajos recientes mezclan la estructura y los atributos. Existen dos tipos de métodos: basados en modelo y basados en distancia. Los primeros, usan elementos probabilísticos y detectan comunidades como las reales pero requieren de conocimiento previo de la red y descuidan propiedades básicas. Los segundos, generalmente optimizan una medida basada en una o más propiedades, pero su aproximación a las comunidades reales no es buena. En esta tesis se propone un método mixto basado en modelo (RMOCA) y en distancia (BAS) para obtener las ventajas de ambos. El MOdelo de Regresiones para Comunidades en redes con Atributos (RMOCA) considera que dos vértices con una conexión tienden a pertenecer a la misma comunidad y que un nodo incluye a sus atributos a la comunidad para integrar posteriormente nodos con los mismos atributos. Se usa un modelo de regresiones con mínimos cuadrados para definir una función que es minimizada. Los resultados demuestran el incremento del RMOCA en similitud entre nodos y precisión a comunidad reales. Se propone QA como una medida de calidad de comunidades basada en atributos. Esta considera información estructural, importancia local y global de atributos, grado del nodo y densidad de atributo. QA es integrada a la conductividad y es balanceada (BAS). Estas medidas son usadas por el método mixto para mejorar las comunidades y generar comunidades sobrepuestas. La importancia global de los atributos es usada para seleccionar los mejores atributos y reducir la complejidad sin afectar la calidad de las comunidades. Los resultados muestran un incremento de la entropía y calidad en traslape de las comunidades detectadas con la expansión.

Abstract

Community is a group of vertices densely coneected. They are often studied structurally, nevertheless some real-world networks contain attributes. Those are important because a node is in the same community as its neighbors, but it should also share the community with similar nodes. A member of a social network belongs to multiple communities, so there methods to detect overlapping communities. Just recent works merge attributes and graph structure. There are two main methods: the model based and the distance based. The first ones are usually probabilistic and they find communities similar to the ground-truth communities but they require previous knowledge of the network and do not consider basic network properties. The second ones use measures based on one or more properties but there is not an approximation to the ground-truth communities. We propose a mixed method based on model (RMOCA) and distance (BAS) to get advantages of both process. Regression MOdel for Communities in Attributed networks (RMOCA) models that two vertices with a connection tend to be in the same community, and a node includes its attributes to the community in order to integrate nodes with same attributes. We used regression models with ordinary least squares to define a function that is minimized. Experimental results demonstrate mostly the entropy (attribute similarity) and purity (precision to recover ground-truth communities) improvement. We propouse QA, a community quality measure based on attributes. It stores structural information, local and global importance of attributes, node degree, and attribute degree. We integrate it with conductance to Balance Attributes and Structure (BAS). The measure is used by the mixed method to improve communities generating overlapping communities. The global importance of attributes is also used to rank attributes and to select the best ones to reduce the complexity. Experimental results shows better communities with the expansion of BAS and a time reduction with the pre-process without affecting the quality of the communities.