Quality Functions in Graph ClusteringLeonidas Pitsoulis

A central topic in community detection is that of a quality function, that is, a function where for a given graph and a partitioning of its vertices returns a real value that represents the degree upon which this partition exhibits community structure. In this talk we will present a set of axioms for clustering quality functions, and show whether or not these axioms are satisfied by a number of different quality functions. Some of the quality functions that will be presented are well known in the literature and some are new. We will then focus on a certain quality function called modularity and present theoretical results which prove that modularity maximization can both overestimate and underestimate the true number of communities in a graph. Moreover, a new quality function will be presented that is based on the generalization of the degree of a vertex with favorable preliminary computational results. Finally we will discuss about the concept of validity of a cluster and snow its application on a set of artificially generated instances known as Newman-Girvan graphs.