ACO-based clustering for Ego Network analysis

Abstract

The unstoppable growth of Social Networks (SNs), and the huge number of connected users, have become these networks as one of the most popular and successful domains for a large number of research areas. The different possibilities, volume and variety that these SNs offer, has become them an essential tool for every-day working and social relationships. One of the basic features that any SN provides is to allow users to group, organize and classify their connections into different groups, or “circles”. These circles can be defined using different characteristics as roommates, workmates, hobbies, professional skills, etc. The problem of finding these circles taking into account the variety, volume and dynamics of these SNs has become an important challenge for a wide number of Computer Science areas, as Big Data, Data Mining or Machine Learning among others. Problems related to pre-processing, fusion and knowledge discovering of information from these sources are still an open question. This paper presents a new Bio-inspired method, based on Ant Colony Optimization (ACO) algorithms, that has been designed to find and analyze these circles. Given any user in a network, the new method is able to automatically determine the different users that compose his/her groups or circles of interest, so the network will be clustered into different components based on the users profiles and their dynamics. This algorithm has been applied to Ego Networks where the node centering the network (called “Ego”) represents the user being studied. In this work two different ACO algorithms, that differ in the source of information used to perform the community finding tasks, have been designed. The first ACO algorithm uses the information extracted from the topology of the network, whereas the second one uses the profile information provided by users. The proposed algorithms are able to detect the different circles in three popular Social Networks: Facebook, Twitter and Google+. Finally, and using several databases from previous SNs, an experimental evaluation of our methods has been carried out to show how the algorithms are currently working.

Publication
Future Generation Computer Systems
Antonio Gonzalez-Pardo
Antonio Gonzalez-Pardo
PhD Computer Science

Lecturer at the Computer Science Department. Main research interests are related to Computational Intelligence and Metaheuristics applied to Social Networks Analysis, and the optimization of graph-based problems.