A theoretical and computational approach for the community detection problem

• Grant number: 09/16603-0
• Support Opportunities: Scholarships in Brazil - Post-Doctorate
• Effective date (Start): March 01, 2010
• Effective date (End): October 31, 2010
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Computing Methodologies and Techniques
• Principal Investigator: Franklina Maria Bragion de Toledo
• Grantee: Mariá Cristina Vasconcelos Nascimento Rosset
• Host Institution: Instituto de Ciências Matemáticas e de Computação (ICMC). Universidade de São Paulo (USP). São Carlos , SP, Brazil

Abstract

The community detection problem aims at finding groups of nodes in a graph in such a way that the nodes within communities (or clusters) share high connectivity. This problem can be found in literature as either the graph clustering problem or the graph partitioning problem. Its objective is to find a partition in a network or graph. One of the applications of this problem comprehends, e.g., the community detection of social networks to explain the behavior of groups of individuals according to their interactions. This problem can be defined using different objective functions and connectivity measures. In the last decades, the community detection problem was strengthened with the arising of a novel graph partitioning evaluation measure, the modularity. Since then, many studies that optimize (maximize) this measure in order to find partitions in graphs were proposed. In some of these studies, it was observed that, for some types of networks, the communities found by the maximization of the modularity represent a weak clustering. Therefore, a theoretical study to better explain the behavior of the partitions found through its optimization became necessary. Moreover, it was observed that, in general, the spectral clustering algorithms have been proposed without using the bounds provided by the spectral relaxation in the evaluation of the resulting partitions. Therefore, in this project, the candidate intends to approach two issues: the theoretical study of the modularity measure using matroid theory; and the development of hybrid algorithms that combine spectral agorithms and metaheuristics for the maximimization of modularity formulation.