Informations-, Kommunikations- und Medienzentrum
Informations-. Kommunikations- und Medienzentrum
BTU Cottbus
Eingang zum Volltext
Urheberrechtshinweis / Copyright notice

Bitte beziehen Sie sich beim Zitieren dieses Dokumentes immer auf folgende
URN: urn:nbn:de:kobv:co1-opus-4046
URL: http://opus.kobv.de/btu/volltexte/2007/404/

Noack, Andreas

Unified quality measures for clusterings, layouts, and orderings of graphs, and their application as software design criteria

Einheitliche Gütemaße für Clusterings, Layouts und Orderings von Graphen, und deren Anwendung als Software-Entwurfskriterien

pdf-Format:
Dokument 1.pdf (9.477 KB)

Kurzfassung in Englisch

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 minimize the interdependence of the subsystems? This work introduces and validates simple and uniform measures for these two properties. Together with existing optimization 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 clusterings, 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 orderings, even for graphs without particularly dense or sparse subgraphs, and thus do not (only) measure quality in the above sense.
- For example graphs, the minimization of new, unbiased (or weakly biased) measures reveals nonobvious groups, e.g. communities in social networks, subject areas in hypertexts, or closely interlocked countries in international trade.
The second part derives, validates, and unifies dependency-based indicators of software design quality. It applies two quality measures for graph clusterings as measures for the coupling of software subsystems -- specifically for the coupling indicated by common changes and for the coupling indicated by references -- and shows:
- The measures quantify the dependency-caused development costs, under well-defined simplifying assumptions.
- The minimization of the measures conforms to existing dependency-related design principles (like locality of change, acyclicity of references, and stability of references), design rules, and design patterns.
- For example software systems, the incremental minimization of the measures reveals nonobvious design flaws, like the distribution of coherent responsibilities over several subsystems, or references from low-level to high-level subsystems.
In summary, this work shows that
- simple measures can suffice to capture important aspects of graph clustering quality, graph layout quality, graph ordering quality, and software design quality, and
- the optimization of simple measures can suffice to detect nonobvious and often useful structure in various real-world systems.

Kurzfassung in Deutsch

Wie gut ist ein Graph-Clustering, Graph-Layout oder Graph-Ordering -- insbesondere, wie gut gruppiert es dicht verbundene Knoten? Wie gut ist ein Software-Entwurf -- insbesondere, wie gut minimiert er die Abhängigkeiten zwischen Subsystemen? Für diese beiden Eigenschaften definiert und validiert die vorliegende Arbeit einfache und einheitliche Maße. Zusammen mit existierenden Optimierungsalgorithmen ermöglichen diese Maße die automatische Entdeckung z.B. von kohäsiven Communities in sozialen Netzwerken und von Entwurfsfehlern in Software-Systemen.
Der erste Teil definiert, validiert und vereinheitlicht Gütemaße für Graph-Clusterings, Graph-Layouts und Graph-Orderings, mit folgenden Ergebnissen:
- Identische Gütemaße können auf Clusterings, Layouts und Orderings angewendet werden. Dies ermöglicht die Berechnung von konsistenten Clusterings, Layouts und Orderings.
- Viele existierende und neue Gütemaße können zu wenigen allgemeinen Maßen vereinheitlicht werden; dies erleichtert ihren Vergleich und ihre Validierung.
- Viele existierende Maße messen nicht (nur) Güte im obigen Sinne, da sie selbst für Graphen ohne ungewöhnlich dichte oder dünne Teilgraphen bestimmte Clusterings, Layouts oder Orderings bevorzugen.
- Durch Optimierung verbesserter Maße lassen sich nicht-offensichtliche Gruppen in vielen realen Systemen finden, z.B. Communities in sozialen Netzwerken, Themengebiete in Hypertexten, und Integrationsräume in der Weltwirtschaft.
Der zweite Teil definiert, validiert und vereinheitlicht abhängigkeitsbasierte Indikatoren für Software-Entwurfsqualität. Er verwendet zwei Gütemaße für Graph-Clusterings als Maße für die Kopplung von Software-Subsystemen -- insbesondere für Kopplung, deren Symptom gemeinsame Änderungen sind und für Kopplung, deren Ursache Referenzen sind -- und zeigt:
- Die Maße quantifizieren die durch Abhängigkeiten verursachten Entwicklungskosten, unter vereinfachenden Annahmen.
- Die Optimierung der Maße impliziert anerkannte Entwurfsprinzipien (z.B. Lokalität von Änderungen, Azyklizität von Referenzen, und Stabilität von Referenzen), Entwurfsregeln und Entwurfsmuster.
- Durch Optimierung der Maße lassen sich nicht-offensichtliche Entwurfsfehler finden, z.B. die Verteilung kohärenter Verantwortlichkeiten über mehrere Subsysteme, oder Referenzen von allgemeinen zu speziellen Subsystemen.
Zusammenfassend zeigt die Arbeit, dass
- einfache Maße ausreichen, um wichtige Aspekte der Qualität von Graph-Clusterings, Graph-Layouts, Graph-Orderings und Software-Entwürfen zu formalisieren, und
- die Optimierung einfacher Maße ausreicht, um nicht-offensichtliche und nützliche Struktur in verschiedensten Systemen zu finden.

SWD-Schlagwörter: Softwareentwicklung , Graphische Darstellung , Computergraphik , Projektmanagement
Freie Schlagwörter (deutsch): Graph-Clustering , Graphenzeichnen , Wissensextraktion , Softwareentwurf , Refactoring
Freie Schlagwörter (englisch): Graph clustering , Graph layout , Knowledge discovery , Software design , Refactoring
Collection BTU / Wiss. Publikationen
Institut: LS Praktische Informatik / Software-Systemtechnik
Fakultät: Fakultät für Mathematik, Naturwissenschaften und Informatik
DDC-Sachgruppe: Informatik
Dokumentart: Dissertation
Hauptberichter: Lewerentz, Claus Prof. Dr.
Sprache: Englisch
Tag der mündlichen Prüfung: 06.07.2007
Erstellungsjahr: 2007
Publikationsdatum: 11.12.2007

Home | Suchen | Veröffentlichen | Hilfe | Policy
Fragen und Anregungen an E-Mail
Letzte Änderung:
Hosted by KOBV powered by OPUS