A theoretical approach for the community detection problem in networks

• Grant number: 12/10698-2
• Support Opportunities: Research Grants - Visiting Researcher Grant - International
• Start date: October 01, 2012
• End date: October 15, 2012
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Computing Methodologies and Techniques
• Principal Investigator: Mariá Cristina Vasconcelos Nascimento Rosset
• Grantee: Mariá Cristina Vasconcelos Nascimento Rosset
• Visiting researcher: Leonidas S. Pitsoulis
• Visiting researcher institution: Aristotle University Of Thessaloniki/Auth , Greece
• 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
• City of the host institution: São José dos Campos
• Associated research grant: 10/20231-9 - A theoretical and computational approach for the community detection problem in networks, AP.JP

Abstract

The challenge of finding groups of vertices (or communities) highly connected in a graph (or network), known as the community detection problem in networks or the graph clustering problem, has arouse interest of many physicians, computer scientists, mathematicians, among other researchers in the last decade. The main reasons for such are its wide applicability and, also, due to the emerging, in 2002, of a measure known as modularity that currently has been used in the community detection in networks, the modularity maximization problem. Although the overwhelming amount of studies in literature to handle with this problem, the theoretical study of the modularity maximization problem is one of the biggest challenges in the community detection in networks research issue. A formal study towards this measure is necessary, since it has been proven that, although it is the most used currently to determine graph clusterings, it has a resolution limit, i.e., this problem fails to detect communities with a low number of vertices in the clusters for some types of networks. Therefore, one of the branches of research, maybe the principal, to be developed with Prof Leonidas Pitsoulis is the formal study using matroid theory for better characterizing the modularity, mainly in graphs for which have proved the low performance of the modularity maximization problem. In both branches of study to be developed, we hope to present important advance in the community detection in networks research issue. (AU)