The analysis of large networks with up to billions of entities (e.g., the Internet, biochemical pathways, or huge social structures) is often based on abstract representations. Density-based clustering is an important technique for deriving these abstractions. In this thesis we dicuss the complexity of finding density-based substructures in large-scale networks, represented as simple, undirected graphs. The main focus is on the analysis of a corresponding fixed parameter dense subgraph problem. We derive a classification for the decision problem that decides whether a given graph contains a subgraph on exactly k vertices and a given minimum number of edges (calculated by some fixed function f of k). Based on the magnitude of function f we state an upper bound for membership in the class of polynomially solvable problems and a lower bound for completeness in NP. A large fraction of real world networks can be sufficiently described in terms of so called power-law graphs, which are characterized by their typical degree sequence. Based on this property, we also discuss the complexity of the above decision problem, when restricted to this class of input graphs. Similarly to the previous classification, we derive corresponding bounds. Finally, we investigate the approximability of an underlying optimization problem. Further, in order to outline some possibilities to overcome the poor best known approximation ratio, we discuss some commonly used heuristics for networks representing the hyperlink structure of the World Wide Web.
Übersetzte Kurzfassung:
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.
Veröffentlichung:
Universitätsbibliothek der Technischen Universität München
Login
BibTeX