Unified quality measures for clusterings, layouts, and orderings of graphs, and their application as software design criteria
Andreas Noack · 2007
How good is a given graph clustering, graph layout, or graph ordering – specifically, how well does it group densely connected vertices and separate sparsely connected vertices? How good is a given software design – specifically, how well does it min-imize the interdependence of the subsystems? This work introduces and validates simple and uniform measures for these two properties. Together with existing op-timization algorithms, the introduced measures enable the automatic computation e.g. of communities in social networks and of design flaws in software systems. The first part derives, validates, and unifies quality measures for graph cluster-ings, graph layouts, and graph orderings, with the following results: • Identical quality measures can be applied to clusterings, layouts, and orderings; this enables the computation of consistent clusterings, layouts, and orderings. • Diverse existing and new measures can be unified into few general measures; this facilitates their comparison and validation. • Many existing measures are biased towards certain clusterings, layouts, or order-