Preview

PDF, English (Dissertation Stefan Wiesberg) - main document Download (3MB) | Terms of use

Abstract

Network theorists define patterns in complex networks in various ways to make them accessible to human beholders. Prominent definitions are thereby based on the partition of the network's nodes into groups such that underlying patterns in the link structure become apparent. Clustering and blockmodeling are two well-known approaches of this kind.

In this thesis, we treat pattern search problems as discrete mathematical optimization problems. From this viewpoint, we develop a new mathematical classification of clustering and blockmodeling approaches, which unifies these two fields and replaces several NP-hardness proofs by a single one. We furthermore use this classification to develop integer mathematical programming formulations for pattern search problems and discuss new linearization techniques for polynomial functions therein. We apply these results to a model for a new pattern search problem. Even though it is the most basic problem in combinatorial terms, we can prove its NP-hardness. In fact, we show that it is a generalization of well-known problems including the Traveling Salesman and the Quadratic Assignment Problem. Our derived exact pattern search procedure is up to 10,000 times faster than comparable methods from the literature. To demonstrate its practicability, we finally apply the procedure to the world trade network from the United Nations' database and show that the network deviates by less than 0.14% from the patterns we found.

Translation of abstract (German)

Um komplexe Netzwerke dem menschlichen Betrachter zugänglich zu machen, definieren Netzwerktheoretiker den Begriff des Musters auf vielfältige Weise. Gebräuchliche Definitionen beruhen auf der Aufteilung der Netzwerkknoten in Gruppen. Diese Aufteilung geschieht in einer Weise, die Muster in den Verbindungen innerhalb und zwischen den Gruppen erkennen lässt. Bekannte Beispiele hierfür sind Cluster- und Blockmodell-Ansätze.

In dieser Arbeit betrachten wie die Mustersuche als diskretes mathematisches Optimierungsproblem. Von diesem Standpunkt aus entwickeln wir eine neue mathematische Klassifizierung für Cluster- und Blockmodell-Verfahren, welche beide Gebiete vereinigt und bisher unabhängig erbrachte Komplexitätsbeweise zusammenführt. Die Klassifizierung wird außerdem dazu verwendet, mathematische Programme für die Mustersuche zu entwickeln und neue Linearisierungsmethoden für die enthaltenen Polynomfunktionen zu diskutieren. Wir wenden unsere Erkenntnisse auf ein neu formuliertes Mustersuch-Problem an. Trotz seiner einfachen kombinatorischen Struktur können wir bereits seine NP-Schwere nachweisen. Tatsächlich erweist es sich als Verallgemeinerung verschiedener bekannter Probleme, wie dem Traveling-Salesman- und dem Quadratic-Assignment-Problem. Unser abgeleitetes exaktes Mustersuch-Verfahren ist bis zu 10.000-mal schneller als vergleichbare Verfahren aus der Literatur. Zur Demonstration seiner Praktikabilität wenden wir das Verfahren schließlich auf das Welthandelsnetzwerk der Vereinten Nationen an und zeigen, dass das Netzwerk um weniger als 0,14% von den von uns entdeckten Mustern abweicht.