Die Organisation von Handelsstrukturen bringt seit je her weitreichende soziale, politische sowie ökonomische Implikationen mit sich. Da die zugrundeliegenden Dynamiken von Handelssystemen a priori unbekannt sind bieten Konzepte aus der Theorie komplexer Systeme nützliche Werkzeuge, um neue Muster zu entdecken, sowie neue Hypothesen zu den Vorgängen innerhalb der Handelssysteme zu entwickeln. Einen nützlichen Ansatz stellen dabei komplexe Netzwerke dar, da Handelsströme zwischen ökonomischen Einheiten sinnvoll als Knoten und Verbindungen im Netzwerk darstellbar sind. In dieser Arbeit erweitern wir spezielle Methoden auf komplexen Netzwerken, um die Netzwerk-Topologie des Handels auf globaler und auf nationaler Ebene zu untersuchen. Auf dem Level einzelner Industriesektoren erhalten wir neue Einblicke in die topologische Struktur des internationalen Handelsnetzwerks. Dazu führen wir neue Netzwerkmaße ein, welche die Funktion von Knoten in Subgraphen unter dem Blickwinkel, dass das Gesamtsystem durch ein Netzwerk aus mehreren Subnetzwerken dargestellt wird, beschreiben. Im Zuge der Globalisierung gewinnen bilaterale Handelsabkommen bei Entscheidungsträgern an Aufmerksamkeit und werden in zunehmender Zahl verhandelt. Wir entwickeln in dieser Arbeit einen neuen Ansatz, um die Auswirkungen dieser Abkommen auf die beteiligten Ökonomien zu analysieren und zu quantifizieren. Weiterhin behandeln wir die Fragestellung, in welchem Maß Handel als ein Übermittler von Nachfrage- und Angebotsveränderungen auf andere Industrien angesehen werden kann. Schließlich betrachten wir Handelsnetzwerke auf der Ebene von einzelnen Firmen und beschreiben die Funktion von einzelnen Knoten, insbesondere deren Rolle innerhalb von 3er-Motiven. Obwohl alle Methoden und Maße, die wir im Zuge dieser Arbeit einführen, aus Fragen im Kontext des Handels motiviert sind, sind die methodischen Konzepte auf komplexe Netzwerke in anderen Forschungsrichtungen anwendbar. / The organization of trade and its patterns and structures have always had far reaching implications among social, political and economic dimensions. The underlying dynamics of trade systems are often a priori unknown and concepts from complex system theory provide useful tools to discover new patterns and to develop new hypotheses on the mechanisms of the system. Complex networks offer a particularly useful approach to trade systems, as trade flows between economic entities can be intuitively and meaningfully represented as nodes and links in a network. In this thesis, we extend specific methods of complex networks with a focus on the relations between different subnetworks to investigate the network topology of trade on both the global and national scale. On an aggregation level considering individual industries as nodes, we obtain new insights about the topological structure of the international trade network by introducing new network measures that characterize the roles of nodes in subnetworks from a network of networks perspective. During the process of globalization bilateral trade agreements have received rising attention among policy makers and have been negotiated at an increasing pace. Here, we develop a framework to analyze and quantify impacts of these agreements on the involved economies. A further question that we address is to what extent trade can be regarded as a mediator of demand and supply spillovers to other industries. Finally, we look into trade networks at the scale of individual business firms and describe the role of nodes with a focus on 3-node motifs. Although all new methods and measures introduced in this thesis are motivated by questions in the context of trade, the methodological concepts are widely applicable to complex networks of other research disciplines.

In der klassischen Komplexitätstheorie werden worst-case Laufzeiten von Algorithmen typischerweise einzig abhängig von der Eingabegröße angegeben. In dem Kontext der parametrisierten Komplexitätstheorie versucht man die Analyse der Laufzeit dahingehend zu verfeinern, dass man zusätzlich zu der Eingabengröße noch einen Parameter berücksichtigt, welcher angibt, wie strukturiert die Eingabe bezüglich einer gewissen Eigenschaft ist. Ein parametrisierter Algorithmus nutzt dann diese beschriebene Struktur aus und erreicht so eine Laufzeit, welche schneller ist als die eines besten unparametrisierten Algorithmus, falls der Parameter klein ist. Der erste Hauptteil dieser Arbeit führt die Forschung in diese Richtung weiter aus und untersucht den Einfluss von verschieden Parametern auf die Laufzeit von bekannten effizient lösbaren Problemen. Einige vorgestellte Algorithmen sind dabei adaptive Algorithmen, was bedeutet, dass die Laufzeit von diesen Algorithmen mit der Laufzeit des besten unparametrisierten Algorithm für den größtmöglichen Parameterwert übereinstimmt und damit theoretisch niemals schlechter als die besten unparametrisierten Algorithmen und übertreffen diese bereits für leicht nichttriviale Parameterwerte. Motiviert durch den allgemeinen Erfolg und der Vielzahl solcher parametrisierten Algorithmen, welche eine vielzahl verschiedener Strukturen ausnutzen, untersuchen wir im zweiten Hauptteil dieser Arbeit, wie man solche unterschiedliche homogene Strukturen zu mehr heterogenen Strukturen vereinen kann. Ausgehend von algebraischen Ausdrücken, welche benutzt werden können, um von Parametern beschriebene Strukturen zu definieren, charakterisieren wir klar und robust heterogene Strukturen und zeigen exemplarisch, wie sich die Parameter tree-depth und modular-width heterogen verbinden lassen. Wir beschreiben dazu effiziente Algorithmen auf heterogenen Strukturen mit Laufzeiten, welche im Spezialfall mit den homogenen Algorithmen übereinstimmen. / In classical complexity theory, the worst-case running times of algorithms depend solely on the size of the input. In parameterized complexity the goal is to refine the analysis of the running time of an algorithm by additionally considering a parameter that measures some kind of structure in the input. A parameterized algorithm then utilizes the structure described by the parameter and achieves a running time that is faster than the best general (unparameterized) algorithm for instances of low parameter value. In the first part of this thesis, we carry forward in this direction and investigate the influence of several parameters on the running times of well-known tractable problems. Several presented algorithms are adaptive algorithms, meaning that they match the running time of a best unparameterized algorithm for worst-case parameter values. Thus, an adaptive parameterized algorithm is asymptotically never worse than the best unparameterized algorithm, while it outperforms the best general algorithm already for slightly non-trivial parameter values. As illustrated in the first part of this thesis, for many problems there exist efficient parameterized algorithms regarding multiple parameters, each describing a different kind of structure. In the second part of this thesis, we explore how to combine such homogeneous structures to more general and heterogeneous structures. Using algebraic expressions, we define new combined graph classes of heterogeneous structure in a clean and robust way, and we showcase this for the heterogeneous merge of the parameters tree-depth and modular-width, by presenting parameterized algorithms on such heterogeneous graph classes and getting running times that match the homogeneous cases throughout.

Die Regularitätsmethode für Graphen wurde vor über 30 Jahren von Szemerédi, für den Beweis seines Dichteresultates über Teilmengen der natürlichen Zahlen, welche keine arithmetischen Progressionen enthalten, entwickelt. Grob gesprochen besagt das Regularitätslemma, dass die Knotenmenge eines beliebigen Graphen in konstant viele Klassen so zerlegt werden kann, dass fast alle induzierten bipartiten Graphen quasi-zufällig sind, d.h. sie verhalten sich wie zufällige bipartite Graphen mit derselben Dichte. Das Regularitätslemma hatte viele weitere Anwendungen, vor allem in der extremalen Graphentheorie, aber auch in der theoretischen Informatik und der kombinatorischen Zahlentheorie, und gilt mittlerweile als eines der zentralen Hilfsmittel in der modernen Graphentheorie. Vor wenigen Jahren wurden Regularitätslemmata für andere diskrete Strukturen entwickelt. Insbesondere wurde die Regularitätsmethode für uniforme Hypergraphen und dünne Graphen verallgemeinert. Ziel der vorliegenden Arbeit ist die Weiterentwicklung der Regularitätsmethode und deren Anwendung auf Probleme der theoretischen Informatik. Im Besonderen wird gezeigt, dass vererbbare (entscheidbare) Hypergrapheneigenschaften, das sind Familien von Hypergraphen, welche unter Isomorphie und induzierten Untergraphen abgeschlossen sind, testbar sind. D.h. es existiert ein randomisierter Algorithmus, der in konstanter Laufzeit mit hoher Wahrscheinlichkeit zwischen Hypergraphen, welche solche Eigenschaften haben und solchen die „weit“ davon entfernt sind, unterscheidet. / About 30 years ago Szemerédi developed the regularity method for graphs, which was a key ingredient in the proof of his famous density result concerning the upper density of subsets of the integers which contain no arithmetic progression of fixed length. Roughly speaking, the regularity lemma asserts, that the vertex set of every graph can be partitioned into a constant number of classes such that almost all of the induced bipartite graphs are quasi-random, i.e., they mimic the behavior of random bipartite graphs of the same density. The regularity lemma had have many applications mainly in extremal graph theory, but also in theoretical computer science and additive number theory, and it is considered one of the central tools in modern graph theory. A few years ago the regularity method was extended to other discrete structures. In particular extensions for uniform hypergraphs and sparse graphs were obtained. The main goal of this thesis is the further development of the regularity method and its application to problems in theoretical computer science. In particular, we will show that hereditary, decidable properties of hypergraphs, that are properties closed under isomorphism and vertex removal, are testable. I.e., there exists a randomised algorithm with constant running time, which distinguishes between Hypergraphs displaying the property and those which are “far” from it.

Diese Arbeit nutzt und verfeinert Methoden der Komplexitätstheorie, um mit diesen die Komplexität dünner Instanzen zu untersuchen. Dazu gehören etwa Graphen mit wenigen Kanten oder Formeln mit wenigen Bedingungen beschränkter Weite. Dabei ergeben sich zwei natürliche Fragestellungen: (a) Gibt es einen effizienten Algorithmus, der beliebige Instanzen eines NP-schweren Problems auf äquivalente, dünne Instanzen reduziert? (b) Gibt es einen Algorithmus, der dünne Instanzen NP-schwerer Probleme bedeutend schneller löst als allgemeine Instanzen gelöst werden können? Wir formalisieren diese Fragen für verschiedene Probleme und zeigen, dass positive Antworten jeweils zu komplexitätstheoretischen Konsequenzen führen, die als unwahrscheinlich gelten. Frage (a) wird als Kommunikation modelliert, in der zwei Akteure kooperativ eine NP-schwere Sprache entscheiden möchten und dabei möglichst wenig kommunizieren. Unter der komplexitätstheoretischen Annahme, dass coNP keine Teilmenge von NP/poly ist, erhalten wir aus unseren Ergebnissen erstaunlich scharfe untere Schranken für interessante Parameter aus verschiedenen Teilgebieten der theoretischen Informatik. Im Speziellen betrifft das die Ausdünnung von Formeln, die Kernelisierung aus der parameterisierten Komplexitätstheorie, die verlustbehaftete Kompression von Entscheidungsproblemen, und die Theorie der probabilistisch verifizierbaren Beweise. Wir untersuchen Fragestellung (b) anhand der Exponentialzeitkomplexität von Zählproblemen. Unter (Varianten) der bekannten Exponentialzeithypothese (ETH) erhalten wir exponentielle untere Schranken für wichtige #P-schwere Probleme: das Berechnen der Zahl der erfüllenden Belegungen einer 2-KNF Formel, das Berechnen der Zahl aller unabhängigen Mengen in einem Graphen, das Berechnen der Permanente einer Matrix mit Einträgen 0 und 1, das Auswerten des Tuttepolynoms an festen Punkten. / In this thesis, we use and refine methods of computational complexity theory to analyze the complexity of sparse instances, such as graphs with few edges or formulas with few constraints of bounded width. Two natural questions arise in this context: (a) Is there an efficient algorithm that reduces arbitrary instances of an NP-hard problem to equivalent, sparse instances? (b) Is there an algorithm that solves sparse instances of an NP-hard problem significantly faster than general instances can be solved? We formalize these questions for different problems and show that positive answers for these formalizations would lead to consequences in complexity theory that are considered unlikely. Question (a) is modeled by a communication process, in which two players want to cooperatively decide an NP-hard language and at the same time communicate as few as possible. Under the complexity-theoretic hypothesis that coNP is not in NP/poly, our results imply surprisingly tight lower bounds for parameters of interest in several areas, namely sparsification, kernelization in parameterized complexity, lossy compression, and probabilistically checkable proofs. We study the question (b) for counting problems in the exponential time setting. Assuming (variants of) the exponential time hypothesis (ETH), we obtain asymptotically tight, exponential lower bounds for well-studied #P-hard problems: Computing the number of satisfying assignments of a 2-CNF formula, computing the number of all independent sets in a graph, computing the permanent of a matrix with entries 0 and 1, evaluating the Tutte polynomial at fixed evaluation points.

Diese Arbeit beinhaltet {\it geometrische Algorithmen} zur L\"osung reeller polynomialer Gleichungssysteme mit rationalen Koeffizienten, wobei die Polynome eine reduzierte regul\"are Folge bilden (vgl. Abschnitt \ref{abschgeo}). Unter reellem L\"osen verstehen wir hier die Bestimmung eines Punktes in jeder Zusammenhangskomponente einer kompakten glatten reellen Variet\"at $V:=W \cap \R^n$.\\ Im Mittelpunkt steht die Anwendung des f\"ur den algebraisch abgeschlossenen Fall ver\"offentlichten symbolischen geometrischen Algorithmus nach \cite{gh2} und \cite{gh3}. Die Berechenungsmodelle sind {\em Straight--Line Programme} und {arithmetische Netzwerke} mit Parametern in $\; \Q$. Die Input--Polynome sind durch ein Straight--Line Programm der Gr\"o{\ss}e $L$ gegeben. Eine geometrische L\"osung des Input--Glei\-chungs\-sys\-tems besteht aus einem primitiven Element der Ringerweiterung, welche durch die Nullstellen des Systems beschrieben ist, aus einem mininalen Polynom dieses primitiven Elements, und aus den Parametrisierungen der Koordinaten. Diese Darstellung der L\"osung hat eine lange Geschichte und geht mindestens auf Leopold Kronecker \cite{kron} zur\"uck. Die Komplexit\"at des in dieser Arbeit begr\"undeten Algorithmus erweist sich als linear in $L$ und polynomial bez\"uglich $n, d, \delta$ bzw. $\delta \;'$, wobei $n$ die Anzahl der Variablen und $d$ eine Gradschranke der Polynome im System ist. Die Gr\"o{\ss}en $\delta$ und $\delta \; '$ sind geometrische Invarianten, die das Maximum der {\em Grade des Inputsystems} und geeigneter {\em polarer Variet\"aten} repr\"asentieren (bzgl. des ({\em geometrischen}) Grades vgl. \cite{he}). Die Anwendung eines Algorithmus \"uber den komplexen Zahlen auf das L\"osen von polynomialen Gleichungen im Reellen wird durch die Einf\"urung polarer Variet\"aten m\"oglich (vgl. \cite{bank}). Die polaren Variet\"aten sind das Kernst\"uck und das vorbereitende Werzeug zur effizienten Nutzung des oben erw\"ahnten geometrischen Algorithmus. Es wird ein inkrementelles Verfahren zur Auffindung reeller Punkte in jeder Zusammenhangskomponente der Nullstellenmenge des Inputsystems abgeleitet, welches einen beschr\"ankten glatten (lokalen) vollst\"andigen Durchschnitt in $\R^n$ beschreibt. Das Inkrement des Algorithmus ist die Kodimension der polaren Variet\"aten. Die Haupts\"atze sind Satz $\ref{theorem12}$ auf Seite $\pageref{theorem12}$ f\"ur den Hyperfl\"achenfall, und Satz $\ref{theoresult}$ auf Seite $\pageref{theoresult}$, sowie die Aussage in der Einf\"uhrung dieser Arbeit, Seite $\pageref{vollres}$ f\"ur den vollst\"andigen Durchschnitt. / This dissertation deals with {\em geometric algorithms} for solving real multivariate polynomial equation systems, that define a reduced regular sequence (cf. subsection $\ref{abschgeo}$). Real solving means that one has to find at least one real point in each connected component of a real compact and smooth variety $V := W \cap \R^n$. \\ The main point of this thesis is the use of a complex symbolic geometric algorithm, which is designed for an algebraically closed field and was published in the papers \cite{gh2} and \cite{gh3}. The models of computation are {\em straight--line programms} and {\em arithmetic Networks} with parameters in $\; \Q$. Let the polynomials be given by a division--free straight--line programm of size $L$. A geometric solution for the system of equations given by the regular sequence consists in a {\em primitiv element} of the ring extension associated with the system, a minimal polynomial of this primitive element and a parametrization of the coordinates. This representation has a long history going back to {\em Leopold Kronecker} \cite{kron}. The time--complexity of our algorithms turns out to be linear in $L$ and polynomial with respect to $n, d, \delta$ or $\delta '$, respectively. Here $n$ denotes the number of variables, $d$ is an upper bound of the degrees of the polynomials involved in the system, $\delta$ and $\delta '$ are geometric invariants representing the maximum of the {\em affine (geometric) degree} of the system under consideration and the affine (geometric) degree of suitable {\em polar varieties} (cf. \cite{he} for the ({\em geometric}) degree). The application of an algorithm running in the complex numbers to solve polynomial equations in the real case becomes possible by the introduction of polar varieties (cf. \cite{bank}). The polar varieties introduced for this purpose prove to be the corner--stone and the preliminary tool for the efficient use of the geometric algorithm mentioned above. An incremental algorithm is designed to find at least one real point on each connected component of the zero set defined by the input under the assumption that the given semialgebraic set $V = W \cap \R^n$ is a bounded, smooth (local) complete intersection manifold in $\R^n$. The increment of the new algorithm is the codimension of the polar varieties under consideration. The main theorems are Theorem $\ref{theorem12}$ on page $\pageref{theorem12}$ for the hypersurface case, and Theorem $\ref{theoresult}$ on page $\pageref{theoresult}$ for the complete intersection as well as the statement in the introduction of this thesis on page $\pageref{vollres}$.

Wir betrachten ein Kraftwerkssystem mit thermischen Blöcken und Pumpspeicherwerken und entwickeln dafür ein Modell für den kostenoptimalen Wochenbetrieb. Auf Grund der Ungewißheit des Bedarfs an elektrischer Energie ist das mathematische Modell ein mehrstufiges stochastisches Problem. Dieses Modell beinhaltet viele gemischt-ganzzahlige stochastische Entscheidungsvariablen. Die Variablen einzelner Einheiten sind aber nur durch wenige Nebenbedingungen miteinander verbunden, welches die Zerlegung in stochastische Teilprobleme erleichtert. Diese stochastischen Teilprobleme besitzen deterministische Analoga, deren Lösungsverfahren entsprechend erweitert werden können. In dieser Arbeit werden ein Abstiegsverfahren für stochastische Speicherprobleme und eine Erweiterung der dynamischen Programmierung auf stochastische Probleme betrachtet. Die Lösung des dualen Problems führt zu Schattenpreisen, die bestimmte Einsatzentscheidungen bevorteilen. Die Heuristik zur Suche von primalen zulässigen Punkten wertet eine Folge von zugeordneten Economic-Dispatch-Problemen aus. Die Kombination der Einschränkung auf dual bevorzugte Fahrweisen (Lagrangian reduction) mit der Auswertung einer Folge von Economic-Dispatch-Problemen (Facettensuche) führt zu einem effizienten Verfahren. Die numerischen Ergebnisse an Hand realistischer Daten eines deutschen Versorgungsunternehmens rechtfertigen diesen Zugang. / We consider a power generation system comprising thermal units and pumped hydro storage plants, and introduce a model for its weekly cost-optimal operation. Due to the uncertainty of the load, the mathematical model represents a dynamic (multi-stage) stochastic program. The model involves a large number of mixed-integer (stochastic) decisions but its constraints are loosely coupled across operating power units. The coupling structure is used to design a stochastic Lagrangian relaxation method, which leads to a decomposition into stochastic single unit subproblems. The stochastic subproblems have deterministic counterparts, which makes it easy to develop algorithms for the stochastic problems. In this paper, a descent method for stochastic storage problems and an extension of dynamic programming towards stochastic programs are developed. The solution of the dual problem provides multipliers leading to preferred schedules (binary primal variables). The crossover heuristics evaluates the economic dispatch problems corresponding to a sequence of such preferred schedules. The combination of the restriction on dual preferred schedules (Lagrangian reduction) with the evaluation of a sequence (facet search) leads to an efficient method. The numerical results on realistic data of a German utility justify this approach.

Menschliche Systeme werden seit einiger Zeit modelliert und analysiert auf der Basis der Theorie komplexer Netzwerke. Dies erlaubt es quantitativ zu untersuchen, welche strukturellen und zeitlichen Merkmale eines Systems Ausbreitungsprozesse beeinflussen, z.B. von Informationen oder von Infektionskrankheiten. Im ersten Teil der Arbeit wird untersucht, wie eine modular-hierarchische Struktur von statischen Netzwerken eine schnelle Verbreitung von Signalen ermöglicht. Es werden neue Heuristiken entwickelt um die Random-Walk-Observablen “First Passage Time” und “Cover Time” auf lokal geclusterten Netzwerken zu ermitteln. Vergleiche mit der Approximation eines gemittelten Mediums zeigen, dass das Auftreten der beobachteten Minima der Observablen ein reiner Netzwerkeffekt ist. Es wird weiterhin dargelegt, dass nicht alle modular-hierarchischen Netzwerkmodelle dieses Phänomen aufweisen. Im zweiten Teil werden zeitlich veränderliche face-to-face Kontaktnetzwerke auf ihre Anfälligkeit für Infektionskrankheiten untersucht. Mehrere Studien belegen, dass Menschen vornehmlich Zeit in Isolation oder kleinen, stark verbundenen Gruppen verbringen, und dass ihre Kontaktaktivität einem zirkadianen Rhythmus folgt. Inwieweit diese beiden Merkmale die Ausbreitung von Krankheiten beeinflussen, ist noch unklar. Basierend auf einem neuen Modell wird erstmals gezeigt, dass zirkadian variierende Netzwerke Trajektorien folgen in einem Zustandsraum mit einer strukturellen und einer zeitlichen Dimension. Weiterhin wird dargelegt, dass mit zunehmender Annäherung der zeitlichen Dimension von System und Krankheit die systemische Infektionsanfälligkeit sinkt. Dies steht in direktem Widerspruch zu Ergebnissen anderer Studien, die eine zunehmende Anfälligkeit vorhersagen, eine Diskrepanz, die auf die Ungültigkeit einer weit verbreiteten Approximation zurückzuführen ist. Die hier vorgestellten Ergebnisse implizieren, dass auf dem Gebiet die Entwicklung neuer theoretischer Methoden notwendig ist. / Human systems have been modeled and analyzed on the basis of complex networks theory in recent time. This abstraction allows for thorough quantitative analyses to investigate which structural and temporal features of a system influence the evolution of spreading processes, such as the passage of information or of infectious diseases. The first part of this work investigates how the ubiquitous modular hierarchical structure of static real-world networks allows for fast delivery of messages. New heuristics are developed to evaluate random walk mean first passage times and cover times on locally clustered networks. A comparison to average medium approximations shows that the emergence of these minima are pure network phenomena. It is further found that not all modular hierarchical network models provide optimal message delivery structure. In the second part, temporally varying face-to-face contact networks are investigated for their susceptibility to infection. Several studies have shown that people tend to spend time in small, densely-connected groups or in isolation, and that their connection behavior follows a circadian rhythm. To what extent both of these features influence the spread of diseases is as yet unclear. Therefore, a new temporal network model is devised here. Based on this model, circadially varying networks can for the first time be interpreted as following trajectories through a newly defined systemic state space. It is further revealed that in many temporally varying networks the system becomes less susceptible to infection when the time-scale of the disease approaches the time-scale of the network variation. This is in direct conflict with findings of other studies that predict increasing susceptibility of temporal networks, a discrepancy which is attributed to the invalidity of a widely applied approximation. The results presented here imply that new theoretical advances are necessary to study the spread of diseases in temporally varying networks.