Die Analyse großer Netzwerke mit bis zu Milliarden von Elementen (z.B. das Internet, biochemische Netze oder große soziale Strukturen) bedient sich oft abstrahierender Darstellungen. Dichte-basiertes Clustern ist eine wichtige Technik, um diese Abstraktionen zu erzielen.
Die vorliegende Arbeit diskutiert die Komplexität des Auffindens dichte-basierter Substrukturen in großen Netzwerken, die als einfache, ungerichtete Graphen dargestellt werden. Der Schwerpunkt der Arbeit liegt in der Analyse eines entsprechenden ``fixed-parameter'' Entscheidungsproblems zum Finden dichter Subgraphen. Es wird eine Klassifizierung des Problems erzielt, das entscheidet, ob ein gegebener Graph einen Subgraphen auf genau k Knoten mit einer bestimmten Mindestanzahl von Kanten enthält (in Abhängigkeit einer festen Funktion f über k). In Abhängigkeit des Wachstums der Funktion f wird eine obere Schranke für die Zugehörigkeit zur Klasse der polynomiell lösbaren Probleme und eine untere Schranke für eine NP-Vollständigkeit angegeben.
Eine Vielzahl der realen, großen Netzwerke kann gut durch so genannte Power-Law Graphen beschrieben werden, die durch ihre typische Gradverteilung charakterisiert sind. Entsprechend dieser Eigenschaft wird in der Arbeit auch die Komplexität des oben genannten Entscheidungsprobelms betrachtet, wenn die Menge der Eingabegraphen auf diese Graphklasse beschränkt wird. Ähnlich zur vorhergehenden Klassifizierung werden entschrechende Schranken ermittelt.
Abschließend wird die Approximierbarkeit eines zu Grunde liegenden Optimierungsproblems untersucht. Um Möglichkeiten aufzuzeigen, wie die schwache, bestbekannt Approximationsgüte verbessert werden kann, werden für Netzwerke zur Darstellung der Hyperlinkstruktur des World Wide Web einige gängige Heuristiken erläutert.