A multilevel metaheuristic for modularity maximization for large scale graphs

• Grant number: 12/12182-3
• Support Opportunities: Scholarships in Brazil - Scientific Initiation
• Start date: September 01, 2012
• End date: May 31, 2013
• 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
• Associated research grant: 10/20231-9 - A theoretical and computational approach for the community detection problem in networks, AP.JP

Abstract

The community detection problem in networks aims at finding, in a given graph, highly related groups of vertices. The identification of these groups is applied to various research areas, which is the reason why the problem has been intensively studied. Modularity maximization is a common approach for community detection in networks. However, the problem that decides whether a partition has maximum modularity is NP-Complete, thus finding heuristic strategies on literature for its solution is very common. The project premise is to propose, based on the literature review, a heuristic for the modularity maximization problem efficient for large-scale graphs for which there are few heuristics. It is expected that the proposed heuristic, besides being efficient, finds competitive solutions with the current state-of-the-art. (AU)