A spectral heuristic for community detection problem in networks

• Grant number: 14/13696-6
• Support Opportunities: Scholarships in Brazil - Scientific Initiation
• Start date: August 01, 2014
• End date: June 30, 2015
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Computing Methodologies and Techniques
• Principal Investigator: Mariá Cristina Vasconcelos Nascimento Rosset
• Grantee: Rodrigo Francisquini da Silva
• Host Institution: Instituto de Ciência e Tecnologia (ICT). Universidade Federal de São Paulo (UNIFESP). Campus São José dos Campos. São José dos Campos , SP, Brazil
• Associated research grant: 10/20231-9 - A theoretical and computational approach for the community detection problem in networks, AP.JP

Abstract

Spectral heuristics for graph clustering problems, also known as community detection in networks, are target of solid research in the past years, mainly because of the improvements of numerical methods for evaluation of eigenvalues and eigenvectors of matrices. Moreover, the consistent theory and the relevance of the obtained solutions using these heuristics have drawn the attention of many researchers. In this project, we intend to guide the student in order to him to acquire a consistent knowledge of graph clustering, specially, the modularity maximization-based problem. Additionally, we aim at introducing to him the spectral heuristics and the spectral relaxation of the aforementioned problem. From this relaxation, a novel spectral heuristic will be developed. The primary objective is this heuristic to be more efficient than that based on dynamic programming-based found in the literature. (AU)