<!DOCTYPE article PUBLIC "-//NLM//DTD JATS (Z39.96) Journal Archiving and Interchange DTD v1.0 20120330//EN" "JATS-archivearticle1.dtd">
<article xmlns:xlink="http://www.w3.org/1999/xlink">
  <front>
    <journal-meta />
    <article-meta>
      <title-group>
        <article-title>Quality Functions in Recognizing Communities in Complex Networks</article-title>
      </title-group>
      <contrib-group>
        <contrib contrib-type="author">
          <string-name>Nenad Mladenovic</string-name>
          <email>nenad@mi.sanu.ac.rs</email>
          <xref ref-type="aff" rid="aff0">0</xref>
        </contrib>
        <aff id="aff0">
          <label>0</label>
          <institution>Mathematical Institute SASA</institution>
          ,
          <addr-line>Belgrade</addr-line>
          ,
          <country country="RS">Serbia</country>
        </aff>
      </contrib-group>
      <kwd-group>
        <kwd>networks</kwd>
        <kwd>community detection</kwd>
        <kwd>quality functions</kwd>
      </kwd-group>
    </article-meta>
  </front>
  <body>
    <sec id="sec-1">
      <title>-</title>
      <p>Many systems in the real world exist in the form of complex networks, such as
biological, social, www, transportation etc. Community detection refers to
nding a subset of vertices, called communities, that are more densely connected
among themselves than with vertices in other communities. There is no precise
de nition of the community but there are many ways to formalize this idea.
One way is to specify an objective function to optimize. Various objective
functions, 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.</p>
    </sec>
  </body>
  <back>
    <ref-list />
  </back>
</article>