Advanced search
Start date

Spectral Theory for Analysing Graph Clustering

Grant number: 16/22688-2
Support Opportunities: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 Investigator:Mariá Cristina Vasconcelos Nascimento Rosset
Grantee:Camila Pereira dos Santos Tautenhain
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


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

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)
TAUTENHAIN, CAMILA P. S.; NASCIMENTO, MARIA C. V.; ROCHA, AP; STEELS, L; VANDENHERIK, J. Spectral Algorithm for Line Graphs to Find Overlapping Communities in Social Networks. PROCEEDINGS OF THE 11TH INTERNATIONAL CONFERENCE ON AGENTS AND ARTIFICIAL INTELLIGENCE (ICAART), VOL 2, v. N/A, p. 12-pg., . (15/21660-4, 16/22688-2)

Please report errors in scientific publications list using this form.