Master Thesis Defense on " Decentralized Diffusion-Controlled Algorithm for Community Detection" (Monday, Aug 28, 2:30pm)
Tid: Måndag 28 augusti 2017 kl 14:30 - 16:00
Plats: Ada Room
Student: Adrian Ramirez
Date and Time: 14:30, Monday, 28th August 2017
Place: Ada Room, 4th floor
Examiner: Sarunas Gridzijauskas
Supervisor: Amira Soliman
Title: Decentralized Diffusion-Controlled Algorithm for Community Detection
Opponents: Braulio Grana, Marco Dallagiacoma
Abstract
Community detection in graphs has been an important research topic for many fields. The aim of community detection is to extract from graphs those groups of nodes that present more connections between them than with the rest of the network. Extracting such groups at different scales can help understanding the global behaviour of the system. However, recent studies have shown that real-world graphs follow power-law distributions for degree and community sizes.Specifically, these graphs present many small communities but just a few large ones. This unbalanced community size distribution poses a great challenge for community detection algorithms. Most of the existing methods are based on global approaches that require information about the network to be processed as a whole. Thus, those techniques can not be applied when the graph is too big to fit into one single machine, or in distributed setting when the graph is portioned among multiple machines. To solve this limitations a completely decentralized community detection algorithm is presented. It is based on diffusion, following a vertex-centric approach that let each node decide the diffusion rates based on local information. It adds as well a mechanism for controlling the diffusion speed through a customizable function. We evaluate the algorithm with a variety of graphs with different levels of imbalance and community structures. Our algorithm is able to detect (almost)perfectly the communities when the imbalance between community sizes is not extreme. We show as well how the sizes of the detected communities can be controlled by the diffusion strategy, allowing for better detection of finer or coarser resolutions in hierarchical graphs. The algorithm is also compared to other two well-known existing methods, achieving similar results in most of the cases though with a higher computation time.