Axioms for graph clustering quality functions

Abstract

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.

23 pages. Full text and sources available on: http://www.cs.ru.nl/~T.vanLaarhoven/graph-clustering-axioms-2014/

References in corpus (9)

• Fast unfolding of communities in large networks
• Finding community structure in networks using the eigenvectors of matrices
• Resolution limit in community detection
• Statistical Mechanics of Community Detection
• Narrow scope for resolution-limit-free community detection
• Identifying network communities with a high resolution
• Significant Scales in Community Structure
• A Uniqueness Theorem for Clustering
• Partitioning and modularity of graphs with arbitrary degree distribution

Cited by in corpus (9)

• On the evaluation potential of quality functions in community detection for different contexts
• Systematic Analysis of Cluster Similarity Indices: How to Validate Validation Measures
• Detecting communities is hard, and counting them is even harder
• A Statistical Density-Based Analysis of Graph Clustering Algorithm Performance
• Towards Continuous Consistency Axiom
• Excisive Hierarchical Clustering Methods for Network Data
• Finding compact communities in large graphs
• Metrics for Community Analysis: A Survey
• Graph Clustering Via QUBO and Digital Annealing