A spectral heuristic for community detection problem in networks

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)