Institute for Logic, Language and Computation

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

Speaker: Twan van Laarhoven and Elena Marchiori (Nijmegen)
Title: Axioms for Graph Clustering
Date: Friday 27 September 2013
Time: 16:00
Location: Room F1.15, Science Park 107, Amsterdam


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, or contact Ulle Endriss ().

The websites of the UvA make use of cookiesThis site uses cookies More informationMore info Hide this message XHide X