27 September 2013, Computational Social Choice Seminar, Twan van Laarhoven and Elena Marchiori (Nijmegen)

Abstract

In this talk we will discuss axioms that intuitively ought to be satisfied by graph clustering quality functions. After a general introduction on graph clustering, its applications and methods for solving it, we will discuss these axioms. Previous work has defined such axioms for distance-based clustering, and we will adapt them to the graph setting. Then we introduce two more axioms, specifically tailored for graph clustering.

Next we will show that the popular modularity quality function does not satisfy all of these axioms, and discuss a way to fix it. This leads to a flexible family of quality functions with desirable real world properties. Standard graph clustering quality functions, such as normalized cut and unnormalized cut, are obtained as special cases of this function.

For more information, see http://www.illc.uva.nl/~ulle/seminar/, or contact Ulle Endriss (ulle.endriss at uva.nl).