Spectral Theory for Analysing Graph Clustering

• Grant number: 16/22688-2
• Support Opportunities: Scholarships in Brazil - Doctorate
• Start date: May 01, 2017
• End date: 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

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

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, MAR 1 2020. (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., 2019-01-01. (15/21660-4, 16/22688-2)