Axioms for graph clustering quality functions
This work provides a foundational framework for evaluating and designing graph clustering methods, which is incremental but important for researchers in network analysis and machine learning.
The paper tackled the problem of defining axiomatic properties for graph clustering quality functions and showed that the widely-used modularity fails to satisfy all six proposed axioms, leading to the derivation of a new family called adaptive scale modularity that satisfies them and includes standard functions like normalized cut as special cases.
We investigate properties that intuitively ought to be satisfied by graph clustering quality functions, that is, functions that assign a score to a clustering of a graph. Graph clustering, also known as network community detection, is often performed by optimizing such a function. Two axioms tailored for graph clustering quality functions are introduced, and the four axioms introduced in previous work on distance based clustering are reformulated and generalized for the graph setting. We show that modularity, a standard quality function for graph clustering, does not satisfy all of these six properties. This motivates the derivation of a new family of quality functions, adaptive scale modularity, which does satisfy the proposed axioms. Adaptive scale modularity has two parameters, which give greater flexibility in the kinds of clusterings that can be found. Standard graph clustering quality functions, such as normalized cut and unnormalized cut, are obtained as special cases of adaptive scale modularity. In general, the results of our investigation indicate that the considered axiomatic framework covers existing `good' quality functions for graph clustering, and can be used to derive an interesting new family of quality functions.