Quality Functions in Recognizing Communities
             in Complex Networks

                               Nenad Mladenović

                  Mathematical Institute SASA, Belgrade, Serbia
                             nenad@mi.sanu.ac.rs


Keywords: networks, community detection, quality functions.

    Many systems in the real world exist in the form of complex networks, such as
biological, social, www, transportation etc. Community detection refers to find-
ing a subset of vertices, called communities, that are more densely connected
among themselves than with vertices in other communities. There is no precise
definition of the community but there are many ways to formalize this idea.
One way is to specify an objective function to optimize. Various objective func-
tions, also known as quality functions, have been proposed such as normalized
cut, sum-of-squares, ratio cut, edge-ratio, modularity and exponential quality.
In this paper we compare several such functions on small test instances where
communities are known. Communities obtained by each objective function are
evaluated by other quality functions and ranked. Interesting observations are
derived. For example, the objective function that recognized known structures
of all instances, was ranked among worst with respect to other objectives.