Cohesive subgraphs

• Grant number: 24/18049-0
• Support Opportunities: Scholarships in Brazil - Doctorate
• Start date: April 01, 2025
• End date: March 31, 2029
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Cristina Gomes Fernandes
• Grantee: Yan Soares Couto
• Host Institution: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brazil

Abstract

Graphs are often used to model real-world structures such as social networks or protein interactions. Thus, the visualization and analysis of these graphs become essential for extracting patterns and relevant information (data mining). One area of interest is the search for communities, such as a close group of friends in a social network. This is done by identifying cohesive subgraphs, which are small parts of a graph consisting of similar entities densely connected with specific properties.The problem of finding cohesive subgraphs can be addressed in various ways, such as searching for cliques, k-cores, or strongly connected components. It can be studied in different types of graphs, such as directed, weighted, or dynamic graphs (where edges are added or removed), and under various algorithmic models, such as the LP (locally persistent) model, where each vertex only has access to local information, or the Congest model, a distributed model where processing occurs at the vertices, which can communicate through the edges.The aim of this project is to study and search for new algorithms and results in the area of cohesive subgraphs. We seek both theoretical and practical results, with a focus on implementing the algorithms and experimenting with real-world data.