A theoretical approach for the community detection problem in networks

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)