| Grant number: | 10/20231-9 |
| Support type: | Research Grants - Young Investigators Grants |
| Duration: | July 01, 2011 - December 31, 2015 |
| Field of knowledge: | Physical Sciences and Mathematics - Computer Science - Computing Methodologies and Techniques |
| Principal researcher: | Mariá Cristina Vasconcelos Nascimento Rosset |
| Grantee: | Mariá Cristina Vasconcelos Nascimento Rosset |
| 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 |
| Associated grant(s): | 12/10698-2 - A theoretical approach for the community detection problem in networks, AV.EXT |
| Associated scholarship(s): | 14/13696-6 - A spectral heuristic for community detection problem in networks,
BP.IC 12/12182-3 - A multilevel metaheuristic for modularity maximization for large scale graphs, BP.IC 11/10315-3 - A Tabu Search metaheuristic for the graph clustering problem, BP.IC |
Abstract
The community detection problem aims at finding groups of nodes in a graph in such a way that the nodes within communities (or clusters) share high connectivity. The objective of this problem is to find partitions in a network or graph. One of its applications consists in determining communities in social networks in order to explain the behavior of groups of individuals taking their iterations into account. This problem can be defined using different objective functions and connectivity measures. In the last decades, the community detection problem was strengthened with the arising of a novel graph partitioning evaluation measure, the text it {modularity}. Since then, many studies that optimize (maximize) this measure in order to find partitions in graphs were proposed. In some of these studies, it was observed that, for some types of networks, the communities found by the modularity maximization-based algorithms has a weak nature. Therefore, a theoretical study to better explain the behavior of the partitions found through its optimization became necessary. In this project, the head researcher intend to approach two topics involving the modularity maximization problem: its theoretical study using matroid theory; and the development of algorithms based on its spectral relaxation, hybridizing them with metaheuristics. In sum up, this project consists on the continuation of the proposal referred as Proc. no. 2009/16603-0 regarding the pos-doctorate financial support. The scholarship started on March 2010 and was cancelled on October 2010 (due to the new position of the researcher as a professor of UNIFESP). (AU)