Directly to content
  1. Publishing |
  2. Search |
  3. Browse |
  4. Recent items rss |
  5. Open Access |
  6. Jur. Issues |
  7. DeutschClear Cookie - decide language by browser settings

Link Patterns in Complex Networks

Wiesberg, Stefan

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

Citation of documents: Please do not cite the URL that is displayed in your browser location input, instead use the DOI, URN or the persistent URL below, as we can guarantee their long-time accessibility.

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.

Document type: Dissertation
Supervisor: Reinelt, Prof. Dr. Gerhard
Date of thesis defense: 16 November 2015
Date Deposited: 24 Nov 2015 13:11
Date: 2015
Faculties / Institutes: The Faculty of Mathematics and Computer Science > Dean's Office of The Faculty of Mathematics and Computer Science
The Faculty of Mathematics and Computer Science > Institut für Mathematik
The Faculty of Mathematics and Computer Science > Department of Computer Science
DDC-classification: 510 Mathematics
About | FAQ | Contact | Imprint |
OA-LogoDINI certificate 2013Logo der Open-Archives-Initiative