Advanced search
Start date
Betweenand

Spectral Theory for Analysing Graph Clustering

Grant number: 16/22688-2
Support type:Scholarships in Brazil - Doctorate
Effective date (Start): May 01, 2017
Effective date (End): February 07, 2021
Field of knowledge:Physical Sciences and Mathematics - Computer Science - Computing Methodologies and Techniques
Principal researcher:Mariá Cristina Vasconcelos Nascimento Rosset
Grantee:Camila Pereira dos Santos Tautenhain
Home 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

Abstract

The literature is vast in algorithms to approach the graph partitioning problem. Algorithms based on the spectral relaxation of several formulations of this problem are knownas spectral clustering heuristics, algorithms conceptually elegant and that achieve satisfactory results. The computational cost of these algorithms, however, oftentimes makesthem impracticable to deal with large scale graphs. Moreover, the relaxations based onthe adjacency matrix cannot detect clusters of certain types of sparse graphs. In thissense, it was proposed an excelent alternative for aproaching sparse graphs consideringthe spectral relaxation of a new matrix, based on non-backtracking paths in the graph.This project aims at addressing the problem of clustering large scale graphs by new spectral heuristics. By manipulating the non-backtracking matrix, we expect to find groups inlarge scale graphs with thousands of vertices and edges and to improve the results from theliterature for these graphs by using new strategies introduced in this study. Furthermore,we intend to contribute with theoretical aspects and investigate new evaluation measuresthat measure better the quality in graphs with these characteristics

News published in Agência FAPESP Newsletter about the scholarship:
Articles published in other media outlets (0 total):
More itemsLess items
VEICULO: TITULO (DATA)
VEICULO: TITULO (DATA)

Scientific publications
(References retrieved automatically from Web of Science and SciELO through information on FAPESP grants and their corresponding numbers as mentioned in the publications by the authors)
TAUTENHAIN, CAMILA P. S.; NASCIMENTO, V, MARIA C.. An ensemble based on a bi-objective evolutionary spectral algorithm for graph clustering. EXPERT SYSTEMS WITH APPLICATIONS, v. 141, . (16/22688-2, 15/21660-4)

Please report errors in scientific publications list by writing to: cdi@fapesp.br.